Hash Tables Under the Hood: Collisions, Resizing, and O(1)

You use hash tables every day. But do you know what actually happens when two keys collide?

Many of the data structures you rely on every day are built on hash tables or similar sublinear lookup structures: database indexes, caches, Sets, and Map implementations like V8's. And yet most developers never stop to think about what's happening under the hood. That's usually fine — until a Map mysteriously slows down with 100k entries, or a cache starts degrading, and you have no mental model to fall back on. This article walks through how hash tables actually work, from the hash function through collisions and resizing, so you can reason about performance when it matters.

What is a hash table?

A hash table stores key-value pairs. It uses a hash function to convert each key into a number (an index), then stores the value at that index in an underlying array.

key: "email" → hash("email") = 4
→ store "user@test.com" at array[4]

Lookup is O(1) — constant time. You don't scan every element to find what you're looking for. You hash the key, jump straight to the index, and you're done. This direct addressing is why hash tables are the backbone of fast lookups across virtually every runtime and database engine in use today.

The hash function and the bucket array

The hash function is the heart of the whole structure. A good hash function does three things: it distributes keys uniformly so there's no clustering around particular indices, it's deterministic so the same key always produces the same hash, and it's fast to compute so the hashing step itself doesn't become a bottleneck.

Engines like V8 back JavaScript's Map with a hash table. When you call map.get("userId"), the engine hashes "userId", finds the corresponding bucket or slot, and returns the value. The underlying array — often called the bucket array — starts small and grows as you add more entries. The ratio of stored entries to the array's size is called the load factor, and it's the number that governs when the table decides to resize itself.

Collisions — when two keys hash to the same index

This is where it gets interesting. Two different keys can produce the same hash, or at least map to the same array index after the hash is reduced to fit the array size. So what happens when that slot is already taken?

There are two main strategies, and production hash tables split between them.

Chaining gives each bucket a linked list. When keys collide, they go into the same list, and a lookup walks that list to find the right key. The downside is that if many keys collide into the same bucket, lookup degrades toward O(n) for that bucket.

Open addressing keeps everything in the array itself. If the target bucket is already taken, the table probes for the next available slot using a strategy like linear probing (check the next slot), quadratic probing (check slots at increasing quadratic intervals), or double hashing (use a second hash function to determine the probe step).

// Chaining example
array[4] → ["email" → "user@test.com"] → ["name" → "Mesh"]

The major runtimes chose different sides here. Java's HashMap uses chaining, and it goes a step further by converting long chains into balanced trees so a worst-case bucket degrades to O(log n) rather than O(n). CPython's dict and V8's Map both use open addressing, which tends to be more cache-friendly and avoids the pointer-chasing overhead of linked lists.

Resizing — when the hash table grows up

When the load factor exceeds a threshold — typically around 0.75 — the hash table resizes itself to keep lookups fast. The process has three steps: allocate a new array, usually twice the current size; rehash every existing key into its new position in that array; and update the internal reference so subsequent operations use the new table.

That rehashing step is O(n) — every key has to be hashed again against the new array size. It's expensive. But because it happens infrequently relative to the number of insertions, the amortized cost of an insert is still O(1). Any single insert might trigger a resize and be slow, but averaged across many inserts, each one is effectively constant time.

This is why Map.set() is fast most of the time but occasionally causes a performance spike if you're inserting thousands of entries in a tight loop. One of those inserts hits the load-factor threshold and triggers a full rehash, and that's the one you'd notice in a profiler.

Why this matters in production

Understanding what's under the hood pays off in concrete, everyday ways. O(1) lookup is the reason your database can find a row by ID in milliseconds rather than scanning the whole table. Understanding collisions helps you debug questions like "why is my Map slow with 100k entries?" — the answer is often a pathological key set or a hash function that's clustering. Knowing about resizing helps you pre-size collections when you already know roughly how many entries you'll store, avoiding repeated rehashing. And hash table behavior is the foundation of caching, indexing, and deduplication, so the mental model transfers everywhere.

If your language or library lets you set an initial capacity, pre-size it:

// Pre-allocate to avoid repeated resizing in Java
Map<String, String> map = new HashMap<>(expectedSize);

JavaScript's Map doesn't expose a capacity constructor, but building a Map from an iterable rather than calling set() thousands of times in a tight loop still helps engines optimize the growth pattern. The fewer times the engine has to stop and rehash, the smoother your insertions will be.

Hash tables are one of those topics that seems like textbook trivia until the day a production bottleneck traces back to one. Having the model in your head — hash function, collisions, load factor, amortized resizing — means you can go straight from "this is slow" to "here's why, and here's the fix."

Need help with this?

Get in touch — I take on a few new clients each month.