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: every language's map / dict / HashMap, every database index, every cache, every router's flow table. The two collision strategies are chaining (linked lists per bucket) and open addressing (probe to the next bucket).

The whole hash table is built on one trick. You have a key — a string, a number, anything hashable. You apply a hash function that turns it into an integer. You modulo by the table size. The result is the index where that key's value lives. Look-up: same hash, same index, fetch in O(1). No search, no traversal — just arithmetic.

The catch is that the hash function maps an unbounded keyspace to a bounded number of slots. Two keys can hash to the same slot — a collision. The table's strategy for resolving collisions is what defines its character.

Below: an 11-slot hash table. Type a key and watch where it lands. Switch strategies and reseed — same keys, different layouts. Open addressing slots stay flat; chaining grows lists at busy slots.

When two keys collide, you have two options. Either you find another empty slot in the same array (open addressing) or you turn the slot into a list and append (chaining). Both work. They have very different operational shapes.

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. Production hash tables amortise the cost — Java grows by 2× every threshold breach, so resizes happen rarely and amortise to O(1) per insert. Some implementations incrementally rehash — moving a few keys per operation rather than all at once — to keep p99 latency tight, the same trick Redis uses for its dictionary resize.

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

Don't use cryptographic hashes (SHA-256) for hash tables — they're overkill on speed and unnecessary on bit quality. Don't use the older Java String.hashCode() as your only line of defence — it's known to cluster on real-world strings; the JDK now post-mixes it specifically because of this.

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 running O(n²) per request. This is HashDoS, and it took down major frameworks until they fixed it.

The fix is per-process random seeds — every server starts with a different hash function. Python, Ruby, Java, Rust, and Go all do this. The seed is invisible to the attacker, so collision-engineering attacks fail.

Every language's map / dict / object is a hash table. Database query optimizers use them for joins. Caches use them for keys. JVM string interning uses one. The kernel's file-descriptor table is one. You almost certainly used a dozen hash table operations to load this page.

Java HashMap

Open addressing turned to chained buckets in 8.0; if a chain exceeds 8 entries it converts to a tree (red-black) for O(log n) worst case. Initial capacity 16, load factor 0.75.

Python dict

Open addressing with perturbation. Since 3.6 (CPython 3.6+, guaranteed since 3.7) keys keep insertion order — implemented via two arrays (one ordered hash table, one ordered key list). Load factor caps at ~2/3.

Go map

Open addressing with bucket-of-8 cells (each bucket holds up to 8 entries). Resize doubles capacity, incremental rehashing during writes. Source: runtime/map.go.

Rust HashMap

SwissTable algorithm (Google, 2017): single array of 16-byte groups, SIMD lookup of 16 metadata bytes at once. Faster than chained tables by ~30%. Default since Rust 1.36.

C++ std::unordered_map

Mandated chained — the spec 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.

The SwissTable revolution. Google's 2017 CppCon talk on SwissTable changed the field. Modern hash tables use SIMD to compare 16 metadata bytes at once, getting ~3x throughput on modern x86. Rust, Abseil (Google), and F14 (Meta) all implement variants. Java and Python's stdlib hashmaps haven't adopted SwissTable yet but conversations are active.

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. Quiet vulnerability for years.

2011 — the sequel. Klink and Wäldecke at the 28C3 conference demonstrated practical exploits against PHP, Java, Python, Ruby, ASP.NET. A few KB of carefully crafted HTTP form data could pin a server's CPU at 100% for minutes. Most languages patched within days by adopting SipHash (Aumasson and Bernstein, 2012) — a randomised hash that takes a per-process key, making the input-to-bucket mapping unpredictable to attackers.

Today. Every modern language ships a randomised hash for hash tables. Python uses SipHash since 3.4 (2014); Rust uses SipHash; Go uses a randomised AES-based hash; Java's HashMap uses a hash with per-process randomisation since Java 8. The vulnerability is largely closed; the lesson — never use raw input as a hash without randomisation — is permanently in security-101 curricula.