How does a hash table work? | Interview Question

Q: How does a hash table work?

**Target Audience:** Developers who use maps every day and want to know what happens inside — beginners welcome. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** Each idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact words an interviewer expects. Every program in this doc was run with `python3 main.py`, and the output quoted in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First A theatre cloakroom has 100 hooks. When you hand in your coat, the attendant does not hang it on the first free hook and then search all 100 when you come back. Instead, they use a rule: take the last two digits of your ticket number, and that is your hook. Ticket 4,217 goes on hook 17. When you return, they compute 17 again and walk straight to it. The work is the same whether the cloakroom holds 3 coats or 90. Sometimes two tickets end in the same digits, 4,217 and 8,317. The atten

The problem

Question presented to candidate: "Explain how a hash table works under the hood: what happens when you insert a key, how collisions are handled, and why lookups are fast. Then tell me how Python's built-in hash map behaves, and sketch a simple one in Python if we have time."

What a strong answer should cover:

Hash function → hash code → bucket index (modulo the bucket count), and the rule that equal keys must have equal hashes.
Collision handling: separate chaining versus open addressing (probing), and tombstones on deletion.
Load factor and resizing with rehashing, giving amortized O(1) inserts.
Average O(1) versus worst-case O(n), what causes the worst case (bad hash, adversarial keys) and the defences.
No ordering guarantees from hashing itself; a tree map when order or ranges matter.
Python specifics: dict and set are hash tables (CPython uses open addressing), keys must be hashable (a list is not), dict keeps insertion order since Python 3.7, and str hashes are randomised per process.

Code / implementation expected: Optional — a small separate-chaining table with put, get, remove and resize in Python, or correct use of the built-in map.

hash-table

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Developers who use maps every day and want to know what happens inside — beginners welcome. Difficulty: Medium Language: Python 3

How to read this doc: Each idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact words an interviewer expects. Every program in this doc was run with python3 main.py, and the output quoted in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

A theatre cloakroom has 100 hooks. When you hand in your coat, the attendant does not hang it on the first free hook and then search all 100 when you come back. Instead, they use a rule: take the last two digits of your ticket number, and that is your hook. Ticket 4,217 goes on hook 17. When you return, they compute 17 again and walk straight to it. The work is the same whether the cloa

The solution is hidden so you can try first

14 min read · 12 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonA hash table from scratch: chaining, load factor, resize

Practice

PythonThe built-in hash map: word counts

Practice

PythonGood hash vs bad hash, counted

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.