Hash Tables Explained: How Maps and Sets Get O(1) Lookups

You’re signing up for something. You type a username — cricketfan_92 — and before your finger leaves the key, the box turns red: already taken. There are four hundred million accounts on that site. It didn’t read through them. It couldn’t have — reading four hundred million names would take longer than your coffee break, and it answered in a blink.

So how did it check one name against four hundred million in the time it takes a screen to refresh? That trick has a name. It’s a data structure called a hash table, and once you see how it works you’ll understand why map.get(key) and "is this in the set?" feel instant no matter how much you’ve stored. By the end of this article, you and I will have built one together — buckets, collisions, resizing, and all.

Let’s start nowhere near a computer

Picture the cloakroom at a busy theatre. Five hundred coats come in during the ten minutes before curtain, and every one of them has to come back to the right person at the end of the night — fast, because nobody wants to queue in the cold.

A hopeless attendant would pile every coat in one heap. To return yours, they’d dig through the whole pile. Five hundred coats, five hundred possible digs. That’s a list, and it’s the thing we’re trying to escape.

A good attendant does something cleverer. They have a rule that turns your name into a hook number — say, add up the letters and take the last two digits. "Meera" always comes out as hook 3. They hang your coat on hook 3 and hand you a tag. At the end of the night you say "Meera," they run the same rule, get 3 again, and walk straight to that one hook. No digging.

That rule — the thing that turns a name into a hook number — is the whole idea. In our world it’s called a hash function, and the hooks are buckets. Two properties make it work, and they’re worth saying out loud because everything later leans on them:

1. It’s deterministic. The same name always yields the same hook. If "Meera" hashed to 3 on the way in and 8 on the way out, you’d never see your coat again.
2. It scatters. A good rule spreads names across all the hooks evenly, so no single hook collects half the coats.

But you already feel the crack in the plan, don’t you? Names are unlimited; hooks are not. Sooner or later "Meera" and "Rahul" both hash to hook 3. Two coats, one hook. That’s a collision, and how the attendant handles it is the heart of this whole article — so hold that thought, we’ll come back and stare at it properly.

The same idea, everywhere in your day

Once you know the shape, you start seeing hash tables holding up your whole day. Your phone’s contacts jump to a name the instant you type it. A spell-checker decides a word is real by asking a set "is this in the dictionary?" — one hash, one answer. When a database promises a query is "indexed," a hash index is often what turns scan every row into jump to the row. A git commit names your snapshot by the hash of its contents, so the same content always lands at the same address. Caches, de-duplication, counting how many times each word appears in a file — all of it is turn a key into a slot, then look right there.

The pattern is so common that it’s the default answer to a huge class of interview problems: "make this faster." Nested loop scanning for a pair that sums to a target? Drop the values in a hash set and the inner loop vanishes. The trie beats a hash set only when the question is about prefixes; for plain "have I seen this exact key?", nothing beats a hash table.

What it actually looks like

Under the hood a hash table is almost embarrassingly simple: an array, plus a rule for turning a key into an index into that array. That’s it. The array slots are the buckets.

Follow one key through. You call key.hashCode() and get back some large, arbitrary integer — a fingerprint of the key. That number is way too big to be an array index (the array only has, say, 8 slots), so you fold it down into the array’s range, usually with modulo: index = hash % 8. Now you have a slot. To put, you drop the entry there. To get the same key later, you run the identical steps, land on the identical slot, and read it back.

Neither step looked at any other key. That independence is the entire payoff: the cost of a lookup doesn’t grow just because you stored more stuff. That’s what "average O(1)" means, and it’s why the username check didn’t care that there were four hundred million names.

Let’s build one, step by step

We’ll build a real, working map with separate chaining and resizing, in small pieces, and assemble the whole thing at the end. Standard library only, no magic.

Step 1: the buckets and the index

Every box in that last diagram is one slot in an array. And we need the rule that turns a key’s hash into a slot number. Here’s the version most people write first — and it has a bug that will crash you in production:

private int indexFor(int hash) {
    return hash % buckets.length;   // BUG: hash can be negative
}

