Hash Table
Luhn wrote it down in an IBM memorandum in early 1953: put the thing in a bucket chosen by a function of the thing itself, and you can find it again without looking through everything. The part that is usually drawn as an animation and left there is the cost. A bad hash does not make lookups slower by some constant; it collapses them into walking a list. What follows counts the walking.
New to hashing? Start here
A hash function turns a key of any size into a number in a fixed range. What a table needs of it is that the numbers come out spread evenly over the range whatever the keys look like, which usually means similar keys land nowhere near each other, though that is a symptom rather than the requirement. Use the number as a position in an array and a lookup goes straight to one bucket instead of searching the whole table. It is not one step: what is in that bucket still has to be walked, and counting those steps is what this page does.
The catch arrives immediately. There are more possible keys than positions, so two keys will eventually want the same one, and no cleverness removes that: it is counting, not engineering. Everything else on this page is about what to do when it happens.
A key, a drawer, and what happens when two keys want the same one
1 A key, and the index the hash sends it to
The function is arithmetic on the characters, and the bucket is that number modulo how many buckets there are. Nothing about the key is stored in the index.
2 Two keys that want the same drawer
Twenty-five words, in sixteen buckets. Switch the function and watch where they land. A bucket holding more than one key is outlined, because that is a bucket somebody will have to walk.
3 Chaining, and the probe count it costs
The number after each key is how many items a lookup touches to reach it. That is the probe count. It is the measure this page counts, and the honesty ledger names the two it cannot: how the walk behaves in a cache, and how expensive one key comparison is.
4 Load factor, and where the constant time goes
Keys divided by buckets is the load factor. Take the buckets away and the same keys have to share.
Constant time was never a promise about one lookup. It is a statement about the average when the load factor is held down and the function spreads, and both of those are things somebody has to keep true.
These ran in this browser at load.
| claim | held | measured |
|---|---|---|
| a good hash spreads 25 keys across most of the buckets | yes | 13 of 16 buckets used |
| a hash on the key's length alone leaves most buckets unreachable | yes | 7 buckets used against 13 |
| and the difference between these two tables is in probes, not in a complexity class | yes | mean 1.68 probes against 2.92 |
| the worst lookup in the bad table walks a chain several long | yes | worst 4 against 7 |
| raising the load factor raises the mean probe count | yes | load 0.50 gives 1.00, load 3.13 gives 2.40 |
| every key is still found with the bad hash, because only the cost changed | yes | 25 keys, 0 lost |
What is real here, and what is not
Chaining only, which is half the subject
Every bucket here holds a list. Open addressing, where a colliding key goes to another bucket instead, is the other family and none of it is modelled: no linear probing, no double hashing, no tombstones on delete. It is separate work from Luhn's, developed around the same period, and this page does not name the people involved because it has not read a source that establishes who did what.
The bad hash is bad on purpose, and on these words
Hashing by the key's length fails here because twenty-five words have seven distinct lengths, so nine of the sixteen buckets can never be reached. On different data it would fail differently, or not much at all. The first version of this page hashed on the first character instead and it was not bad enough to show anything: on this word list it used the same thirteen buckets FNV did, and the page would have claimed a difference the numbers did not support.
Probes, not seconds
Every cost on this page is a count of items touched. Real cost is dominated by things this page has no access to: whether the chain is in cache, how the allocator laid it out, how long the comparison takes. A probe count is the thing those multiply, not the answer.
Twenty-five keys cannot show you the failure that matters
The bad hash on this page costs 2.92 probes against 1.68, and its worst lookup walks seven. That is a difference in probes rather than in complexity, and it is true of these twenty-five keys and not of hashing in general. A chaining table whose hash sends everything to one bucket is a linked list with extra steps: every lookup walks all n, and the constant time is gone rather than worse. Real implementations defend against that, with a randomised seed so an attacker cannot choose the keys, or by replacing a long chain with a tree. None of that is here, and twenty-five keys is too few to make it visible even if it were.
The number the hash starts from is an accident
The offset basis looks like a chosen constant and is not one. RFC 9923 says it is the FNV-0 hash of a 32-character string, and that the string is a copy of Landon Curt Noll's email signature made by somebody who misread it. Almost any non-zero value would do the same work. The tests here do not type the number in: they take that string out of the archived RFC and compute it.
No sound
Nothing here has a duration to hear.
The date is the year, and the month is not on this page
IEEE Spectrum places Luhn's memorandum in early 1953 and gives no month. January is what other accounts repeat. The chronology sorts it in January so that it sits ahead of the other 1953 entry, and that is a sorting decision rather than a claim, which is why no month is printed above.
Sources
- IEEE Spectrum, Hans Peter Luhn and the Birth of the Hashing Algorithm. Fetched and checked: it places the memo in early 1953 and describes the buckets. It does not give a month.
- L. Noll, K. Vo, D. Eastlake 3rd and T. Hansen, RFC 9923: The FNV Non-Cryptographic Hash Algorithm, February 2026. The specification the good hash follows. Section 5 prints the 32-bit prime and the offset basis, section 2 gives the order of the exclusive-or and the multiply, and section 8.2.1 carries the authors' own C. This page's tests compile that C out of the archived copy and run every word through it.
- Glenn Fowler, Landon Curt Noll and Phong Vo, FNV Hash. The authors' own page, which carried these constants for years before the RFC did.
- Logical Art, the studio this belongs to.