Buckets and hashing
A hash table maps keys to slots called buckets. A hash function turns a key into a number, which is reduced into a bucket index. Ideally each key lands in its own bucket, but different keys can hash to the same index, a collision.
Separate chaining
The chaining strategy handles collisions by making each bucket hold a small linked list of all entries that map to it:
- Insert computes the bucket and prepends the entry to that bucket's list.
- Lookup computes the bucket and scans its list comparing keys.
- Delete finds the entry in the list and unlinks it.
When the hash function spreads keys evenly, the lists stay short, so operations are fast on average.
The load factor
What keeps the lists short is the load factor, the ratio of stored entries to buckets. As it rises, lists lengthen and lookups slow. Implementations resize, allocating more buckets and rehashing entries, once the load factor crosses a threshold, restoring short chains.
Key idea
Chaining stores colliding keys in a per bucket linked list and resizes when the load factor grows, keeping the chains short so average operations stay fast.