Hash Functions
Mapping keys to buckets.
What Is a Hash Function
A hash function takes a key and produces an integer index into an array of buckets. It is the heart of a hash table, turning arbitrary keys like strings into fast array positions.
- Input: a key (string, integer, etc.)
- Output: a bucket index in
[0, capacity)
Properties of a Good Hash
A good hash function is deterministic, fast, and spreads keys uniformly across buckets.
- Same key always gives the same index
- Small key changes cause large index changes (avalanche)
- Few collisions for typical data