# Collisions: Two Coats, One Hook

Keep every coat when two names land on the same hook: why refusing the coat, taking the next free hook and starting with a huge rack each fall short, and the plan most hash tables use instead: chaining, the load factor and resizing.

Journeyman · Data Structures · Updated November 17, 2026

By Gregor Dzierzon

## After this lesson you can

- Explain how chaining keeps two keys that collide in one bucket, and how a lookup finds the right one
- Work out a hash table's load factor, and explain why the table resizes and re-places every key when it gets too full

## Key takeaways

- A collision is two keys landing in the same bucket. With more possible keys than buckets, collisions can't be avoided, so every hash table plans for them.
- With chaining, each bucket holds a short list of key-value pairs, and a lookup walks that list comparing keys.
- The load factor is the number of keys divided by the number of buckets: how many keys each bucket holds on average.
- When the load factor gets too high, the table doubles its buckets and re-places every key. That costs O(n), but it's rare, so a put stays O(1) on average.
- If every key collided, one bucket would hold everything and lookups would be O(n): the worst case a good hash function makes very unlikely.

**Before this:** *Finding Maya's Coat Without a Ticket: Hash Tables* and *Why Is Everyone on Hook 3? Hash Functions*.

In *Finding Maya's Coat Without a Ticket*, Omar's coat replaced Sam's, because both names led to hook 9. A real hash table can't lose data like that, and every hash table in every language has a plan for it. That plan is why you'll hear "O(1) **on average**" and not plain "O(1)", why your language's dictionary sometimes pauses for a moment while it grows, and why textbooks and interviews ask about load factors and chaining. This lesson works out the plan.

## Collisions can't be avoided

Two keys landing in the same bucket is a **collision** (or a **hash collision**). A better hash function makes collisions rarer, but nothing makes them impossible. There are far more possible names than hooks, so some names have to share. Hang 17 coats on 16 hooks and at least one hook holds two.

They also come sooner than you'd guess. In a room of just 23 people, it's more likely than not that two share a birthday, even though there are 365 days to choose from. A hash table with a few thousand buckets will see its first collisions after a few dozen keys, so it's built to handle them from the start.

## What would you try?

Omar is at the counter, and his name leads to hook 9, where Sam's coat already hangs.

**Turn Omar away.** "Hook 9 is taken, sorry." Nothing is lost, but the coat check now refuses guests at random, and with a few thousand hooks it starts refusing them after a few dozen coats.

**Use the next free hook.** Hook 9 is taken, so try 10, then 11, until one is free, and at pickup, walk along the same way until you find Omar's name. This works, and some hash tables really do it (Python's `dict` uses a version of it). The catch is how it behaves as the rack fills: coats bunch up in long runs, and each run makes the next coat walk further. With the rack 90% full, finding a coat that's there takes about 5 or 6 looks on average, and learning that a name *isn't* there takes about 50.

**Start with a huge rack.** Give a 50-guest night 10,000 hooks, so collisions are too rare to matter. That's 9,950 empty hooks of memory, and it still doesn't work: with 50 names on 10,000 hooks there's about a 1 in 9 chance that two of them share one, the birthday surprise above.

None of these keep every coat *and* stay fast as the night fills up. So, a better question: **what if a hook could hold more than one coat?**

## Chaining: several coats on one hook

The most common plan is **chaining**. Each bucket doesn't hold one key-value pair: it holds a short list of them, called a chain. Picture a hook with a few hangers on it.

- **Put:** hash the key to find the bucket, then add the pair to that bucket's chain.
- **Get:** hash the key to find the bucket, then walk along its short chain, comparing each key with the one you want.

That's why a hash table keeps the key next to the value. Two coats on one hook look alike from across the room; the name tag on each hanger says which is whose.

![Four hooks numbered 0 to 3, each holding a chain of name tags: hook 0 holds Maya then Zoe, hook 1 is empty, hook 2 holds Leo, and hook 3 holds Priya then Ben. A lookup for Zoe goes to hook 0, then checks Maya, then finds Zoe](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/2849ebaf52fc4e1d85262e08dd108d46.webp)

## How full is too full: the load factor

A chain of one or two is fine. A chain of fifty is a sign-up sheet again. What matters is how many keys each bucket holds on average, and that number has a name: the **load factor**, the number of keys divided by the number of buckets.

Five coats on four hooks is a load factor of 5 ÷ 4 = 1.25: on average, more than one coat per hook. Hash tables keep their load factor low on purpose. Java's `HashMap` grows when it passes 0.75, and Python's `dict` when it's about two-thirds full; other languages pick numbers of their own.

## Resizing: a bigger coat room

