Hashing in data structure is the reason your phone finds a contact instantly, a login page checks your username in milliseconds, and Python's dict feels like magic. It's also the most useful tool in coding interviews: a huge number of “make it faster” questions are solved by adding one hash map.
This guide explains hash functions, hash tables, collisions and the O(1) idea with a hash table you can build yourself, real code in Python, Java and C++, the famous Two Sum problem, and a memory trick from your hostel mailroom.
The problem hashing solves
Say you store 10,000 students' marks in an array and want Meera's marks. Without any structure you check names one by one: O(n). If the array is sorted you can use binary search: O(log n), about 14 checks. Hashing does better: about 1 check, no matter how many students there are.
The trick is to compute where an item lives from the item itself. If you know the formula, you never have to search.
How hashing works: key → hash → bucket
- Key: what you look things up by (a name, roll number, word).
- Hash function: turns the key into a number, e.g. add up the letter codes.
- Bucket index: reduce the number to a valid position with
% table_size. - Store or find the value in that bucket.
Because the same key always produces the same index, a lookup just repeats the calculation and goes straight to the right bucket. Try it below: the box shows the exact calculation for every name you type.
🎮 Build a hash table
3 keys · 7 buckets · load factor 0.43hash(“meera”) = 109 + 101 + 101 + 114 + 97 = 522 → 522 % 7 = 4
- 0ravi: 78
- 1empty
- 2empty
- 3zoya: 66
- 4empty
- 5arjun: 91
- 6empty
Type a name and press Put. Then try Get, and try names until two land in the same bucket.
Hint for a collision: put “meera”, then “dev”. Both land in bucket 4.
What makes a good hash function?
- Deterministic: the same key always gives the same index.
- Fast: computing it should be cheaper than searching.
- Uniform: keys spread evenly so no bucket gets crowded.
Our demo's “sum of letter codes” is easy to follow but weak: anagrams like ravi and vari always collide. Real languages use smarter formulas (for strings, something like h = h × 31 + c for each character) and a prime or power-of-two table size.
Collisions: chaining vs open addressing
With more possible keys than buckets, collisions are guaranteed. What matters is how you handle them:
| Feature | Separate chaining | Open addressing |
|---|---|---|
| Idea | Each bucket holds a small list (chain) | Everything lives in the array; on a clash, probe for another slot |
| On collision | Append to the bucket's list | Linear (i+1, i+2…), quadratic (i+1², i+2²…) or double hashing |
| Load factor | Can go above 1 | Must stay below 1 (table can fill up) |
| Deletion | Easy: remove from the list | Tricky: needs a “deleted” marker |
| Used by | Java HashMap, C++ unordered_map | Python dict |
Each chain in separate chaining is just a small linked list, which you built in part 5.
Load factor and rehashing
The load factor is number of keys ÷ number of buckets. As it grows, chains get longer and lookups slow down. So hash tables resize (usually doubling) and rehash every key once the load factor passes a limit (Java's HashMap uses 0.75). One resize costs O(n), but it happens so rarely that inserts stay O(1) on average.
🧠 PATH memory card
Remember hashing for good
Picture it · Anchor it · Trace it · Hit-recall it. Four quick steps that turn “I read it once” into “I can explain it in an exam”.
- P
Picture it
Your brain remembers scenes far better than definitions.
← swipe to see the whole picture →
Your hostel mailroom: a letter for roll number 2147 goes straight to locker 7 (the last digit). No searching through every letter. When 3917 also ends in 7, both letters share locker 7, tied on one string.
- A
Anchor it
A silly sentence you can't forget, where every word maps to the concept.
“Roll No. → Locker, Clash → Chain”
- Roll No.→The key
- Last digit→The hash function (key % 10)
- Locker→The bucket / array index
- Go straight there→O(1) average lookup
- Clash→Collision: two keys, same bucket
- Chain→Separate chaining: a list per bucket
- T
Trace it
Run it by hand on a tiny example once. Doing beats reading.
Table of 10 lockers,hash = key % 10. Insert 2147 → locker 7. Insert 1352 → locker 2. Insert 3917 → locker 7 again: clash, chain it after 2147. Now find 3917: go to locker 7, check 2147 (no), 3917 (yes). Two checks, not ten. - H
Hit-recall it
Test yourself now, then again on the day each card comes back.
Card 1 / 9 · new0 mastered · 0 practisedSay the answer out loud first, then flip and be honest.
Hash map in Python, Java and C++
You almost never write a hash table from scratch. Every language ships one. Here are the operations you'll use daily, the frequency-count pattern, and Two Sum:
# Python's dict IS a hash table.
marks = {}
marks["meera"] = 85 # insert O(1) average
marks["ravi"] = 78
marks["meera"] = 88 # same key -> value is updated
print(marks["meera"]) # lookup -> 88
print("asha" in marks) # membership -> False
print(marks.get("asha", 0)) # safe lookup with default -> 0
del marks["ravi"] # delete O(1) average
# Count frequencies: the most common hash map pattern
word = "banana"
freq = {}
for ch in word:
freq[ch] = freq.get(ch, 0) + 1
print(freq) # {'b': 1, 'a': 3, 'n': 2}
# Two Sum in O(n) with a hash map
def two_sum(nums, target):
seen = {} # value -> index
for i, x in enumerate(nums):
if target - x in seen:
return seen[target - x], i
seen[x] = i
return None
print(two_sum([3, 8, 4, 11, 6], 10)) # (2, 4) because 4 + 6 = 10Time complexity of hash table operations
| Operation | Average | Worst case |
|---|---|---|
| Insert / update | O(1) | O(n) |
| Search (lookup) | O(1) | O(n) |
| Delete | O(1) | O(n) |
| Iterate all keys | O(n) | O(n) |
| Find min / max key, or keys in order | O(n) | O(n): use a tree map instead |
Interview classic: Two Sum in O(n)
Given an array and a target, find two numbers that add up to the target. Checking every pair is O(n²). With a hash map you walk the array once, and for each number ask: “have I already seen the partner I need?” That question is an O(1) lookup.
Step 1/5: Target is 10. Look at 3: we need 10 − 3 = 7. seen = {} has no 7, so store 3 → index 0.
Where hashing is used in real life
- Databases and caches: indexes and key-value stores like Redis find records by key in O(1).
- Compilers: symbol tables map variable names to their details.
- Passwords: websites store a cryptographic hash, not your password (a different, one-way kind of hash).
- Deduplication: checking if a file, URL or email has been seen before.
What to learn next
Hash maps give fast lookups but no order. When you need keys kept in sorted order, you need a tree: the next part of the course is binary search trees.
Key takeaways
- ✓Hashing computes where a value lives from its key, so you jump straight to it.
- ✓Key → hash function → bucket index (hash % size) → value.
- ✓Insert, search and delete are O(1) on average, O(n) in the worst case.
- ✓Collisions are normal: fix them with chaining (lists) or open addressing (probing).
- ✓Keep the load factor low by resizing and rehashing.
- ✓Remember it with “Roll No. → Locker, Clash → Chain.”
Frequently asked questions
What is hashing in data structure?
Hashing is a technique that converts a key (like a name or roll number) into an array index using a hash function. The value is stored at that index, so later you can find it by computing the same index again, instead of searching through every item. This gives O(1) average time for insert, search and delete.
What is a hash function?
A hash function takes a key and returns a number, which is then reduced to a valid bucket index (often with % table size). A good hash function is fast, always gives the same output for the same key, and spreads keys evenly across buckets.
What is a collision in hashing and how is it handled?
A collision happens when two different keys get the same bucket index. The two main fixes are separate chaining (each bucket holds a small list of entries) and open addressing (if a bucket is taken, probe for the next free one using linear probing, quadratic probing or double hashing).
What is the difference between a hash table and a hash map?
They are the same idea: a structure that maps keys to values using hashing. “Hash map” is the common name in Java (HashMap) and in general programming; “hash table” is the textbook term. Python's dict and C++'s unordered_map are hash tables too. A hash set stores only keys, with no values.
Why is hash table lookup O(1) and when can it become O(n)?
On average each bucket holds only a few keys, so computing the index and checking that bucket takes constant time. In the worst case, a bad hash function or an attacker can push every key into the same bucket, making lookup O(n). Keeping the load factor low (by resizing) and using a good hash function keeps it O(1) in practice.
🧠 Quick check: hashing
1. A hash table has 10 buckets and uses hash(key) = key % 10. Where does key 47 go?
2. Keys 27 and 57 both go to bucket 7. What is this called?
3. What is the average time to look up a key in a good hash table?
4. In “Roll No. → Locker, Clash → Chain”, what does “Chain” mean?
Checking your access…