Looks fine. It isn’t. A hash code is a signed 32-bit integer, so it’s often negative — and in this language, -1 % 8 is -1, not 7. Feed that back as an array index and you get an ArrayIndexOutOfBoundsException the first time an unlucky key walks in. The fix is to fold negatives back into range:

// floorMod keeps the index in range even when the hash is negative.
private int indexFor(int hash) {
    return Math.floorMod(hash, buckets.length);
}

There’s a second, subtler improvement. A weak hashCode() can leave all its variation in the high bits, so after % 8 everything clumps into a few low buckets. Real maps defend against this by stirring the bits down before folding:

// Stir the high bits down so a weak hashCode doesn't clump in low buckets.
private static int spread(Object key) {
    int h = key.hashCode();
    return h ^ (h >>> 16);
}

Step 2: collisions — the part everyone underestimates

Now, the collision we parked at the cloakroom. It is not a rare edge case you can wave away — it is guaranteed. You have unlimited possible keys and a finite number of buckets, so by the pigeonhole principle, once you store more keys than buckets, something must share. (There’s a famous version: in a room of just 23 people, two of them probably share a birthday. Buckets fill up far faster than your intuition expects.)

So what do we do when put("cat") and put("dog") both want bucket 2? The naive answer — one value per slot — quietly destroys data:

Look at the left panel. dog lands on bucket 2, overwrites cat, and now cat is simply gone — get("cat") returns nothing, even though you inserted it. A silent, data-losing bug.

The fix on the right is called separate chaining: each bucket doesn’t hold one entry, it holds a little linked list of entries. When dog collides with cat, it just joins the list. Nothing is lost. So each node in a bucket’s chain needs to carry its key, its value, and a pointer to the next node sharing that bucket:

private static final class Entry<K, V> {
    final K key;
    V value;
    final int hash;        // the spread hash, cached so we never recompute
    Entry<K, V> next;      // the next entry sharing this bucket
 
    Entry(K key, V value, int hash, Entry<K, V> next) {
        this.key = key;
        this.value = value;
        this.hash = hash;
        this.next = next;
    }
}

Inserting means: find the bucket, walk its chain looking for the key. If the key’s already there, overwrite its value (a map holds one value per key). If we reach the end without finding it, we’ve got a brand-new key, so link a fresh node onto the front of the chain:

public V put(K key, V value) {
    int hash = spread(key);
    int i = indexFor(hash);
    for (Entry<K, V> e = buckets[i]; e != null; e = e.next) {
        if (e.hash == hash && e.key.equals(key)) {
            V old = e.value;
            e.value = value;                 // key already here → overwrite
            return old;
        }
    }
    buckets[i] = new Entry<>(key, value, hash, buckets[i]);  // prepend
    size++;
    if (size > MAX_LOAD_FACTOR * buckets.length) {
        resize();
    }
    return null;
}

Notice the e.hash == hash && guard before the .equals(). Comparing two ints is nearly free, and full equals() can be expensive (imagine long strings), so we cheaply rule out most mismatches before paying for the real comparison. That’s why we cached the hash on every node.

Step 3: get and remove — walk the chain

Reading back is the same walk without the surgery: hash the key, go to its bucket, walk the chain, and return the value whose key matches.

public V get(K key) {
    int hash = spread(key);
    for (Entry<K, V> e = buckets[indexFor(hash)]; e != null; e = e.next) {
        if (e.hash == hash && e.key.equals(key)) {
            return e.value;
        }
    }
    return null;
}

Removing is the classic linked-list splice — but with one trap. If the node you’re deleting is the head of the chain, there’s no previous node to re-point; you have to move the bucket’s own reference forward instead. Miss that case and you either crash or leave a ghost entry behind:

public V remove(K key) {
    int hash = spread(key);
    int i = indexFor(hash);
    Entry<K, V> prev = null;
    for (Entry<K, V> e = buckets[i]; e != null; e = e.next) {
        if (e.hash == hash && e.key.equals(key)) {
            if (prev == null) {
                buckets[i] = e.next;         // it was the chain's head
            } else {
                prev.next = e.next;          // splice it out of the chain
            }
            size--;
            return e.value;
        }
        prev = e;
    }
    return null;
}

