How Dictionaries Work — Hash Tables

Start here A list lets you find an item by its position (0, 1, 2, ...). A dictionary lets you find a value by any key — a name, a roll number, a word — and it is just as fast for every key. How? A dictionary is secretly an array, plus a clever function that turns any key into an array position. This is called a hash table.

Lists vs dictionaries #

A dictionary is a collection of key–value pairs, like {"Asha": 85, "Ravi": 72}.

The idea: turn keys into positions #

The storage underneath is an array. Given a position i, we can reach A[i] in constant time. So we only need a way to convert any key into a position in 0, 1, ..., n − 1.

That converter is a hash function.

Hash function h : S → X maps a big set of possible keys S to a small range of integers X = {0, 1, ..., n − 1}.

A toy hash function — worked example #

Let's use a table of size n = 10 and this hash function: add up the character codes of the key, then take the remainder when divided by 10.

(Each character has a number code: 'a' = 97, 'b' = 98, 'c' = 99, 'd' = 100, 'g' = 103, 'o' = 111, 't' = 116.)

So "cat" goes to slot 2, "dog" to slot 4, "bat" to slot 1. But "act" also wants slot 2, and "god" also wants slot 4.

Collisions #

There are far more possible keys than slots (|X| is much smaller than |S|), so two different keys will sometimes get the same position:

Collision: h(s) = h(s′) even though s ≠ s′.

A good hash function spreads keys out evenly to make collisions rare. (Our toy function is bad: any two words with the same letters, like "cat" and "act", always collide.) Collisions can't be avoided completely, so we need a plan to handle them.

Two ways to handle collisions #

1. Open addressing (also called closed hashing) #

Everything stays inside the same array. If the slot is taken, probe (try) other slots in a fixed sequence until a free one is found. The simplest sequence is "try the next slot": h, h+1, h+2, ... (wrapping around at the end). This is called linear probing.

Inserting cat, dog, act, bat, god in that order:

Final array (slots 0–9): [ —, bat, cat, act, dog, god, —, —, —, — ]

2. Open hashing (also called chaining) #

Each slot of the array points to a list of key–value pairs. On a collision, just add to that slot's list.

(Yes, the names are confusing: open addressing = closed hashing; open hashing = chaining. Learn them as pairs.)

Why dictionary keys must be immutable #

The position of a key is computed from the key itself. If a key could change after it was stored, its hash would change too — and the dictionary would look in the wrong slot and never find it.

So Python only allows immutable keys: numbers, strings, tuples. Lists can't be keys:

d = {[1, 2]: 3}
# TypeError: unhashable type: 'list'

d = {(1, 2): 3}      # a tuple is fine

Hashing in the real world — SHA-256 #

SHA-256 is an industry-standard hash function. Its output is 256 bits long (usually written as 64 hexadecimal characters). Even a tiny change in the input gives a completely different hash.

Use: cloud storage services hash large files to avoid storing duplicates. If the hash of your file matches a file already stored, there is no need to upload it again.

In one line: A dictionary is a hash table — an array plus a hash function that turns keys into positions; collisions are handled by probing for another slot (open addressing) or by keeping a list at each slot (chaining).

Exam words: dictionary, key–value pair, hash function, hash table, collision, open addressing (closed hashing), probing, linear probing, open hashing (chaining), immutable keys, unhashable, SHA-256.

Quick check #