Hash tables

A hash function maps each key to one of m slots in an array. With more possible keys than slots, two keys will sometimes land on the same slot, so every design handles collisions: chaining keeps a small list per slot, and open addressing probes other slots in the same array. If keys spread evenly and m grows with n, each lookup touches O(1) entries on average, and resizing is amortized like a dynamic array’s, giving “expected amortized O(1)” operations in MIT’s 6.006 notes. Tables grow before they get too full: most cap the load factor (the share of used slots) at 70–90%, and Java’s HashMap defaults to 0.75, then rehashes into about twice as many buckets.

The O(1) is expected, not guaranteed. Python’s complexity table lists O(n) as the worst case for dict lookups, and any fixed hash function has inputs that all collide. Rust’s HashMap seeds its hash (SipHash 1-3 by default) randomly to resist HashDoS attacks, and its docs note that faster hashers exist for small keys such as integers. Modern designs tune for the CPU: Swiss Tables, presented by Google in 2017, group slots in eights with a control word of 7-bit hash fragments so one comparison checks 8 slots. Rust’s HashMap is a port of SwissTable, and Go 1.24 rebuilt its built-in map on the design.

Python’s dict and set are resizable hash tables, chosen over B-trees for faster lookups. Java has HashMap and HashSet, C++ std::unordered_map, Rust HashMap and HashSet, and Go its built-in map. None keeps keys sorted (Java’s docs say HashMap makes no guarantees about order), so for ranges or “next key after k” use a search tree.