Dictionaries, sets, caches, database indexes: whenever you look things up by key, there's probably a hash table underneath. Instead of searching for a key, a hash function computes where it should be, so search, insert and delete take O(1) time on average.
The table is an array of m slots. Key k belongs in slot h(k) = k mod m, the remainder after dividing by m. For example, with m = 7, 22 = 3 × 7 + 1, so 22 goes in slot 1. Choosing m prime helps spread out keys that share a pattern, like multiples of 10. Real tables hash strings and objects with fancier functions, but the idea is the same.
With more possible keys than slots, two keys will sometimes hash to the same slot: a collision. (15, 22 and 8 all give remainder 1 when divided by 7.) There are two classic fixes:
| Separate chaining | Linear probing | |
|---|---|---|
| Idea | Each slot holds a list (chain) of all keys that hash there. | Each slot holds one key. If a key's slot is taken, use the next free slot, wrapping from the last slot to slot 0. |
| Insert | Hash, append to the chain. | Hash, then probe forward to the first free slot. |
| Search | Hash, scan the chain. | Hash, probe forward until you find the key or reach an empty slot. |
| Delete | Unlink it from the chain. | Leave a deleted marker (DEL), not an empty slot (see below). |
In the picture, 8 belongs in slot 1 but sits in slot 3, because 15 and 22 were there first. A search for 8 starts at slot 1 and walks forward. If 22 were deleted by simply emptying slot 2, that search would hit the empty slot and give up, wrongly concluding 8 isn't there. A deleted marker says "something was here, keep going". Inserts may reuse a marked slot.
The load factor α = n / m says how full the table is. As it grows, chains get longer and probe runs (clusters) get longer, so operations slow down. When α passes a limit, the table grows to a prime at least twice as big and rehashes every key: since h(k) depends on m, every key's slot changes. These pages use the limits 3/4 for chaining (as Java's HashMap does) and 2/3 for probing (as Python's dict does). For probing, deleted markers count too, because they lengthen probe runs just like keys do.
| Cost | |
|---|---|
| Average | O(1) per operation, as long as the load factor stays bounded (resizing makes sure of that; an occasional O(n) rehash averages out). |
| Worst case | O(n): if every key collides, a hash table is no better than a list. Good hash functions make that vanishingly unlikely. |