# Finding Maya's Coat Without a Ticket: Hash Tables

Find a coat by its owner's name in one step, at a coat check with 3,000 coats and no tickets: why a list, an A-to-Z rack and hooks by first letter all fall short, and the structure that fixes them, the hash table.

Apprentice · Data Structures · Updated November 17, 2026

By Gregor Dzierzon

## After this lesson you can

- Explain why a hash table finds a value by its key in O(1) time on average
- Work out which bucket a key goes to from its hash and the number of buckets
- Choose between a list, a sorted list and a hash table for a lookup job, and say why

## Key takeaways

- Checking every coat is O(n); a rack kept A to Z finds a coat in O(log n), but every new coat slides the rest along, O(n) per coat.
- A hash table stores values under keys, and turns each key into a bucket number, so it goes straight to the right bucket instead of searching.
- A hash function is the recipe that turns a key into a number; the remainder after dividing by the number of buckets picks the bucket.
- Putting, getting and removing a value by its key are O(1) on average, however many values the table holds.
- Finding a value without its key, or listing the values in order, still means looking at every bucket: O(n).

**Before this:** *Jump to Song 500: Arrays* (going straight to slot 7 is one step, however long the array) and *One Song in a Million, in 20 Looks: Binary Search* (halving a sorted list).

The concert ends at 11 p.m., and 3,000 people want their coats at once. The coat check's paper tickets ran out at 8, so since then every guest has handed over a coat and said a name. Now the line reaches the door, and each guest at the counter says "It's under Maya" and waits while the attendant finds it.

You'll meet this job all the time, wearing other clothes. A login form finds your account from your email among millions. A shopping cart finds the price of product 48213 without reading the whole catalog. Each one starts from a name and needs the thing stored under it, fast. By the end of this lesson you'll have the structure every language uses for it, the **hash table**; first, the coat check.

## What would you try?

**Hang the coats in the order they arrive, and check each one.** Hanging is instant: the next free hook. But finding Maya's coat means reading name tags from the first hook until you reach hers, about 1,500 tags on average and all 3,000 for a name that isn't there. That's O(n) for every guest, and about 4.5 million name tags read before everyone goes home.

**Keep the rack in A to Z order, and halve it.** Now finding is *One Song in a Million, in 20 Looks: Binary Search* from Module 4: about 12 looks for 3,000 coats, O(log n). But the coats don't arrive in A to Z order. When Maya turns up, every coat from "Mb" to "Z" slides one hook along to make room, about half the rack. Hanging 3,000 coats that way is over 2 million slides, all in the half hour before the show. Finding got fast, and hanging got slow: O(n) per coat.

**Give each first letter its own section.** Twenty-six sections, A to Z. Maya's coat goes in the M section, and at 11 p.m. you walk straight there: one step, like going to slot 7 of an array. That part is right. But names don't spread evenly over the alphabet. M, S and J can hold two or three hundred coats each, while Q, X and U hold almost none. At the M section, you're back to checking coats one by one.

| What we tried | Hang a coat | Find a coat | Where it breaks |
|---|---|---|---|
| Arrival order | O(1) | O(n): about 1,500 looks | the line at 11 p.m. |
| A to Z rack | O(n): slide up to 3,000 | O(log n): about 12 looks | the rush at 8 p.m. |
| A section per first letter | O(1) | one step, then a search of a crowded section | crowded letters |

## The questions that lead to it

**What does the coat check do most?** Two jobs, 3,000 times each: hang a coat, in a rush before the show, and find one, in a rush after it. Both have to be fast. Nobody asks for the coats in A to Z order, so keeping that order is work nobody needs.

**Why was the paper ticket so fast?** Because the number on it said where to look. Nobody searched: they walked to hook 214.

**What did the first-letter try get right?** It turned the name into a place. It failed in two ways: 26 places aren't enough for 3,000 coats, and one letter doesn't spread names out.

So what if *every* letter of the name helped pick the hook, and there were as many hooks as we liked? Turn the name into a number with a quick recipe that uses all its letters, and hang the coat on that hook. At the end of the night, run the same recipe on the same name, get the same number, and walk straight there. The name *is* the ticket.

![A concert coat check with no tickets: a guest says her name, Maya, at the counter; the attendant reads a small recipe card that turns a name into a hook number, and walks straight to hook 2 on a long rack of numbered hooks, passing every other coat](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/608464e5d934479ca15b5798fb17845c.webp)

## How it got its name

This idea was so useful that it got a name: a **hash table**. "Hash" means to chop up and mix, as in hash browns, and the recipe chops a key up into a number.