Everything so far assumed the chains stay short. If they don’t, get degrades from "look at one slot" to "walk a long list," and the whole promise falls apart. Keeping chains short is the job of the next step.

Step 4: load factor and resize — how it stays O(1)

The load factor is the one number that governs a hash table’s health: it’s entries ÷ buckets. At a load factor of 0.75, the table is three-quarters full, and the average chain is short — most buckets hold zero or one entry. Let it climb toward 5 or 10 and every chain is long; your O(1) map is now a pile of little linked lists, which is O(n).

So the table watches its own load factor and, when it crosses a threshold (0.75 is the classic choice), it resizes: allocate a bigger array — double is standard — and rehash every existing entry into it. This isn’t optional bookkeeping; it’s the mechanism that keeps chains short as you grow.

private void resize() {
    Entry<K, V>[] old = buckets;
    buckets = (Entry<K, V>[]) new Entry[old.length * 2];   // double the table
    for (Entry<K, V> head : old) {
        for (Entry<K, V> e = head; e != null; ) {
            Entry<K, V> next = e.next;       // save before we relink
            int i = indexFor(e.hash);        // re-place using the new width
            e.next = buckets[i];
            buckets[i] = e;
            e = next;
        }
    }
}

Two details in that loop are load-bearing. We save e.next before relinking, because we’re about to overwrite e.next and would otherwise lose the rest of the chain. And we recompute indexFor(e.hash) against the new length — the same hash folds to a different slot in a bigger table, which is precisely how the crowd spreads out.

Now, resizing sounds expensive — copying every entry is O(n)! So how do we still claim O(1)? The magic word is amortized. Because we double each time, resizes get rarer as the table grows: you resize at 6 entries, then 12, then 24, then 48. Each entry gets moved only a handful of times across the table’s entire life. Spread that rare, expensive O(n) copy across the many cheap O(1) inserts between resizes, and the average insert is still O(1). You pay a big bill occasionally, but the per-insert cost stays flat.

The other way to resolve a collision: open addressing

Separate chaining stores collided keys outside the array, in little lists. There’s a completely different philosophy called open addressing that refuses to ever leave the array: if your bucket is taken, you go looking for another empty slot right there in the table.

The simplest form is linear probing: bucket taken? Try the next one. Still taken? The next. Keep walking ((index + 1) % capacity) until you hit an empty slot, and drop your entry there.

To get, you replay the same walk: hash to the starting bucket, then step forward comparing keys until you either find yours or hit an empty slot (which means it was never inserted). No pointers, no separate list nodes — everything lives in one contiguous array, which is wonderful for the CPU cache. That cache-friendliness is why high-performance maps often prefer it.

But it has a nasty personality trait you can see in the diagram: primary clustering. Every collision grows a run of occupied slots, and runs tend to merge into longer runs, which catch even more keys — full regions snowball. Worse, deletion gets genuinely tricky. You can’t just empty a slot in the middle of a run, because that empty slot would tell a future get to stop early and miss keys that probed past it. Open-addressing maps mark deleted slots with a tombstone — "empty, but keep walking" — and periodically clean them up.

The practical upshot: open addressing lives or dies by keeping the table emptier than chaining does. Once it passes about a 0.7 load factor, those clusters make probes explode, so it resizes sooner and wastes more space. Chaining tolerates a fuller table and simpler deletes; open addressing wins on cache locality and memory-per-entry. Both are correct; they trade different things.

How fast is this, really?

Here’s the hash map against the two structures you’d otherwise reach for — a plain list you scan, and a balanced search tree (the TreeMap family). Call n the number of entries:

(The scanned list is O(n) on put too, because it has to walk the whole thing first just to check the key isn’t already there.)

