Hash tables

A hash table is the structure people reach for when they want lookup to stop being a search, and it delivers on that so reliably that the condition underneath it is easy to forget. The condition is not a footnote. Almost every way a hash table disappoints you is that condition failing quietly, and the settings it exposes are all there to keep it true.

Constant time, with a condition attached#

The idea is to compute where a key belongs rather than look for it. Run the key through a hash function, reduce the result to a bucket number, and go straight there. Nothing is scanned, nothing is compared on the way, and the size of the table does not enter into it — which is what makes the operation constant time rather than proportional to anything.

Java’s HashMap documentation states the guarantee with its condition attached, and the phrasing repays reading closely: the implementation provides constant-time performance for the basic operations, assuming the hash function disperses the elements properly among the buckets. If the keys spread out, each bucket holds roughly one thing and finding it is immediate. If they pile into a few buckets, the lookup still finds the right bucket instantly and then has to work through everything sitting in it. The address arithmetic never degrades; what degrades is how much is waiting at the address — which is the subject collisions and how a table resolves them takes up in its own right.

The load factor is the dial#

Even a good hash function produces collisions once the table gets full, for the same reason a room of thirty people probably shares a birthday: with more keys than buckets, sharing is arithmetic rather than bad luck. So a hash table watches how full it is and grows before that becomes the normal case. Java’s rule is exact — when the number of entries exceeds the load factor multiplied by the current capacity, the table is rehashed into roughly twice as many buckets.

The load factor is where that trade is set, and 0.75 is the default because, in the documentation’s words, it offers a good tradeoff between time and space costs. Push it higher and you use less memory while making lookups dearer. Push it lower and lookups stay cheap while you pay for buckets you are not using. Rehashing itself is the same bargain a growable array strikes when it doubles: an occasional expensive rebuild, spread thin enough across the operations that follow that no individual one has to carry it.

Where it goes wrong#

The failure that surprises people is oversizing. Giving a map a large initial capacity feels like a free precaution — it avoids rehashing, and the extra buckets are only memory. But Java documents iteration as costing time proportional to the capacity plus the size, because a pass has to visit the buckets and not merely the entries. A map built with room for a million and holding twelve will walk a million buckets every time you iterate it, and the documentation says so directly: it is very important not to set the initial capacity too high if iteration performance matters.

The second is a key whose hash and equality do not agree, or whose value changes after insertion. A hash table computes the bucket once, at insertion. Mutate a field the hash depends on and the entry is now filed under an address nobody will compute again — the map still contains it, iteration still lists it, and a lookup with an equal key returns nothing. No error is raised, because from the table’s side nothing invalid has happened. This is why keys are conventionally values that do not change, and why breaking that convention produces one of the quietest bugs in ordinary application code.