When the load factor gets too high, the table **resizes**: it makes a new array of buckets, usually twice as many, and moves every key-value pair into it. Every key has to be hashed again, because the bucket is the hash's remainder, and the remainder depends on the number of buckets. Maya's coat was on hook 0 of 4; on 8 hooks it belongs on hook 4. Hashing every key again into the new buckets is called **rehashing**.

This code puts five coats in a chained table of 4 hooks, using the times-31 recipe from *Why Is Everyone on Hook 3? Hash Functions*, then resizes it to 8:

```csharp
List<List<Entry>> hooks = NewHooks(4);
int count = 0;

List<List<Entry>> NewHooks(int size)
{
    List<List<Entry>> fresh = new List<List<Entry>>();
    for (int i = 0; i < size; i++)
    {
        fresh.Add(new List<Entry>());
    }
    return fresh;
}

int HookFor(string name, int size)
{
    int hash = 0;
    foreach (char letter in name)
    {
        hash = (hash * 31 + letter) % size;
    }
    return hash;
}

void Put(string name, string coat)
{
    hooks[HookFor(name, hooks.Count)].Add(new Entry(name, coat));
    count++;
}

string? Get(string name)
{
    foreach (Entry entry in hooks[HookFor(name, hooks.Count)])
    {
        if (entry.Name == name)
        {
            return entry.Coat;
        }
    }
    return null;
}

void Resize(int size)
{
    List<List<Entry>> old = hooks;
    hooks = NewHooks(size);
    foreach (List<Entry> chain in old)
    {
        foreach (Entry entry in chain)
        {
            hooks[HookFor(entry.Name, size)].Add(entry);
        }
    }
}

void Show()
{
    Console.WriteLine(hooks.Count + " hooks, " + count + " coats, load factor " + (double)count / hooks.Count);
    for (int i = 0; i < hooks.Count; i++)
    {
        List<string> names = new List<string>();
        foreach (Entry entry in hooks[i])
        {
            names.Add(entry.Name);
        }
        Console.WriteLine("Hook " + i + ": " + (names.Count == 0 ? "(empty)" : string.Join(", ", names)));
    }
}

Put("Maya", "green raincoat");
Put("Leo", "denim jacket");
Put("Priya", "red scarf");
Put("Zoe", "yellow umbrella");
Put("Ben", "gray hoodie");
Show();
Resize(8);
Show();
Console.WriteLine("Zoe's coat: " + Get("Zoe"));

record Entry(string Name, string Coat);
```

```text
4 hooks, 5 coats, load factor 1.25
Hook 0: Maya, Zoe
Hook 1: (empty)
Hook 2: Leo
Hook 3: Priya, Ben
8 hooks, 5 coats, load factor 0.625
Hook 0: Zoe
Hook 1: (empty)
Hook 2: (empty)
Hook 3: Ben
Hook 4: Maya
Hook 5: (empty)
Hook 6: Leo
Hook 7: Priya
Zoe's coat: yellow umbrella
```

```java
List<List<Entry>> hooks = newHooks(4);
int count = 0;

List<List<Entry>> newHooks(int size) {
    List<List<Entry>> fresh = new ArrayList<>();
    for (int i = 0; i < size; i++) {
        fresh.add(new ArrayList<>());
    }
    return fresh;
}

int hookFor(String name, int size) {
    int hash = 0;
    for (char letter : name.toCharArray()) {
        hash = (hash * 31 + letter) % size;
    }
    return hash;
}

void put(String name, String coat) {
    hooks.get(hookFor(name, hooks.size())).add(new Entry(name, coat));
    count++;
}

String get(String name) {
    for (Entry entry : hooks.get(hookFor(name, hooks.size()))) {
        if (entry.name().equals(name)) {
            return entry.coat();
        }
    }
    return null;
}

void resize(int size) {
    List<List<Entry>> old = hooks;
    hooks = newHooks(size);
    for (List<Entry> chain : old) {
        for (Entry entry : chain) {
            hooks.get(hookFor(entry.name(), size)).add(entry);
        }
    }
}

void show() {
    IO.println(hooks.size() + " hooks, " + count + " coats, load factor " + (double) count / hooks.size());
    for (int i = 0; i < hooks.size(); i++) {
        List<String> names = new ArrayList<>();
        for (Entry entry : hooks.get(i)) {
            names.add(entry.name());
        }
        IO.println("Hook " + i + ": " + (names.isEmpty() ? "(empty)" : String.join(", ", names)));
    }
}

record Entry(String name, String coat) {}

void main() {
    put("Maya", "green raincoat");
    put("Leo", "denim jacket");
    put("Priya", "red scarf");
    put("Zoe", "yellow umbrella");
    put("Ben", "gray hoodie");
    show();
    resize(8);
    show();
    IO.println("Zoe's coat: " + get("Zoe"));
}
```