Read the tree column before you crown the hash map. A balanced tree is never O(n) — its O(log n) is a rock-solid guarantee, not an average — and it keeps your keys sorted, which a hash map flatly cannot do. So if you need range queries ("all users with score between 50 and 80") or "give me the smallest key," a hash map is the wrong tool no matter how fast its point lookups are. The hash map’s superpower is unordered point access; the moment you need order, that superpower is gone. Choosing between them is choosing which question you’ll ask most.

The contract that makes buckets work: equals() and hashCode()

Everything above quietly assumed something you must never break. To find a key, the map hashes it to pick a bucket, then uses equals() to pick it out of the chain. So a key type has to answer two questions consistently, and they have to agree:

The rule, stated once and for all: if two objects are equal, they must return the same hash code. (The reverse isn’t required — two unequal objects are allowed to collide.) Break this and you get the bug on the right of that diagram: you put a key, it hashes to bucket 7; you later get an equal key, but its hash code is different, so the map goes looking in bucket 3 — a bucket it will search perfectly and find nothing in. The entry is right there in the table. The lookup just refuses to look where it lives.

This is why every custom key type must override hashCode() and equals() together — override one and forget the other and you’ve broken the contract. But the sneakiest version of this bug isn’t a missing override. It’s a mutable key:

static final class MutablePoint {
    int x, y;
    MutablePoint(int x, int y) { this.x = x; this.y = y; }
    @Override public int hashCode() { return Objects.hash(x, y); }
    @Override public boolean equals(Object o) {
        return o instanceof MutablePoint p && p.x == x && p.y == y;
    }
}

This type does everything right — until you mutate a key after using it:

MutablePoint p = new MutablePoint(1, 2);
map.put(p, "here");
map.get(p);        // "here"  — hashes to, say, bucket 4
 
p.x = 99;          // we changed a field hashCode() depends on
map.get(p);        // null!   — now hashes to bucket 9, where nothing lives

The entry never moved; it’s still sitting in bucket 4. But p now hashes to bucket 9, so the map can’t find its own entry. This is why the golden rule for keys is use immutable types — String, boxed numbers, records, frozen value objects. A key whose hash can change out from under the table is a key that can get lost inside it.

When O(1) becomes O(n): adversarial keys

Here’s the part that turns a data structure into a security lesson — and it’s the most interesting corner of the whole topic.

Every "average O(1)" we’ve written hides an assumption: that keys scatter across buckets. But look back at the worst case in that trade-off table. What if they don’t scatter? What if every single key hashes to the same bucket?

Then your beautiful O(1) hash map is one gigantic linked list wearing a costume. Every get walks the whole chain — O(n). Resizing doesn’t help, because doubling the array doesn’t separate keys that all hash to the same value; they just re-collide in the bigger table. You’ve built a list and paid for a hash map.

"But keys don’t naturally all collide," you might say — and you’d be right. The danger is when they’re chosen to collide on purpose. This is a real, named attack: hash flooding (algorithmic complexity denial-of-service). An attacker who knows your hash function crafts thousands of distinct keys that all hash to the same bucket, then sends them as, say, HTTP form fields or JSON keys — which your server dutifully drops into a hash map. Insertion goes quadratic, one request pins a CPU core, and a few cheap requests take the service down. In the early 2010s this flattened web frameworks across nearly every language at once, because they all shared the same predictable string-hashing behavior.

So how do real hash tables defend the O(1) they promise? Two moves, and they’re worth knowing cold:

1. Treeify the bucket. Since version 8, this language’s HashMap watches individual chains, and when one grows past a threshold (8 nodes), it converts that bucket from a linked list into a balanced tree. The bucket’s lookups go from O(n) to O(log n). An attacker who forces a million collisions now faces a red-black tree, not a million-node list — the O(n) worst case is capped at O(log n). (This needs the keys to be comparable, which strings and numbers are.)
2. Randomize the hash. Many runtimes seed their string hashing with a random secret chosen at startup (using keyed hashes like SipHash), so an attacker can’t predict which keys will collide — they’d have to guess a per-process secret. The scatter assumption becomes something an outsider can’t reverse-engineer.

