When a Hash Lookup Stops Being O(1)

A hash table finds a key in O(1) only while its keys spread across many buckets. When many keys share one bucket, a lookup compares the key it wants with each of them in turn, and costs O(n). This card covers what causes that, a run that measures it, and the defence Java builds into its HashMap.

Three things put many keys in one bucket. A poor hash function gives many keys the same hash code: one that adds up the letters of a word gives listen and silent the same code, and every other rearrangement of those six letters too. Keys can share a pattern the hash function passes straight through, such as whole numbers that are all multiples of the capacity. And someone who knows the hash function can choose keys that collide on purpose, to slow a server down, which is why Python changes the hash codes of its strings from one run to the next.

A run measured the effect in a Python dict. It stored n keys whose hash code was either each key's own number or, for every key, 42. Then it looked up one stored key and counted how many different stored keys the lookup compared it with:

With distinct hash codes the lookup compared one key at every size, which is O(1). With one hash code for all, it compared every key the table held, so its cost grew with n: O(n) for one lookup, and O(n²) for a loop of n lookups. A dict stores keys by probing, not chaining, and the result is the same, because every key's walk starts at the same slot and follows the same path.

Java 8 and later limit the damage in HashMap. Once a bucket holds more than eight keys and the table has at least 64 buckets, the bucket becomes a balanced tree, a structure that keeps a search to O(log n) steps. A smaller table doubles its buckets instead. The tree helps most when the keys can also be compared as smaller or larger, so the reliable defence is still a hash function that spreads keys well. The cost of a hash lookup is O(1) expected, and O(n) when the keys pile into one bucket.