- The thing you look up by, here the name, is the **key**. What you store under it, the coat, is the **value**. Together they're a **key-value pair**.
- The recipe that turns a key into a number is a **hash function**, and the number it gives is the key's **hash**.
- Each hook is a **bucket**: one numbered slot in an array.
- The whole thing, an array of buckets and a hash function to pick one, is a **hash table**.

Here's the recipe this lesson uses. Every letter is stored as a number (its character code: `M` is 77, `a` is 97, `y` is 121), so add up the letters' codes. Then, since there are only 10 hooks, keep the **remainder** after dividing by 10. In code the remainder is written `%`, read "mod": 392 % 10 is 2, because 392 is 39 tens with 2 left over. Whatever the total, the remainder is always 0 to 9, so it always names a real hook.

![The key "Maya" going through the hash function: its letters M, a, y, a become the codes 77, 97, 121 and 97, which add up to 392; 392 mod 10 is 2, so Maya's coat goes in bucket 2 of a row of ten buckets numbered 0 to 9](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/17f6bfab286e42aba8ab18ae614fcadf.webp)

## A coat check in code

This hash table has 10 buckets. Each bucket holds one name and one coat, in two arrays side by side. `Put` hashes the name and hangs the coat in that bucket. `Get` hashes the name again, goes to that bucket, and checks that the name there is the one asked for:

```csharp
string?[] owners = new string?[10];
string?[] coats = new string?[10];

int HookFor(string name)
{
    int total = 0;
    foreach (char letter in name)
    {
        total += letter;
    }
    return total % 10;
}

void Put(string name, string coat)
{
    int hook = HookFor(name);
    owners[hook] = name;
    coats[hook] = coat;
    Console.WriteLine(name + " hangs on hook " + hook);
}

string? Get(string name)
{
    int hook = HookFor(name);
    return owners[hook] == name ? coats[hook] : null;
}

Put("Maya", "green raincoat");
Put("Leo", "denim jacket");
Put("Priya", "red scarf");

Console.WriteLine("Leo's coat: " + Get("Leo"));
Console.WriteLine("Sam's coat: " + (Get("Sam") ?? "none"));
```

```text
Maya hangs on hook 2
Leo hangs on hook 8
Priya hangs on hook 7
Leo's coat: denim jacket
Sam's coat: none
```

```java
String[] owners = new String[10];
String[] coats = new String[10];

int hookFor(String name) {
    int total = 0;
    for (char letter : name.toCharArray()) {
        total += letter;
    }
    return total % 10;
}

void put(String name, String coat) {
    int hook = hookFor(name);
    owners[hook] = name;
    coats[hook] = coat;
    IO.println(name + " hangs on hook " + hook);
}

String get(String name) {
    int hook = hookFor(name);
    return name.equals(owners[hook]) ? coats[hook] : null;
}

void main() {
    put("Maya", "green raincoat");
    put("Leo", "denim jacket");
    put("Priya", "red scarf");

    IO.println("Leo's coat: " + get("Leo"));
    String samsCoat = get("Sam");
    IO.println("Sam's coat: " + (samsCoat == null ? "none" : samsCoat));
}
```

```text
Maya hangs on hook 2
Leo hangs on hook 8
Priya hangs on hook 7
Leo's coat: denim jacket
Sam's coat: none
```

```python
owners = [None] * 10
coats = [None] * 10


def hook_for(name):
    total = 0
    for letter in name:
        total += ord(letter)
    return total % 10


def put(name, coat):
    hook = hook_for(name)
    owners[hook] = name
    coats[hook] = coat
    print(f"{name} hangs on hook {hook}")


def get(name):
    hook = hook_for(name)
    return coats[hook] if owners[hook] == name else None


put("Maya", "green raincoat")
put("Leo", "denim jacket")
put("Priya", "red scarf")

print(f"Leo's coat: {get('Leo')}")
print(f"Sam's coat: {get('Sam') or 'none'}")
```

```text
Maya hangs on hook 2
Leo hangs on hook 8
Priya hangs on hook 7
Leo's coat: denim jacket
Sam's coat: none
```

```javascript
const owners = new Array(10).fill(null);
const coats = new Array(10).fill(null);

function hookFor(name) {
  let total = 0;
  for (const letter of name) {
    total += letter.charCodeAt(0);
  }
  return total % 10;
}

function put(name, coat) {
  const hook = hookFor(name);
  owners[hook] = name;
  coats[hook] = coat;
  console.log(`${name} hangs on hook ${hook}`);
}

function get(name) {
  const hook = hookFor(name);
  return owners[hook] === name ? coats[hook] : null;
}

put("Maya", "green raincoat");
put("Leo", "denim jacket");
put("Priya", "red scarf");

console.log(`Leo's coat: ${get("Leo")}`);
console.log(`Sam's coat: ${get("Sam") ?? "none"}`);
```

```text
Maya hangs on hook 2
Leo hangs on hook 8
Priya hangs on hook 7
Leo's coat: denim jacket
Sam's coat: none
```

```typescript
const owners: (string | null)[] = new Array(10).fill(null);
const coats: (string | null)[] = new Array(10).fill(null);

function hookFor(name: string): number {
  let total = 0;
  for (const letter of name) {
    total += letter.charCodeAt(0);
  }
  return total % 10;
}

function put(name: string, coat: string): void {
  const hook = hookFor(name);
  owners[hook] = name;
  coats[hook] = coat;
  console.log(`${name} hangs on hook ${hook}`);
}

function get(name: string): string | null {
  const hook = hookFor(name);
  return owners[hook] === name ? coats[hook] : null;
}

put("Maya", "green raincoat");
put("Leo", "denim jacket");
put("Priya", "red scarf");

console.log(`Leo's coat: ${get("Leo")}`);
console.log(`Sam's coat: ${get("Sam") ?? "none"}`);
```

```text
Maya hangs on hook 2
Leo hangs on hook 8
Priya hangs on hook 7
Leo's coat: denim jacket
Sam's coat: none
```

Nobody checked in under "Sam", so `Get` goes to Sam's hook, 9, finds no one there, and answers "none" without looking anywhere else.

**Try it.** Put a coat in for Sam, then one for Omar. Both land on hook 9 (their letters add up to 289 and 399), and Omar's coat replaces Sam's. Two keys on one bucket is called a **collision**, and *Collisions: Two Coats, One Hook* shows how a real hash table keeps both.

## Why it's O(1)

Count the steps of `Get`. It adds up the letters of one name, divides once, and looks in one bucket. None of that depends on how many coats are hanging. With 3 coats or 3 million, finding Leo's is the same handful of steps: **O(1)**, constant time.

There's a catch, and it's why you'll hear "O(1) **on average**". The speed depends on the keys spreading out over the buckets. If many keys landed in the same bucket, the table would have to search that bucket, and you'd be back to O(n). How a good hash function spreads keys out is the next lesson, *Why Is Everyone on Hook 3? Hash Functions*.

## When the A to Z rack wins

A hash table's speed has a price: the hooks follow the recipe, not the alphabet. If the coat check also had to print every guest from A to Z, or find everyone from Kai to Maya, the hash table would have to sort its keys first, every time. When order matters as much as finding, a structure that keeps its keys sorted earns its place: *A Contact List That's Fast to Search and Easy to Change: Binary Search Trees*, in Module 6, finds in O(log n) and adds without sliding everything along.

## You already have one

You don't usually build a hash table yourself: every language has one built in, and *The Front Desk Finds You in One Scan: Dictionaries* shows yours (`Dictionary` in C#, `HashMap` in Java, `dict` in Python, `Map` in JavaScript and TypeScript). Building a small one here is what makes those fast lookups stop feeling like magic, and the exercise *Build a Coat Check* takes it all the way.

## The cost card

| Operation | Big-O | The everyday reason |
|---|---|---|
| Put a value under a key | O(1) on average | Work out the hook from the name, hang the coat there |
| Get the value for a key | O(1) on average | Work out the hook again, walk straight to it |
| Remove a key | O(1) on average | Walk straight to the hook, take the coat down |
| Find a key from its value ("whose is the red scarf?") | O(n) | The recipe works from names, not coats, so you check every hook |
| List the keys in order | O(n log n) | Hooks follow the recipe, not the alphabet, so you sort them first |

## Check yourself

2 questions to try on the lesson page.

## So what

A hash table trades a little arithmetic for not searching at all. Whenever you need to find something by a name, an ID or an email, and the list is long, this is the structure that makes it instant.

## Key terms

- [Hash Table](https://www.ask-codey.com/glossary/hash-table)
- [Hash Function](https://www.ask-codey.com/glossary/hash-function)
- [Bucket](https://www.ask-codey.com/glossary/bucket)
- [Key-Value Pair](https://www.ask-codey.com/glossary/key-value-pair-data-structures)
- [Modulo](https://www.ask-codey.com/glossary/modulo-software-development)

## Cheat sheets

- [Finding Maya's Coat Without a Ticket: Hash Tables](https://www.ask-codey.com/cheat-sheets/ds-hash-tables-cheat-sheet)

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