That’s the deep idea worth carrying out of this article: the hash table’s O(1) is a statistical promise, not a law of physics, and it holds only as long as your keys behave. A balanced tree’s O(log n) is a guarantee — slower on average, but it never betrays you, which is exactly why it’s the fallback both defenses lean on. Understanding when the average breaks — bad hash functions, mutable keys, or an adversary feeding you collisions — is what separates someone who uses a hash map from someone who can reason about one.

The complete implementation

Everything we built, assembled — a working hash map with separate chaining and resizing:

package dev.fiveyear.hashtable;
 
public final class ChainedHashMap<K, V> {
 
    private static final class Entry<K, V> {
        final K key;
        V value;
        final int hash;        // the spread hash, cached so we never recompute
        Entry<K, V> next;      // the next entry sharing this bucket
 
        Entry(K key, V value, int hash, Entry<K, V> next) {
            this.key = key;
            this.value = value;
            this.hash = hash;
            this.next = next;
        }
    }
 
    private static final double MAX_LOAD_FACTOR = 0.75;
 
    private Entry<K, V>[] buckets;
    private int size;
 
    @SuppressWarnings("unchecked")
    public ChainedHashMap() {
        buckets = (Entry<K, V>[]) new Entry[8];
    }
 
    // Stir the high bits down so a weak hashCode doesn't clump in low buckets.
    private static int spread(Object key) {
        int h = key.hashCode();
        return h ^ (h >>> 16);
    }
 
    // floorMod keeps the index in range even when the hash is negative.
    private int indexFor(int hash) {
        return Math.floorMod(hash, buckets.length);
    }
 
    /** Inserts or overwrites; returns the previous value, or null. O(1) average. */
    public V put(K key, V value) {
        int hash = spread(key);
        int i = indexFor(hash);
        for (Entry<K, V> e = buckets[i]; e != null; e = e.next) {
            if (e.hash == hash && e.key.equals(key)) {
                V old = e.value;
                e.value = value;                 // key already here → overwrite
                return old;
            }
        }
        buckets[i] = new Entry<>(key, value, hash, buckets[i]);  // prepend
        size++;
        if (size > MAX_LOAD_FACTOR * buckets.length) {
            resize();
        }
        return null;
    }
 
    /** Returns the value for the key, or null if absent. O(1) average. */
    public V get(K key) {
        int hash = spread(key);
        for (Entry<K, V> e = buckets[indexFor(hash)]; e != null; e = e.next) {
            if (e.hash == hash && e.key.equals(key)) {
                return e.value;
            }
        }
        return null;
    }
 
    /** True if the key is present. O(1) average. */
    public boolean containsKey(K key) {
        int hash = spread(key);
        for (Entry<K, V> e = buckets[indexFor(hash)]; e != null; e = e.next) {
            if (e.hash == hash && e.key.equals(key)) {
                return true;
            }
        }
        return false;
    }
 
    /** Removes the key; returns the old value, or null. O(1) average. */
    public V remove(K key) {
        int hash = spread(key);
        int i = indexFor(hash);
        Entry<K, V> prev = null;
        for (Entry<K, V> e = buckets[i]; e != null; e = e.next) {
            if (e.hash == hash && e.key.equals(key)) {
                if (prev == null) {
                    buckets[i] = e.next;         // it was the chain's head
                } else {
                    prev.next = e.next;          // splice it out of the chain
                }
                size--;
                return e.value;
            }
            prev = e;
        }
        return null;
    }
 
    public int size() {
        return size;
    }
 
    /** A peek at the table width — for teaching; a real map hides this. */
    public int capacity() {
        return buckets.length;
    }
 
    @SuppressWarnings("unchecked")
    private void resize() {
        Entry<K, V>[] old = buckets;
        buckets = (Entry<K, V>[]) new Entry[old.length * 2];   // double the table
        for (Entry<K, V> head : old) {
            for (Entry<K, V> e = head; e != null; ) {
                Entry<K, V> next = e.next;       // save before we relink
                int i = indexFor(e.hash);        // re-place using the new width
                e.next = buckets[i];
                buckets[i] = e;
                e = next;
            }
        }
    }
}

