Hash table
O(1) average lookup via key → bucket index.
Origin
Hans Peter Luhn at IBM in January 1953 wrote the first internal memo describing a "hash addressing" technique for IBM 701 file storage. Independently rediscovered several times in the late 1950s. The name "hash" came later.
Where it shows up in production
- Every language Python dict, Go map, JavaScript Object/Map, Ruby Hash, Java HashMap, C++ unordered_map.
- Memcached & Redis A hash table is the entire data structure for KV operations; everything is keyed access.
- Database join hash tables Hash join builds an in-memory hash on one side, probes with rows from the other.
On Semicolony
Sources & further reading
Found this useful?