Next: Handling of bucket overflows
Up: Hash File Organization
Previous: Hash File Organization
 A good hash function gives an averagecase lookup that is a
small constant, independent of the number of search keys.
 We hope records are distributed uniformly among the buckets.
 The worst hash function maps all keys to the same bucket.
 The best hash function maps all keys to distinct addresses.

Ideally, distribution of keys to addresses is uniform and random.

Suppose we have 26 buckets, and map names beginning with ith letter of the
alphabet to the ith bucket.
 Problem: this does not give uniform distribution.
 Many more names will be mapped to ``A'' than to ``X''.
 Typical hash functions perform some operation on the internal
binary machine representations of characters in a key.
 For example, compute the sum, modulo # of buckets, of the binary
representations of characters of the search key.
 See Figure 11.18, using this method for 10 buckets (assuming the
ith character in the alphabet is represented by integer i).
Osmar Zaiane
Mon Jul 13 13:28:03 PDT 1998