Search tools and guides ⌘K
III · Hashing & lookup

Hash table

O(1), almost always.

1953 · Hans Peter Luhn · IBM internal memo
The story

Luhn's 1953 memo at IBM was the first written description of hashing — chained collision lists, modulo-prime hashing. He never published it; the idea spread through internal IBM technical reports until Donald Knuth catalogued it in TAOCP Vol. 3 (1973). Luhn also invented the now-eponymous credit-card checksum.

How it works

Hash function maps key → bucket index. Two collision strategies: chaining (each bucket is a list) and open addressing (probe to next slot). Load factor (entries / buckets) controls collision rate; resize when above ~0.75.

Where it lives

Every language's dictionary/map type. CPython dict (open addressing with perturbation). Java HashMap. Go map. Rust HashMap. Database hash indexes. Compiler symbol tables. Caches everywhere.

The key insight

A bad hash function turns a hash table into a linked list. Hash flooding attacks (exploiting predictable collisions) are why every modern hashmap uses a randomised hash seed.

More in Hashing & lookup
Cuckoo hashing Two slots, no chains. Robin Hood hashing Steal from the rich, give to the poor. Consistent hashing Hashing that survives node changes. Perfect hashing Zero collisions, by design.
Across the cabinet
IV Bloom filter A set, in a thousandth of the space. IV HyperLogLog Count distinct, in 12 KB. IV Count-Min sketch Approximate frequencies, in tiny memory. IV MinHash Set similarity, in a few hashes. IV t-digest Quantiles, fairly accurate, fully streaming. V Suffix array All suffixes, sorted. V Suffix tree Every substring, in linear space. V Rope A tree of small strings.
← All data structures