Hash tables are widely used in computer science.

A hash table stores and retrieves data in constant average time, O(1), which is much faster than the linear scan an array or linked list would require.

Hash tables show up in many real-world systems:

This chapter covers:

A hash table is a data structure that stores information as key-value pairs.

The mechanism is:

Instead of scanning every entry, the hash table jumps directly to the index. Insertions, lookups, and deletions all run in O(1) time on average.

The internals of a hash table revolve around two ideas: the hash function and collision handling.

1. Hash Function

A hash function takes a key (a string like "apple", a number, or any hashable type) and converts it into an integer index within the bounds of the internal array.

For example:

A good hash function is fast and spreads keys evenly across the array.

2. Collision Handling

When two different keys map to the same index, it's called a collision. Collisions are unavoidable regardless of how good the hash function is, so every hash table needs a strategy to handle them.

There are two main approaches:

A key concept that determines how likely collisions are is called the Load Factor. It measures how full a hash table is.

This resizing keeps the hash table efficient, ensuring that operations like insertion, deletion, and lookup remain close to O(1) on average.

A hash table supports four core operations: insert, search, delete, and update.

1. Insert (Put a Key-Value Pair)

When you insert something, the key goes through the hash function to find its index. The value is then stored at that index in the internal array.

If another key already maps to that same index (that's a collision) the hash table uses its collision-handling strategy, like chaining or open addressing, to resolve it as we discussed earlier.

Time Complexity for insert is O(1) on average, but it can go up to O(n) in the worst case if multiple keys map to the same spot.

2. Search (Lookup by Key)

To search for a value, you hash the key and jump directly to the index where it should be.

If the key exists, you return its value immediately. If there's a collision chain, you walk through that list until you find the match.

Time Complexity for search is O(1) on average, but O(n) in the worst case if all keys collide.

3. Delete (Remove a Key-Value Pair)

Deleting works in a similar way: first hash the key to locate its index, then remove the entry.

Time Complexity for delete is O(1) on average and O(n) in worst case.

4. Update

Updating is insertion with an existing key. If the key already exists, the new value overwrites the old one.

Choosing a good hash function is what determines how efficient a hash table is in practice.

In chaining, each bucket holds a linked list (or another structure) of entries that share the same index. Collisions extend the list at that bucket.

A lookup hashes the key, jumps to that bucket, and scans the chain at that bucket. When chains stay short, the scan is effectively constant time. When one chain grows long, lookups against that bucket slow down proportionally.

The worst case is when every key hashes to the same bucket. Lookups then become O(n) because the chain holds every entry in the table.

In open addressing, every entry lives in the bucket array itself. When a collision happens, the new entry walks forward through the table, following a probe sequence, until it finds an empty slot.

There is no extra memory for pointers, and the entire table sits in one contiguous array. The cost is that every probe has to walk forward until it finds either the target key or an empty slot, and the walk lengthens as the table fills up.

The probe sequence is what decides which slot to try next after a collision. Three sequences dominate in practice.

After a collision at index h, try h + 1, then h + 2, then h + 3, wrapping around the array.

Linear probing is simple to implement and cache-friendly because consecutive probes touch consecutive memory locations.

The downside is primary clustering. Long runs of occupied slots form, and any key whose hash falls anywhere inside the run has to walk the whole run.

After a collision at index h, try h + 1², then h + 2², then h + 3², then h + 4², and so on.

Quadratic probing breaks up primary clusters because consecutive probes spread out further with each step.

The remaining problem is secondary clustering: any two keys with the same initial hash follow the exact same probe sequence. Two keys that collide at index 5 will both try 6, 9, 14, 21, ..., so they keep colliding all the way down the sequence.

For quadratic probing to be guaranteed to find an empty slot, the table size has to be a prime number and the load factor has to stay below 0.5. (Probes of the form (h + i²) mod N visit only (N+1)/2 distinct slots, which is enough to find an empty one when the table is less than half full.)

After a collision at index h, jump by a stride determined by a second hash function h₂(key).

The stride now depends on the key itself. Two different keys with the same initial hash use different strides, which eliminates both primary and secondary clustering.

The cost is the extra computation for h₂, and the requirement that h₂(key) is never zero and is coprime with N (so that the probe sequence eventually covers every slot).

Most production-grade open-addressed hash tables use double hashing or a closely related variant such as Robin Hood hashing.

The load factor α measures how full the table is:

It is the single most important tuning knob for a hash table. A small α means few collisions but wasted memory. A large α means tight memory use but more collisions and slower operations.

Typical Thresholds

Different implementations resize at different points, depending on whether they use chaining or open addressing.

Open-addressed tables resize earlier because probe sequences grow rapidly as the table fills. Chained tables can tolerate higher load factors because longer chains degrade lookups linearly rather than catastrophically.

Rehashing

When the load factor crosses the threshold, the table rehashes itself:

Recomputation is required because the bucket index depends on the table size (the mod N step). An entry that lived at index 5 in a 16-bucket table might live at index 21 in a 32-bucket table.

A single rehash costs O(n) time. But because the table size doubles each time, rehashes happen rarely enough that the cost amortizes to O(1) per insert across many inserts. This is the same amortized-doubling pattern that dynamic arrays use to support O(1) append.

Java HashMap also has a secondary optimization: when a single bucket's chain reaches 8 entries and the table is large enough, that bucket is converted from a linked list to a balanced tree (a red-black tree), so worst-case bucket lookups drop from O(k) to O(log k).

The two collision strategies covered earlier lead to two different implementations. Both watch the load factor and double the table's capacity when it gets too full, but they store entries differently and handle probing and deletion in their own way.

With chaining, each slot holds a list of entries that share an index, and a collision appends to that list. A minimal hash map with chaining and automatic resizing looks like this:

Open addressing takes a different route. Instead of a list per slot, every entry lives directly in the table array. When the target slot is already taken, the table probes forward one slot at a time until it finds a free spot. Lookups follow the same probe sequence, stopping at the matching key or at the first empty slot.

Deletion needs care. If a removed entry left behind an empty slot, it would cut a probe chain in half and make later keys unreachable. To avoid that, removal marks the slot with a tombstone (a deleted flag) instead of clearing it. Probing walks past tombstones, while insertion is allowed to reuse them. Because every entry competes for the same array, open-addressed tables resize at a lower load factor (here 0.5) to keep probe chains short.

This is a teaching implementation. Production hash tables add many refinements: stronger hash mixing to spread out poor hashCode() results, tree-based buckets for long chains, tombstones for deletion in open-addressed tables, and concurrent-access protections for multi-threaded use.

In most real code you'll use a language's built-in hash table rather than rolling your own. The implementations below all expose the standard put / get / remove / contains operations in amortized O(1), with the same worst-case caveats (poor hash distribution, adversarial keys, or extreme load factors can degrade to O(n)).

For interview problems, the built-in is almost always the right starting point. Hand-rolled hash tables come up only when the problem explicitly forbids them or asks you to demonstrate how collision handling works.

Hash tables, arrays, and BSTs each represent a different point on the time-vs-ordering trade-off. The choice depends on what the workload needs.

Hash tables win for direct lookups, inserts, and deletes by key. They lose when the workload involves ordered access: minimum, maximum, predecessor, successor, range queries, or sorted iteration. For those workloads, use a balanced BST.

Arrays remain useful when keys are small non-negative integers and can be used directly as indices. That direct-indexing case is essentially a hash table where the hash function is the identity, with zero collisions and zero overhead.