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.
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, and it is the only honest measure of what the table cost.
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 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.
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.