Open the IRCTC app, type a PNR number, and your ticket status appears in well under a second — even though the railways' servers are holding tens of millions of active bookings at that moment. The app did not scan every booking looking for a match. It went almost straight to the answer. Understanding how that "almost straight to the answer" trick works is the whole point of this chapter, and the data structure behind it is called a hash table.
The problem: finding one record fast
Say you are building the backend for a mobile network with 50,000 active customer records, and you need to look up a customer's plan details the instant their phone number is dialled into a support system. How would you search?
The most obvious method is a linear search: start at record 1, compare the phone number, move to record 2, and so on. In the worst case — the customer you want is the very last record, or is not in the list at all — you make 50,000 comparisons. On a call-centre system handling thousands of lookups a minute, that is far too slow.
You could do better by keeping the records sorted by phone number and using binary search: check the middle record, decide whether your target is in the left half or the right half, and repeat on that half. Each comparison eliminates half of the remaining records, so the number of comparisons needed is roughly log₂(n). For n = 50,000, since 2¹⁵ = 32,768 is less than 50,000 and 2¹⁶ = 65,536 is greater than 50,000, you need about 16 comparisons in the worst case — a huge improvement over 50,000. But 16 comparisons is still 16 steps, and worse, every single insertion into a sorted array requires shifting records to keep the order intact, which is itself an expensive operation.
A hash table aims for something more ambitious: look up (or insert) a record in roughly one step, regardless of whether you are searching among 50 records or 50 million. Not by being clever about comparisons, but by not comparing at all until the very last step. It computes, directly from the key itself, almost exactly where that key's data must be sitting.
Building the intuition: the school cloakroom
Before any formulas, picture a school cloakroom with 50 numbered pegs. If every student simply hung their bag on any free peg, finding your bag later would mean checking pegs one by one — a linear search. Instead, imagine the cloakroom attendant assigns each student a peg number by a fixed rule: take the student's roll number and divide it by 50, and the remainder is the peg number. Roll number 137 gets peg 37 (since 137 = 2×50 + 37). Roll number 214 gets peg 14. Every student's peg number is fully determined by a quick calculation — no searching required. To fetch your bag, you don't scan the room; you redo the same tiny calculation and walk straight to that peg.
That is the entire idea behind a hash table. The "pegs" are called slots or buckets, the array of pegs is the underlying storage, and the "divide and take the remainder" rule is a hash function: a function that converts a key (a roll number, a name, a phone number) into a slot index, so that storing and retrieving both use the exact same calculation instead of a search.
Formal definition: array plus hash function
A hash table combines two things you may already know:
- An array of a fixed size, say
mslots, indexed 0 to m−1 — this is where data actually lives. - A hash function
h(key)that takes any key and deterministically produces an index between 0 and m−1.
To insert a key-value pair, you compute index = h(key) and place the pair at array[index]. To search for a key, you compute the very same index = h(key) and look directly at array[index] — no scanning. Both operations depend only on evaluating the hash function once, which typically takes constant time regardless of how many other keys are already stored. That is why hash table lookups are described as running in O(1) on average — "on average" is a phrase we will pin down precisely later in this chapter, because it hides an important catch.
A good hash function must satisfy two properties. First, it must be deterministic — the same key must always produce the same index, every single time, otherwise you could store a value and never find it again. Second, it should spread keys as evenly as possible across all the available slots, so that no single slot becomes overloaded while others sit empty.
A worked example: hashing four names
Let's build a tiny hash table by hand, small enough to trace completely. Suppose the table has m = 7 slots (indices 0 to 6), and we choose a simple hash function: add up the ASCII codes of every letter in the key, then take the remainder when divided by 7.
def ascii_sum_hash(key, table_size):
total = sum(ord(ch) for ch in key)
return total % table_size
Let's insert four student names — RIYA, KABIR, SANA, and DEV — and hand-compute exactly where each one lands. Recall each letter's ASCII code: A=65, B=66, D=68, E=69, I=73, K=75, N=78, R=82, S=83, V=86, Y=89.
- RIYA: R(82) + I(73) + Y(89) + A(65) = 309. 309 ÷ 7 = 44 remainder 1. So h(RIYA) = 1.
- KABIR: K(75) + A(65) + B(66) + I(73) + R(82) = 361. 361 ÷ 7 = 51 remainder 4. So h(KABIR) = 4.
- SANA: S(83) + A(65) + N(78) + A(65) = 291. 291 ÷ 7 = 41 remainder 4. So h(SANA) = 4.
- DEV: D(68) + E(69) + V(86) = 223. 223 ÷ 7 = 31 remainder 6. So h(DEV) = 6.
Notice something important: KABIR and SANA both hash to slot 4. That is not a mistake in our arithmetic — it is a collision, and it is completely normal. We will deal with it in a moment. First, here is what the table looks like after inserting all four names in this order (RIYA, then KABIR, then SANA, then DEV), with slot 4 holding both KABIR and SANA:
Follow each arrow from a key box down to the slot it actually lands in: RIYA's arrow ends at slot 1, KABIR's arrow ends at slot 4, SANA's arrow also ends at slot 4 — routed into a second box chained off KABIR's, since slot 4 is already occupied — and DEV's arrow curves down into slot 6 in the second row. Slots 0, 2, 3, and 5 stay empty, which is expected: we only inserted four names into seven slots.
Collisions are guaranteed, not a bug
Two different keys landing in the same slot — like KABIR and SANA both hashing to 4 — is called a collision, and every real hash table must handle it, no matter how good the hash function is. Two separate ideas explain why collisions happen, and it is worth being precise about which one applies when.
The pigeonhole principle is the strict guarantee: if you have more keys than slots — say 10 keys and only 7 slots — then at least two keys are forced to share a slot, by simple counting, regardless of how the hash function is designed. You cannot fit 10 pigeons into 7 holes one-per-hole.
But our example only inserted 4 keys into 7 slots — plenty of room, no pigeonhole violation — and we still got a collision. That surprising frequency is explained by the birthday paradox: in a room of just 23 people, there is better than even odds that two of them share a birthday, even though a year has 365 "slots." Collisions become likely much sooner than intuition suggests, because you're not asking "will key X collide with a specific other key," you're asking "will any pair among all the keys collide," and the number of possible pairs grows fast. With 4 keys there are 6 possible pairs that could collide, and each pair has roughly a 1-in-7 chance — so an unlucky match is genuinely plausible, not a sign that our hash function is broken.
The practical conclusion: no hash function, however well designed, can promise zero collisions once your table has any real load on it. Every hash table implementation needs a strategy for what to do when two keys land in the same slot.
Handling collisions: chaining
The most common strategy, and the one drawn above, is called separate chaining: instead of storing one value per slot, each slot holds a small list. When a new key hashes to a slot that's already occupied, it is simply appended to that slot's list rather than overwriting what's there.
table = [[] for _ in range(7)]
def insert(key, value):
idx = ascii_sum_hash(key, 7)
table[idx].append((key, value))
insert("RIYA", "9876543210")
insert("KABIR", "9123456780")
insert("SANA", "9988776655")
insert("DEV", "9012345678")
print(table)
Tracing this by hand: table starts as seven empty lists, one per index 0–6. insert("RIYA", ...) computes index 1 and appends to table[1]. insert("KABIR", ...) computes index 4 and appends to table[4], which was empty, so it now holds one pair. insert("SANA", ...) also computes index 4, finds it non-empty, and appends anyway — table[4] now holds two pairs, in insertion order. insert("DEV", ...) computes index 6 and appends to table[6]. The printed result is:
[[], [('RIYA', '9876543210')], [], [], [('KABIR', '9123456780'), ('SANA', '9988776655')], [], [('DEV', '9012345678')]]
Seven positions, exactly matching the seven slots in the diagram: empty, RIYA, empty, empty, KABIR-then-SANA, empty, DEV.
Searching in a hash table
Search follows the identical logic as insert, just comparing instead of appending: compute the index, then walk that slot's chain comparing keys until you find a match (or run off the end of the chain, meaning the key isn't present).
def search(key):
idx = ascii_sum_hash(key, 7)
bucket = table[idx]
comparisons = 0
for stored_key, value in bucket:
comparisons += 1
if stored_key == key:
return value, comparisons
return None, comparisons
result, comparisons = search("SANA")
print(result, comparisons)
Trace it: ascii_sum_hash("SANA", 7) recomputes to index 4 — the exact same calculation done during insertion, so it lands on the exact same slot. bucket becomes table[4], which is [('KABIR', '9123456780'), ('SANA', '9988776655')]. The loop's first iteration compares against 'KABIR': not a match, comparisons becomes 1. The second iteration compares against 'SANA': a match, comparisons becomes 2, and the function returns immediately. The printed output is 9988776655 2 — the phone number, found using only 2 comparisons, out of four names stored, without ever touching slots 0, 1, 2, 3, 5, or 6 at all.
That last point is the entire payoff: search never looked at RIYA's slot or DEV's slot. It computed one index and only examined the (short) chain living there.
Two misconceptions, corrected
Misconception 1 — "Hash table lookups are always O(1)." This is only true on average, and only when the hash function spreads keys evenly and the table isn't overloaded. In the worst case, a badly designed hash function could send every single key to the same slot, turning the "hash table" into one very long chain — at which point searching it degrades to a plain linear search through that chain, which is O(n). A good hash function makes the worst case rare, but it never makes it impossible; that is why textbooks state hash table performance as "O(1) average case, O(n) worst case," and both halves of that sentence matter.
Misconception 2 — "Hashing is the same as encryption." They solve different problems entirely. Encryption is designed to be reversible by someone holding the right key — you can decrypt ciphertext back into the original message. The hash functions used in hash tables are designed to be fast and to spread keys evenly; they are not designed to be secure or hard to reverse, and in fact many keys can (and do, on purpose, via chaining) map to the same output. Cryptographic hash functions, used for things like password storage, are a different, much more carefully engineered family of functions with additional security requirements — same word "hash," a related idea, but not what powers the everyday hash table you just built by hand above.
Load factor and resizing
A hash table's load factor is the number of stored keys divided by the number of slots: α = n / m. It is the single most important number for predicting performance — the fuller the table, the longer the chains tend to get, and the closer average-case search drifts toward worst-case search.
Most real implementations pick a threshold, commonly around 0.7, and monitor the load factor after every insertion. Suppose a table has 20 slots and currently holds 14 keys: the load factor is 14/20 = 0.7, right at the threshold. Insert one more key and the table holds 15 keys: the load factor becomes 15/20 = 0.75, which exceeds 0.7. At that moment the table triggers a resize: it allocates a larger array — typically double the size, so 40 slots here — and re-inserts every existing key by recomputing its hash against the new, larger table size (this step is called rehashing, and it's necessary because key mod 20 and key mod 40 generally give different answers for the same key). Resizing is an expensive O(n) operation when it happens, but because it only happens occasionally — every time the table roughly doubles in count — its cost, spread out over all the cheap insertions in between, stays low on average. This is why Python dictionaries, Java HashMaps, and most production hash tables all resize automatically rather than letting the load factor climb unchecked.
Where this shows up around you
Once you know what to look for, hash tables are everywhere in Indian digital infrastructure. When you check a PNR on IRCTC, the backend doesn't scan every booking made that week — it hashes the PNR number directly to the record. When UPI processes a transaction, every transaction is tagged with a unique transaction ID, and payment systems use hash-table-backed lookups to instantly check "have I already processed this exact transaction ID?" — critical for preventing the same payment from being deducted twice if a request gets retried after a network hiccup. And when a spell-checker in a word processor flags a typo, it is typically hashing each word you type and checking whether that hash lands on an occupied slot in a dictionary of several lakh valid words — a lookup that has to complete in milliseconds, for every word, as you type.
Active recall
- Using the hash function
h(key) = (sum of ASCII codes) mod 7, compute h("VIR"). (V=86, I=73, R=82.) Which slot does VIR land in, and does it collide with any of RIYA, KABIR, SANA, or DEV from the worked example? - A hash table has 50 slots and currently holds 33 keys. What is the load factor? If the resize threshold is 0.7, will inserting one more key trigger a resize?
- Explain, in one or two sentences, why the pigeonhole principle does not apply to explain the KABIR/SANA collision in this chapter's worked example, but the birthday paradox does.
- A classmate says, "Hash tables are always faster than binary search because they're O(1) and binary search is O(log n)." What is wrong with this claim?
Answer key: (1) V(86)+I(73)+R(82) = 241; 241 ÷ 7 = 34 remainder 3, so h(VIR) = 3, landing in the slot that was empty in the diagram — no collision with any of the four names shown. (2) Load factor = 33/50 = 0.66. Adding one more key makes it 34/50 = 0.68, which is still below 0.7, so no resize is triggered yet. (3) Pigeonhole requires more keys than slots to force a collision (here 4 keys, 7 slots — no forcing); the birthday paradox instead explains why, even with room to spare, collisions among a handful of keys are more likely than intuition suggests, because there are multiple pairs of keys that could each collide. (4) O(1) is an average-case guarantee that depends on a well-behaved hash function and a controlled load factor; in the worst case (a bad hash function, or a table allowed to become extremely full) hash table lookups degrade to O(n), which can be slower than binary search's guaranteed O(log n) — so the blanket claim "always faster" is false.
Summary
A hash table stores data in an array and uses a hash function to compute, directly from a key, almost exactly which slot holds that key's value — turning search from "look through records until you find a match" into "calculate the address, then check that one spot." Collisions, where two different keys compute the same slot, are mathematically inevitable once a table has any real load (guaranteed once keys outnumber slots, by the pigeonhole principle; surprisingly likely well before that, by the birthday paradox), so every hash table needs a collision strategy — chaining, which stores a short list per slot, is the most common. The headline "O(1) lookup" is an average-case claim that depends on the hash function spreading keys evenly and the load factor being kept in check through periodic resizing; the worst case is O(n), and remembering that distinction is what separates a working understanding of hash tables from a slogan.
Practice Exercises
Now it is time to practice! Complete these challenges to solidify your understanding:
- Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
- Exercise 2: Find a real-world example where hash tables is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
- Exercise 3: Create a mind-map connecting hash tables to at least 3 other topics you have studied.