Hash Tables: From Keys to Buckets

A hash table stores key-value pairs for fast lookup by key. It turns each key into a number, uses part of that number to pick a slot, and stores the pair there.

Lookup then takes a constant number of steps because the position was computed, not searched for. No scan walks the table. No tree gets descended.

Two facts make that promise conditional. Different keys can map to the same slot. The table also fills up over time, and full tables slow down. Everything interesting lives in how implementations handle those two facts.

A hash function picks the slot, equality proves the key

A hash function turns a key into a large integer. The table maps that integer to a slot, called a bucket. With a power-of-two capacity the mapping is one mask operation:

index = hash(key) AND (capacity - 1)      -- capacity 1024 keeps bits 0..9

The mask explains why capacities are powers of two. It also explains one failure mode. A hash that varies only in high bits sends every key to one bucket under a mask. Good hash functions spread differences into low bits.

Equal hash values never prove equal keys. Two distinct keys can share a slot, so every lookup must compare the stored key with the requested key. Skipping that check returns wrong values silently.

The contract runs both directions. Equal keys must hash equally. A key's hash must not change while the entry sits in the table. Mutating a field that feeds the hash makes the entry unfindable: it waits in the old bucket while lookups compute the new one. Nearly every "my map loses keys" report traces to this bug.

A minimal bucket table looks the same in every language:

#include <string>
#include <vector>
// A tiny hash table: buckets of key-value pairs with chaining.
// Real tables resize and use stronger hashes; the shape is identical.
struct Entry { std::string key; int value; }; // one stored pair
// Pick a bucket by masking a small hash of the key.
int bucketOf(const std::string& key, int capacity) {
    unsigned h = 0; // running hash value
    for (char c : key) h = h * 31 + (unsigned)c; // spread each character in
    return (int)(h & (unsigned)(capacity - 1)); // keep only the low bits
}
// Insert or overwrite key inside its bucket, comparing full keys.
void tinyPut(std::vector<std::vector<Entry>>& t, const std::string& k, int v) {
    auto& bucket = t[bucketOf(k, (int)t.size())]; // home bucket for k
    for (auto& e : bucket) if (e.key == k) { e.value = v; return; } // key exists
    bucket.push_back({k, v}); // new key: append to the bucket chain
}

All three versions share the shape. Hash the key. Mask to a bucket. Compare full keys inside the bucket. Production tables add resizing and stronger hashes around this core.

Collisions resolve through chains or probes

A collision places two keys in one bucket. Two families of policies handle it.

Separate chaining stores a small list per bucket. New entries append to the list. Lookups walk the list comparing keys. Java 8 and later convert a long bin into a balanced tree once it holds 8 entries, capping the walk.

Open addressing keeps every entry in the slot array itself. A collision walks to another slot by a probing rule. Linear probing checks consecutive slots. Quadratic probing jumps by growing steps. Double hashing derives the step from a second hash.

Deletion in open addressing needs a tombstone. A tombstone is a marker that says "an entry lived here". Removing an entry by emptying its slot would cut probe chains in half. Later lookups would stop early and report present keys as missing.

capacity 8, load factor 0.75 -> resize at 6 entries
 
insert "amy" -> hash AND 7 = 5 -> slot 5 holds "eve" -> probe 6 -> placed

Open addressing runs faster while the table stays under about 70 percent full. Entries sit together with no per-node allocation. Past that point clusters form: long runs of occupied slots that every nearby insert must walk.

The load factor triggers growth before lookups degrade

The load factor divides entry count by capacity. It measures fullness. Implementations cap it and grow the table when the cap breaks.

Common caps differ by design. Java HashMap and C# Dictionary use 0.75. Go grows near 0.8 (6.5 entries per 8-slot bucket). Linear probing tables often stop at 0.5 because clusters grow fast.

Growth means rehashing: allocate a table twice the size and reinsert every entry. New capacity changes the mask, so nearly every key lands in a different slot. Old positions cannot transfer directly.

Rehashing costs O(n) inside one operation. A map with 10 million entries doubles to 20 million slots and reinserts everything at once. Amortized over many inserts the cost stays O(1) each. The single growing insert still stalls, which is exactly the spike a p99 latency graph shows.

Size your initial capacity when you know the load. Inserting a million known entries into a default 16-slot table rehashes about 16 times. Reserving a million slots up front skips all of them.

Expected constant time rests on the hash quality

Under a good hash and ordinary keys, lookups touch one or two entries. That is expected O(1): constant on average over the hash function, not guaranteed per call.

Two failures restore linear behavior. Bad distribution packs keys into few buckets, turning the table into a linked list. Adversarial keys do the same deliberately.

The adversarial case once hurt real servers. In 2011, attackers sent colliding parameter names to web frameworks, forcing every request into one bucket and pinning CPUs at 100 percent. The industry answer was seeded hashing: mix a random per-process seed into the function. Rust, Go, and Ruby hash with seeds such as SipHash so attackers cannot precompute collisions.

Neither failure appears in small unit tests. Three keys like "key1" and "key2" never stress distribution. Load tests with realistic key shapes catch what unit tests miss.

Where hash tables run and what to read next

Hash tables back object properties, caches, indexes, and symbol tables. Compilers resolve names through them. Routers match flows through them. Databases probe hash joins with them.

Reach for one when lookups dominate and order never matters. Reach for a tree the moment someone asks for ranges or sorted output. The two structures split the key-value world between them.

Watch a hash-table lookup execute and follow the lookup flow diagram. Then drill growth behavior in the hash-table flow. The LRU cache practice combines a hash map with a list into a real eviction policy.