Hash Tables Explained: How Dictionaries Really Work

Quick Answer

A hash table stores key-value pairs by running each key through a hash function that converts it into an array index, so lookups jump straight to the right slot instead of searching. That gives O(1) average time for insert, lookup and delete. When two keys land on the same slot it is called a collision, handled by chaining or open addressing. The worst case is O(n) if everything collides, and the structure resizes itself when it gets too full to keep collisions rare.

The Problem It Solves

Suppose you have a million user records and want the one with email riya@example.com. Scanning the list means up to a million comparisons — O(n). Sorting first and binary searching brings it down to about twenty — O(log n). A hash table finds it in roughly one step, regardless of size.

The trick is to stop searching altogether and calculate the location instead. A hash function takes the key and produces a number. That number, reduced to the size of the underlying array, is the index where the value lives.

hash("riya@example.com")  →  8834721904
8834721904 % 16          →  0            <- bucket index

buckets:
  0: [("riya@example.com", <record>)]
  1: []
  2: [("amit@example.com", <record>)]
  ...

To look the key up again, you run the same calculation and go straight to bucket 0. No scanning. This is why dict[key] in Python, map.get(key) in Java and obj[key] in JavaScript all feel instant no matter how much data they hold.

What Makes a Good Hash Function

Three properties matter, and the third is the one people forget.

Deterministic. The same key must always produce the same number. If it did not, you could never find what you stored.

Fast. The hash is computed on every operation. A slow hash function would destroy the benefit of skipping the search.

Uniform. Keys should spread evenly across the buckets. This is what keeps lookups near O(1). A hash function that sent every key to bucket 3 would technically work — and would turn the whole structure back into a linear scan.

This is also why keys must be immutable. If you use a mutable object as a key and then change it, its hash changes, and the table will look in the wrong bucket for something it stored elsewhere. The value is still in there and is now unreachable. Python prevents this by refusing to hash a list at all:

d = {}
d[[1, 2]] = "x"       # TypeError: unhashable type: 'list'
d[(1, 2)] = "x"       # fine — tuples are immutable

Java does not stop you, which is why mutating an object after using it as a HashMap key is a classic source of bugs that look impossible.

Collisions and How They Are Handled

Two different keys will eventually hash to the same bucket. This is unavoidable — there are infinitely many possible keys and only so many buckets. It is called a collision, and how a hash table handles it is most of its implementation.

Chaining is the common approach: each bucket holds a small list, and colliding entries are appended. Lookup finds the bucket, then walks its short list comparing keys. As long as the lists stay short, this is effectively O(1).

bucket 5: [("cat", 1)] → [("tac", 9)]      two keys, same bucket

lookup("tac"): hash → bucket 5, then compare keys in the chain

Open addressing stores everything in the array itself. On a collision it probes for the next free slot by a fixed rule. It avoids the memory overhead of chains and is friendlier to CPU caches, but deletion becomes fiddly — you cannot simply empty a slot, because that would break the probe chain for other keys.

Note what a lookup actually does: it finds the bucket by hash, then compares the actual keys. The hash narrows the search; equality confirms the match. This is why in Java, overriding equals() without also overriding hashCode() breaks HashMap so badly — two equal objects hash to different buckets and the map never finds the one you stored.

Load Factor and Resizing

Performance depends on the buckets not getting crowded. The load factor is the number of stored entries divided by the number of buckets. At 0.75 — a common threshold — three quarters of the slots are used, and chains are starting to grow.

When the load factor crosses the threshold, the table resizes: it allocates a larger array, usually double, and rehashes every existing key into the new bucket count. That is an O(n) operation.

This has two practical consequences. First, a single insert can occasionally be far slower than the rest — the one that triggers the resize. Averaged across all inserts the cost stays O(1), which is what amortised O(1) means. Second, if you know roughly how many items you will store, pre-sizing the structure avoids repeated resizes.

It also explains something that puzzles beginners: dictionary iteration order can change when the table resizes, because entries land in different buckets. Python guarantees insertion order since 3.7 as a language feature, but that is a promise made on top of the hash table, not a property of hashing itself.

Why O(1) Is Average, Not Guaranteed

Interviewers like this question because the honest answer shows you understand the mechanism rather than the headline.

Hash table operations are O(1) on average and O(n) in the worst case. The worst case is every key colliding into one bucket, which collapses the structure into a single list that must be scanned.

With a decent hash function and random data this effectively never happens. But it can be caused: if an attacker knows your hash function, they can craft thousands of keys that all collide, turning every request into a linear scan. That is a real denial-of-service technique, and it is why modern languages use randomised hash seeds per process.

Java's HashMap adds another mitigation worth knowing: once a bucket's chain grows past a threshold, it converts that chain into a balanced tree, improving the worst case for that bucket from O(n) to O(log n).

So in an interview, say O(1) average, O(n) worst case, and mention that a good hash function and resizing are what keep the average true in practice.

Frequently Asked Questions