```text
4 hooks, 5 coats, load factor 1.25
Hook 0: Maya, Zoe
Hook 1: (empty)
Hook 2: Leo
Hook 3: Priya, Ben
8 hooks, 5 coats, load factor 0.625
Hook 0: Zoe
Hook 1: (empty)
Hook 2: (empty)
Hook 3: Ben
Hook 4: Maya
Hook 5: (empty)
Hook 6: Leo
Hook 7: Priya
Zoe's coat: yellow umbrella
```

```python
def new_hooks(size):
    return [[] for _ in range(size)]


def hook_for(name, size):
    hash_value = 0
    for letter in name:
        hash_value = (hash_value * 31 + ord(letter)) % size
    return hash_value


hooks = new_hooks(4)
count = 0


def put(name, coat):
    global count
    hooks[hook_for(name, len(hooks))].append((name, coat))
    count += 1


def get(name):
    for entry_name, coat in hooks[hook_for(name, len(hooks))]:
        if entry_name == name:
            return coat
    return None


def resize(size):
    global hooks
    old = hooks
    hooks = new_hooks(size)
    for chain in old:
        for entry in chain:
            hooks[hook_for(entry[0], size)].append(entry)


def show():
    print(f"{len(hooks)} hooks, {count} coats, load factor {count / len(hooks)}")
    for i, chain in enumerate(hooks):
        names = [entry_name for entry_name, coat in chain]
        print(f"Hook {i}: {', '.join(names) if names else '(empty)'}")


put("Maya", "green raincoat")
put("Leo", "denim jacket")
put("Priya", "red scarf")
put("Zoe", "yellow umbrella")
put("Ben", "gray hoodie")
show()
resize(8)
show()
print(f"Zoe's coat: {get('Zoe')}")
```

```text
4 hooks, 5 coats, load factor 1.25
Hook 0: Maya, Zoe
Hook 1: (empty)
Hook 2: Leo
Hook 3: Priya, Ben
8 hooks, 5 coats, load factor 0.625
Hook 0: Zoe
Hook 1: (empty)
Hook 2: (empty)
Hook 3: Ben
Hook 4: Maya
Hook 5: (empty)
Hook 6: Leo
Hook 7: Priya
Zoe's coat: yellow umbrella
```

```javascript
function newHooks(size) {
  return Array.from({ length: size }, () => []);
}

function hookFor(name, size) {
  let hash = 0;
  for (const letter of name) {
    hash = (hash * 31 + letter.charCodeAt(0)) % size;
  }
  return hash;
}

let hooks = newHooks(4);
let count = 0;

function put(name, coat) {
  hooks[hookFor(name, hooks.length)].push({ name, coat });
  count++;
}

function get(name) {
  for (const entry of hooks[hookFor(name, hooks.length)]) {
    if (entry.name === name) {
      return entry.coat;
    }
  }
  return null;
}

function resize(size) {
  const old = hooks;
  hooks = newHooks(size);
  for (const chain of old) {
    for (const entry of chain) {
      hooks[hookFor(entry.name, size)].push(entry);
    }
  }
}

function show() {
  console.log(`${hooks.length} hooks, ${count} coats, load factor ${count / hooks.length}`);
  hooks.forEach((chain, i) => {
    const names = chain.map((entry) => entry.name);
    console.log(`Hook ${i}: ${names.length === 0 ? "(empty)" : names.join(", ")}`);
  });
}

put("Maya", "green raincoat");
put("Leo", "denim jacket");
put("Priya", "red scarf");
put("Zoe", "yellow umbrella");
put("Ben", "gray hoodie");
show();
resize(8);
show();
console.log(`Zoe's coat: ${get("Zoe")}`);
```

```text
4 hooks, 5 coats, load factor 1.25
Hook 0: Maya, Zoe
Hook 1: (empty)
Hook 2: Leo
Hook 3: Priya, Ben
8 hooks, 5 coats, load factor 0.625
Hook 0: Zoe
Hook 1: (empty)
Hook 2: (empty)
Hook 3: Ben
Hook 4: Maya
Hook 5: (empty)
Hook 6: Leo
Hook 7: Priya
Zoe's coat: yellow umbrella
```

```typescript
type Entry = { name: string; coat: string };

function newHooks(size: number): Entry[][] {
  return Array.from({ length: size }, () => []);
}

function hookFor(name: string, size: number): number {
  let hash = 0;
  for (const letter of name) {
    hash = (hash * 31 + letter.charCodeAt(0)) % size;
  }
  return hash;
}

let hooks: Entry[][] = newHooks(4);
let count = 0;

