Hash tables: keys, collisions and lookup cost

Suppose a program stores a user’s name under an ID. To retrieve it, the table turns the ID into a bucket number and checks the entries there. This avoids walking every stored user, provided most lookups have only a small amount of work in their chosen bucket.

Follow a key to its bucket#

In this simplified five-bucket example, use the remainder after division by five as the bucket number. Keys 1, 6 and 11 all choose bucket 1. Predict where the third key will go, then insert the keys and switch between keeping a list in that bucket and searching for another free slot.

Try it: where does a colliding key go?

Five slots use the simple teaching hash key mod 5. Add the preset keys one by one, then switch collision strategies and compare where they land. This model uses linear probing; real tables may choose another probe sequence.

Collision strategy ChainingLinear probing Insert next key Reset

1. 0empty
2. 1empty
3. 2empty
4. 3empty
5. 4empty

Insert 1, 6, 11, 3 and 8 to see what happens.

A hash function turns a key into a number. The table reduces that number to a bucket and then compares keys, because different keys can choose the same bucket. In the chaining mode above, looking for 11 after inserting 1, 6 and 11 checks those three keys in turn. The arithmetic finds the starting place; it does not identify the entry by itself.

With well-distributed hashes and controlled occupancy, lookup needs an expected constant number of probes or comparisons, written O(1). That model usually treats hashing and equality as fixed-cost operations. A long string may take time to hash, and a custom equality check may have its own cost. Expected O(1) is not a worst-case guarantee for every input.

Java 21’s HashMap reference conditions its constant-time basic operations on proper hash dispersal. OpenJDK’s HashMap source also implements tree bins, so the lab models simple chaining and linear probing, not all of HashMap. See how collisions change lookup and deletion for both recovery rules and their limits.

That bucket mechanism is common to several Java maps. HashMap versus Hashtable is a separate choice about locking and null values, not a different way to calculate a bucket.

Load factor and the cost of growing#

The current load factor is the entry count divided by the bucket count. Three entries in the lab’s five buckets give 3/5 = 0.6, even when all three share one bucket. Occupancy tells you how much is stored overall; it does not tell you whether one bucket is overloaded. A chained table can also hold more entries than buckets, so its load factor can exceed one.

A resizing threshold is a separate policy. Java HashMap grows when its entry count exceeds its configured load factor times its capacity. The default is 0.75; a capacity of 16 therefore has a threshold of 12 entries. Growing rebuilds the table with approximately twice as many buckets. The lab keeps five buckets throughout and does not simulate this resize.

Java documents its default as a time/space trade-off. Raising the threshold uses less bucket space and permits more collision work; lowering it spends memory to reduce that pressure. An insertion that triggers a resize still pays for the rebuild. As with a growable array, amortised analysis spreads occasional rebuilding across many insertions; it does not promise that every insertion is fast.

Oversized tables and changing keys#

More buckets can avoid some growth, but they are not free. Java HashMap documents iteration work proportional to capacity plus size. A populated map with a very large bucket array and only twelve entries still pays to scan that array. This is an implementation-specific reason to avoid excessive capacity when iteration matters; it is not an iteration rule for every hash table.

A key can also become hard to find when fields used by its hash or equality change after insertion. The entry was placed using the old hash, while the next lookup may search using the new one. Equal keys must have equal hashes, as Java’s Object contract specifies. Keep those key properties stable; a coincidentally unchanged hash can hide an unsafe mutation.

Questions people also ask

3 QUESTIONS

▸ Is a hash table lookup really O(1)?

Expected O(1) table work needs well-distributed hashes and bounded occupancy, and usually treats key hashing and equality as fixed-cost operations. A long string can cost time to hash; collisions add comparisons; resizing makes an individual insertion expensive. Java HashMap may turn long collision bins into trees, so a simple linked-chain worst case is not every implementation's worst case.

▸ What is the load factor for?

Current load factor is entries divided by buckets. An implementation can separately configure the threshold at which it grows. Java HashMap's default threshold is 0.75: lower values spend more bucket space, while higher values permit more collision work. This is Java's choice, not a universal threshold for every hash table.

▸ Why is iterating a hash map slower than I expect?

Because iteration has to walk the buckets, not just the entries. Java documents the cost as proportional to the capacity plus the size — so a table given a large initial capacity and then filled with ten entries still pays for every empty bucket on every pass. Oversizing a map you intend to iterate is a real cost, not a harmless safety margin.