next up previous
Next: Handling of bucket overflows Up: Hash File Organization Previous: Hash File Organization

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.

Osmar Zaiane
Mon Jul 13 13:28:03 PDT 1998