function put(name: string, coat: string): void {
  hooks[hookFor(name, hooks.length)].push({ name, coat });
  count++;
}

function get(name: string): string | null {
  for (const entry of hooks[hookFor(name, hooks.length)]) {
    if (entry.name === name) {
      return entry.coat;
    }
  }
  return null;
}

function resize(size: number): void {
  const old = hooks;
  hooks = newHooks(size);
  for (const chain of old) {
    for (const entry of chain) {
      hooks[hookFor(entry.name, size)].push(entry);
    }
  }
}

function show(): void {
  console.log(`${hooks.length} hooks, ${count} coats, load factor ${count / hooks.length}`);
  hooks.forEach((chain, i) => {
    const names = chain.map((entry) => entry.name);
    console.log(`Hook ${i}: ${names.length === 0 ? "(empty)" : names.join(", ")}`);
  });
}

put("Maya", "green raincoat");
put("Leo", "denim jacket");
put("Priya", "red scarf");
put("Zoe", "yellow umbrella");
put("Ben", "gray hoodie");
show();
resize(8);
show();
console.log(`Zoe's coat: ${get("Zoe")}`);
```

```text
4 hooks, 5 coats, load factor 1.25
Hook 0: Maya, Zoe
Hook 1: (empty)
Hook 2: Leo
Hook 3: Priya, Ben
8 hooks, 5 coats, load factor 0.625
Hook 0: Zoe
Hook 1: (empty)
Hook 2: (empty)
Hook 3: Ben
Hook 4: Maya
Hook 5: (empty)
Hook 6: Leo
Hook 7: Priya
Zoe's coat: yellow umbrella
```

Before the resize, two hooks hold chains of two, and finding Zoe means checking Maya first. After it, every coat has a hook of its own, the load factor is down to 0.625, and Zoe is found on the first try. This `Put` leaves out one check a real one makes: whether the name is already on its hook, so the coat should replace the old one. The exercise *Build a Coat Check* adds it, and resizes by itself when the table gets too full.

![The same five coats before and after resizing: on the left, 4 hooks with chains of two on hooks 0 and 3 and a load factor of 1.25; on the right, 8 hooks where Zoe moves to hook 0, Ben to 3, Maya to 4, Leo to 6 and Priya to 7, one coat per hook, with a load factor of 0.625](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/97f50d333de84bd692c1f5df94a316b7.webp)

## Moving day is rare

Resizing touches every key, so that one put costs O(n). But the table doubles each time, so resizes get further and further apart: after growing from 1,000 buckets to 2,000, it takes another 750 or so puts before the next one. Spread over all those cheap puts, the occasional moving day adds only a little to each, and a put is still O(1) on average. It's the same reason a growing array's add is fast, in *Is Adding a Song Slow? Amortized Cost*.

## The worst case

Imagine a hash function that sent every key to bucket 0. One chain would hold everything, and every get would read it from the top: O(n), the sign-up sheet. A bad hash function, or an attacker sending keys chosen to collide, can do that.

That's why hash tables are the famous exception to *Fast in the Demo, Slow for Users: Best, Worst and Average*, where Big-O usually means the worst case. With a good hash function and a table that resizes, the worst case is so unlikely that everyone quotes the average: O(1).

**In your textbook:** the "next free hook" try is called **open addressing**, and walking to the next bucket, then the next, is **linear probing**. It's a real rival to chaining, and the load factor matters just as much: the fuller the table, the longer the walk.

## The cost card

| Operation | Big-O | The everyday reason |
|---|---|---|
| Put, get or remove by key | O(1) on average | One hook, and a chain of one or two coats on it |
| Resize | O(n), but rare | Moving day: every coat is re-hung in the bigger room |
| Put, get or remove, worst case | O(n) | Every coat ended up on one hook, so you check them all |
| Find a key from its value | O(n) | The recipe works from names, so you check every hook |

## Check yourself

2 questions to try on the lesson page.

## So what

Collisions are part of every hash table's day, and chaining plus resizing is how "O(1)" stays true anyway. When a dictionary seems to pause while it fills up, it's moving to a bigger coat room.

## Key terms

- [Hash Collision](https://www.ask-codey.com/glossary/hash-collision)
- [Chaining](https://www.ask-codey.com/glossary/chaining)
- [Load Factor](https://www.ask-codey.com/glossary/load-factor)
- [Rehashing](https://www.ask-codey.com/glossary/rehashing)

## Cheat sheets

- [Collisions: Two Coats, One Hook](https://www.ask-codey.com/cheat-sheets/ds-hash-collisions-cheat-sheet)

Source: https://www.ask-codey.com/lessons/ds-hash-collisions