And here it is doing everything we drew — the comments are the exact outputs:

ChainedHashMap<String, Integer> ages = new ChainedHashMap<>();
ages.put("alice", 30);
ages.put("bob", 25);
 
ages.get("alice");        // 30
ages.put("alice", 31);    // 30  — returns the OLD value it replaced
ages.get("alice");        // 31
ages.containsKey("carol");// false
ages.remove("bob");       // 25
ages.get("bob");          // null
ages.size();              // 1
 
// watch it grow: 8 buckets, resize once size passes 0.75 × 8 = 6
ChainedHashMap<Integer, Integer> big = new ChainedHashMap<>();
big.capacity();           // 8
for (int i = 0; i < 7; i++) big.put(i, i);
big.capacity();           // 16 — doubled, and every entry rehashed intact

The interview corner

Hash tables show up in a huge fraction of interviews — sometimes as the whole question ("design a data structure with O(1) insert, delete, and get-random"), more often as the quiet tool that turns an O(n²) brute force into O(n). Here’s how to handle them under pressure.

Clarifying questions worth asking before you code:

• "Do I need the keys in any order, or is point lookup enough?" If they say sorted, or "give me the range," a hash map is the wrong structure — you want a balanced tree. This one question can save you from building the wrong thing.
• "Can keys be null, and can they be mutated after insertion?" It shows you know the equals/hashCode contract and the mutable-key trap before you fall in.
• "What are the keys — trusted internal data, or attacker-controlled input?" Naming the adversarial case out loud signals you understand O(1) is an average, not a guarantee.

The follow-up ladder — where interviewers push once your basic map works:

1. "Now make get, put, and getRandom all O(1)." Pair the hash map (key → index) with an array list of the entries; getRandom picks a random array index. Delete in O(1) by swapping the target with the last element before removing. The map gives lookup; the array gives random access.
2. "Your map is shared across threads. Make it safe without one global lock." Lock stripes, not the whole map — partition the buckets into segments, each with its own lock, so threads touching different segments never block each other. This is exactly the striping move from the thread-safe LRU cache.
3. "Build an LRU cache on top of this." A hash map for O(1) lookup plus a doubly linked list for O(1) recency updates — the map’s values are the list nodes. That pairing is a whole article: the thread-safe LRU cache.
4. "The map is 40 GB and won’t fit on one machine. Now what?" You shard by hash(key) % machines — but adding a machine reshuffles almost everything. The fix is consistent hashing, which moves only a small slice of keys when the cluster changes.
5. "Membership check over a billion keys, but you can’t afford the memory." When a few false positives are acceptable, a Bloom filter answers "probably present / definitely absent" in a fixed handful of bits per key — the probabilistic cousin of the hash set.

Three mistakes that fail the round:

• Claiming O(1) with no caveat. Say "average O(1), worst case O(n) on collisions" — the missing half is exactly what a senior interviewer is listening for.
• A custom key with equals() but no hashCode() (or a mutable one). Your keys silently vanish into buckets nobody searches. Override both, and keep keys immutable.
• Forgetting the head case in chain deletion, or the negative-index bug in indexFor. Both compile, both look right, and both are wrong on inputs the interviewer will absolutely try.

Where to go from here

You own the core now: hash the key to a slot, resolve collisions, resize to stay fast, and honor the contract. Three directions go deeper:

• Consistent hashing — the trick that lets a distributed hash table add and remove machines while moving only a sliver of the keys; it’s the backbone of sharded caches and databases, and it powers the storage layer in NoSQL internals.
• Bloom filters and HyperLogLog — probabilistic structures that trade a little accuracy for enormous memory savings on "is it present?" and "how many distinct?" at billion-key scale.
• Better open addressing — Robin Hood hashing, cuckoo hashing, and hopscotch hashing tame the clustering we saw, squeezing point lookups down toward a guaranteed small constant.

Next time a form tells you a username is taken before you’ve finished typing, you’ll know it wasn’t magic and it wasn’t luck. It hashed your name to a slot and looked in exactly one place — the same trick a cloakroom attendant has used for a hundred years.