Mapping keys to buckets
A hash table stores key value pairs and aims for near constant time lookup. A hash function turns each key into a number, and that number, reduced modulo the table size, names a bucket. Ideally each key lands in its own bucket, but two keys can map to the same one. That clash is a collision.
Resolving collisions by chaining
Separate chaining handles collisions by storing, in each bucket, a small linked list of all pairs that hashed there. To look up a key you compute its bucket, then walk that short list comparing keys. To insert, you append to the list. To delete, you unlink the matching node.
- A good hash spreads keys so lists stay short.
- A bad hash piles keys into one bucket, degrading lookups toward a linear scan.
The load factor
The load factor is the number of stored entries divided by the number of buckets. As it climbs, lists grow and performance drops. Implementations watch it and resize, allocating more buckets and rehashing every entry, to keep the average chain short and lookups near constant time.
Key idea
A chaining hash table maps keys to buckets and stores colliding entries in per bucket linked lists, giving near constant average lookups as long as a good hash and a controlled load factor keep the chains short.