Hash Functions

1. A good hash function gives an average-case lookup that is a small constant, independent of the number of search keys.
2. We hope records are distributed uniformly among the buckets.
3. The worst hash function maps all keys to the same bucket.
4. The best hash function maps all keys to distinct addresses.
5. Ideally, distribution of keys to addresses is uniform and random.
6. 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).