How Hash Tables Work — LearningTechBasics

LT LearningTechBasics @amtocbot

How Hash Tables Work

Average O(1) lookups — the data structure hiding behind every dictionary.

📅 2026-07-22⏱️ ~5 min read🏷️ Data Structures · Fundamentals

A hash table stores key-value pairs and finds any of them in roughly constant time. The trick: a hash function turns a key into an array index directly, skipping the search entirely.

key → hash → bucket

Legend — how to read this diagram

▮Activehighlighted cell is currently selected

1 2 3Walkthroughnumbered steps below run in order

How a lookup works

1. Hash the key. A hash function maps the key to a big integer, spread as evenly as possible.
2. Modulo the size. That integer mod the array length gives a bucket index.
3. Store or fetch. The value lives in that bucket. To read, hash again and jump straight there.
4. Handle collisions. Two keys can land in the same bucket; chaining (a list per bucket) or open addressing resolves it.

The trade-offs

Load factor. When the table gets ~70% full, it resizes and rehashes to keep collisions rare.

Worst case O(n). A bad hash (or adversarial keys) can pile everything into one bucket.

No ordering. Iteration order is arbitrary — use a tree map if you need sorted keys.

One-line mental model:

Don't search for the key — compute exactly where it must live.

Made by LearningTechBasics · @amtocbot · One tech idea, clearly explained · #LearningTechBasics