How a hash table turns a key into an answer in O(1).

A hash table is an array of buckets indexed by a hash function applied to the key. Hans Peter Luhn proposed the idea at IBM in 1953. Today they back the map / dict / HashMap in most languages, many database indexes, caches and router flow tables. The two collision strategies are chaining (linked lists per bucket) and open addressing (probe to the next bucket).

The idea is simple. Take a key (a string, a number, anything hashable) and apply a hash function to turn it into an integer. Take that modulo the table size to get the index where the key's value lives. A lookup repeats the same hash and fetches from the same index in O(1), with no search or traversal.

The hash function maps an unbounded keyspace onto a bounded number of slots, so two keys can hash to the same slot. That is a collision, and the strategy for resolving collisions largely defines how a given table behaves.

Below is an 11-slot hash table. Type a key to see where it lands. Switch strategies and reseed to get the same keys in different layouts. Open addressing keeps everything in the slots, while chaining grows lists at busy slots.

When two keys collide, the table can either find another empty slot in the same array (open addressing) or turn the slot into a list and append (chaining). Both work, with different operational trade-offs.

The load factor is occupied slots divided by total slots. Past a threshold (typically 0.75 for chaining, 0.5 for open addressing), performance starts to fall off. The fix is to allocate a bigger array, walk every key, rehash with the new size, copy.

Rehashing is O(n) and pauses the table. Java doubles the table each time it crosses the threshold, so resizes are rare and amortise to O(1) per insert. Some implementations rehash incrementally, moving a few keys per operation instead of all at once, to keep p99 latency down. Redis does this for its dictionary.

A good hash function spreads inputs uniformly across the output range, changes a lot when one bit of input changes (avalanche), and runs fast. Modern non-cryptographic hashes (xxHash, MurmurHash, CityHash) do all three in a few ns per key.

Cryptographic hashes such as SHA-256 are too slow for hash tables and the extra bit quality isn't needed. Java's String.hashCode() is simple and can cluster on real-world strings, which is why HashMap mixes the high bits into the low bits before indexing.

If your hash function is deterministic and the attacker knows the algorithm, they can craft keys that all collide. A web server putting JSON keys into a hash map is suddenly doing O(n²) work per request. This is HashDoS, and it affected major frameworks until they fixed it.

The usual fix is a per-process random seed, so every server starts with a different hash function. Python, Ruby, Rust and Go do this. The attacker can't see the seed, so precomputed colliding keys no longer work. Java instead limits the damage by converting long chains to trees.

Most languages implement their map / dict / object as a hash table. Database query optimizers use them for joins. Caches use them for keys. JVM string interning uses one. Operating system kernels use them for several internal tables.

Java HashMap

Chained buckets. Since Java 8, a chain longer than 8 entries (in a table of at least 64 buckets) converts to a red-black tree for O(log n) worst case. Initial capacity 16, load factor 0.75.

Python dict

Open addressing with perturbation. Keys keep insertion order (an implementation detail in CPython 3.6, guaranteed since 3.7), implemented with two arrays: a sparse index table and a dense entries list. Load factor caps at ~2/3.

Go map

Buckets of 8 entries with overflow buckets in the classic implementation, with a Swiss-table design since Go 1.24. Resizing grows capacity and rehashes incrementally during writes.

Rust HashMap

SwissTable algorithm (Google, 2017): single array of 16-byte groups, SIMD lookup of 16 metadata bytes at once. Typically faster than chained tables. It has been the default since Rust 1.36.

C++ std::unordered_map

Effectively chained, because the standard requires reference stability, which open addressing breaks. Performance lags SwissTable variants (Abseil's flat_hash_map, F14 from Folly) by ~2× in benchmarks.

Postgres hash index

On-disk hash index. Optimised for equality lookup but rarely used in practice: B-tree handles equality fast enough plus range, so most workloads pick B-tree by default.

SwissTable. Google's 2017 CppCon talk introduced SwissTable, which uses SIMD to compare 16 metadata bytes at once. Rust, Abseil (Google), F14 (Meta) and recent Go versions use variants. The Java and Python standard-library hash maps do not use it.

The original (2003). Crosby and Wallach showed that an attacker who can choose hash table keys (e.g., via HTTP form fields parsed into a server-side hash) can craft inputs that all collide into the same bucket. Insertion becomes O(n²); a 1,000-key form takes seconds to parse. The problem went largely unaddressed for years.

2011: the sequel. Klink and Wälde at the 28C3 conference demonstrated practical exploits against PHP, Java, Python, Ruby and ASP.NET. A few KB of carefully crafted HTTP form data could pin a server's CPU at 100% for minutes. Languages responded with randomised hashing, and SipHash (Aumasson and Bernstein, 2012) became a common choice. It takes a per-process key, so attackers can't predict the input-to-bucket mapping.

Today. Most languages randomise the hash used by their built-in tables. Python has used SipHash since 3.4 (2014), Rust's default hasher is SipHash, and Go uses a randomised AES-based hash. Java does not randomise, and relies on tree buckets to cap the worst case. The practical rule is to seed hashes that process untrusted input.