Skip to main content
Be Bitwise

How Hash Tables Work

Hashmaps & Hash Tables · Data & Hashing track

5 min read

In this module

The Fastest Dictionary

A million user records, and you need to find one by username. Unsorted array? O(n) — potentially all one million entries. Sorted array with binary search? O(log n), about 20 comparisons. Hash table? O(1) — essentially one computation plus one memory access.

A hash table (also called a hashmap, dictionary, or associative array) stores key-value pairs and gives you near-instant lookup by key. It's the workhorse data structure of practical programming, full stop.

The Core Idea

A hash table sits on top of an ordinary array. The trick is using a hash function to turn a key into an array index.

Insert cat, bird, dog and fish in that order and watch where each one lands. The fourth key is the first collision: fish wants bucket 2, which dog already holds. Then add act and tac. The sum-of-characters hash can't tell anagrams apart, so all three spellings of "cat" pile into bucket 0.

Hash Table Explorer

Challenge: find two keys that collide
0
1
2
3
4
5
6
7
Empty
Occupied
Collision
Probed
Load: 0.00Collisions: 0Entries: 0
Load
0%

The modulo operation (% 8) ensures the hash maps to a valid array index (0 through 7). Because array access is O(1), and the hash computation is O(1), the entire lookup is O(1).

Key Concept

A hash table uses hash(key) % num_buckets to convert a key into an array index, providing O(1) average-case lookup. The hash function does the heavy lifting: it converts any key (string, number, object) into a number that maps to a specific bucket.

Buckets and Slots

Each slot in the underlying array is called a bucket (or slot). In the simplest setup, each bucket holds one key-value pair. The hash function decides which bucket a given key lands in.

With 8 buckets and a good hash function, keys spread out roughly evenly — about 1/8 land in each bucket. As you keep adding keys, buckets start filling up. Sooner or later, two different keys hash to the same bucket. That's a collision, and handling collisions gracefully is the core engineering problem of hash table design.

A Visual Walkthrough

Let's insert several entries into a hash table with 8 buckets. To keep the arithmetic visible, the hash just adds up the character codes and takes the result mod 8.

KeySum of codesBucket (sum % 8)
cat3120
bird4171
dog3142
fish4262

The first three keys each find an empty bucket. Then "fish" arrives and wants bucket 2, which "dog" already holds.

What do we do with "fish"? We can't just clobber "dog" — that throws away data. We need a collision resolution strategy, which is what the next lesson is about.

Key Requirements

For a hash table to behave, a few things have to hold:

  1. The hash function must be deterministic. Same key, same hash, every time. Otherwise you can't find entries after inserting them.

  2. Equal keys must produce equal hashes. If key1 == key2, then hash(key1) == hash(key2). Break this and you'll go looking in the wrong bucket.

  3. The hash function should spread keys uniformly. If many keys land in the same bucket, that bucket becomes a bottleneck and O(1) starts to slip.

Run the walkthrough below, then add your own keys. Before you press Run, predict which bucket a lookup for "cow" checks and what it finds there.

Try itPredict the bucket for each key, then add more keys and watch the collisions pile up.
C (GCC 9.2.0)
Trap: what goes wrong if a key changes after you insert it?

Say you insert "cat" (bucket 0) and then edit the stored string in place to "cot". Its hash is now 326 % 8 = 6, so a lookup for "cot" checks bucket 6 and misses, while a lookup for "cat" goes to bucket 0, finds "cot" and fails the equality check. The entry is still in the table but nobody can reach it. That's why Python refuses lists as dict keys and why the Java Map documentation warns against using mutable objects as keys.

Hash Tables vs. Other Structures

OperationUnsorted ArraySorted ArrayHash Table
LookupO(n)O(log n)O(1) avg
InsertO(1)O(n)O(1) avg
DeleteO(n)O(n)O(1) avg
Ordered?NoYesNo

The trade-off is plain: hash tables give you the fastest lookups and modifications, but they keep no ordering. Want sorted iteration? Reach for a different structure — a balanced BST or a sorted array.

Why Every Language Has One

Hash tables are useful enough that every major language ships one as a built-in type:

  • Python: dict and set
  • JavaScript: Object and Map
  • Java: HashMap and HashSet
  • C++: std::unordered_map and std::unordered_set
  • Go: map
  • Rust: HashMap and HashSet

Use any of these and you're using a hash table underneath. Knowing how they work lets you use them well and dodge the subtle performance traps.

The Power of O(1)

The constant-time lookup is what makes hash tables so useful. Consider the alternative. Without hash tables, looking up a value by key in a sorted collection costs O(log n) with binary search — respectable, but for a collection of a billion entries, that's about 30 comparisons per lookup. With a hash table, it's one hash computation and (on average) one comparison, no matter the size. Multiply by millions of lookups per second and the gap shows up plainly in a profiler.

That's why hash tables are the default choice for any problem with frequent key-based lookups, and why knowing their internals pays off when you're writing high-performance software. The next lesson covers what happens when collisions land and how different resolution strategies shake out in practice.