Basis Lab

Answers · Making it fast enough

Why can a hash table find something without scanning everything else?

In shortA hash table does not search its contents faster. It computes where the item must sit from the key itself, so the number of stored items never enters the calculation.

A hash table never looks through what it holds. It turns the key into a position with a few arithmetic steps and goes straight to that position. Nothing is compared on the way there, so the count of stored items appears nowhere in the calculation, which is why the lookup costs the same at ten items as at ten million. The table is not a faster pair of eyes; it is a map that was computed rather than searched.

address=start+k⋅w\text{address} = \text{start} + k \cdot w

Take the simplest case, where the key is already a small whole number. Reserve one slot per possible key and put each record at its own number: key 0 at slot 0, key 7 at slot 7. If a slot is w=8w = 8 bytes and the keys run from 0 to 999, the table occupies 1000×8=80001000 \times 8 = 8000 bytes, and finding key 431 is one multiplication and one addition, regardless of whether 3 records or 1000 records are actually stored. Now change the keys to nine digit order identifiers. The same recipe needs 10910^{9} slots at 8 bytes each, which is 8×1098 \times 10^{9} bytes, about 8 gigabytes, to hold perhaps a thousand records worth 8000 bytes. That is a million times more memory than data, and almost all of it is empty slots holding nothing. The rule is instant and correct and unusable, which is the whole reason a hash function is needed.

The natural guess is that the table must be doing the same scan, only with better machinery inside the loop, perhaps comparing many keys at once or keeping them in some clever arrangement. That guess fails because no amount of cleverness inside a loop changes how many times the loop runs. A scan of a million records reads, on average, about 500,000 of them, and every one of those reads is work. A hash table reads exactly one. The difference is not speed, it is that one procedure consults the collection and the other does not consult it at all.

So the position is computed instead: h(k) mod mh(k) \bmod m, where hh turns the key into a large integer and mm is the number of slots you can actually afford.

slot=h(k) mod m\text{slot} = h(k) \bmod m

If you hold 1000 records and can afford m=2000m = 2000 slots, then every key lands somewhere in those 2000, and collisions are not bad luck but arithmetic. Two keys share a slot whenever their hash values differ by a multiple of 2000, and with 1000 keys spread over 2000 slots you expect roughly 10002/(2×2000)=2501000^{2} / (2 \times 2000) = 250 colliding pairs. Those are handled by a short chain or a probe, so a lookup examines one item plus whoever shares its slot, which under a decent hash averages close to one and a half. Still no dependence on the collection size: doubling the records doubles the slots, and the average stays where it was.

What the hash function has to do

For that argument to hold, hh must be deterministic, so the same key always gives the same slot, and it must spread keys evenly, so no slot collects a crowd. It must also be cheap: it takes time proportional to the length of the key, which is the same whether the table holds ten records or ten million. A hash that is slow, or that sends similar keys to neighbouring slots, breaks the promise quietly, because the cost then creeps back in through longer chains rather than through the arithmetic.

FIG 1
items storedscan, averagehalving a sorted listhash table
1,000500101
1,000,000500,000201
1,000,000,000500,000,000301

The constant time is an average over keys, not a guarantee. If an adversary knows the hash and can choose the keys, they can aim a thousand of them at one slot, and the chain there has to be scanned just like a list, taking you back to linear cost with the memory overhead still paid. A weak hash does the same by accident. The other limit is structural rather than probabilistic: nothing about the position preserves order, so you cannot ask for everything between two keys, or the smallest key, or a traversal in sequence, without examining the contents. A structure that computes where one thing lives is excellent at exactly that and gives up anything that needs the neighbours. If you need those, you pay for order, as a sorted array or a tree does, and the twenty comparisons come back.

Worth keeping

  • A hash table computes a position from the key and goes there, so the number of stored items never enters the lookup.
  • A direct table with one slot per possible key is instant but needs memory proportional to every key that could exist, which is why real keys need a hash.
  • Collisions are certain when there are more possible keys than slots, and a bad or adversarially chosen hash turns the average lookup back into a scan.

Where this goes next

This question is one step of Finding It Instantly, a course that works through its subject from the beginning. The page that teaches this part of it is Finding One Thing Among Many, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that pageThe whole course

Other questions people ask about this

  1. How does a hash function turn a word into an array index?A hash function reads the word as bytes, mixes them into one large number, then takes the remainder after dividing by the table size to get an index from zero to size minus one.
  2. How can you check whether something is in a set without storing every item?Record a few hashed marks per item in a bitmap; all marks set means probably present, any mark clear means certainly absent.
  3. Why can't a hash table give me the next key in order?Because a good hash deliberately scatters neighbouring keys, so the table keeps no record of which key comes after which; finding the next key means reading every entry.
  4. Why does a hash table need to grow before it is completely full?Because what makes lookup fast is how full the table is, not how big it is: near full, a lookup turns into a scan well before the last slot is taken.
  5. Why doesn't breadth-first search give the cheapest path once the links have different costs?Breadth-first search counts links rather than costs, so it can return a route with fewer links that is more expensive than a longer route.
  6. Why is O(2n) treated the same as O(n)?Because it describes how cost grows rather than exact cost, doubling every cost does not change the growth class.

Read alongside