Welcome to the Hash Maps module. A Hash Map (also known as a Dictionary, Hash Table, or Associative Array) is a structure that stores Key Value pairs and retrieves values in average Constant Time, regardless of whether the table contains 10 entries or 10,000,000 entries.
If Arrays are the workhorse of memory, Hash Maps are the most useful high-level data structure in software development.
Before you start
- You understand arrays and O(1) indexing. See arrays.
- You know what a linked list is, since chaining uses one. See linked lists.
What you will be able to do after this lesson:
- Explain how a hash function turns a key into an array index.
- Explain what a collision is and how chaining resolves it.
- Explain what load factor is and why resizing keeps lookups fast.
- State precisely what assumption ‘O(1) average’ rests on, and how it fails.
Study route: read the mechanism, run the lab, then attempt the independent task before opening the hint.
1. Why Do Hash Maps Exist? (Real-World Motivation)
Imagine a physical Coat Check Room at a concert hall:
Guest gives Name ("Alice") ---> Coat Check Attendant (Hash Function)
|
v
Slot Number #4 (Bucket)
[ Alice's Coat ]
- In an Array, you can only retrieve data if you already know a numeric index like
arr[4]. - But what if your “index” is a person’s name (
"Alice"), a user ID ("usr_99"), or an email address?
A Hash Map acts like that coat check attendant: it takes any arbitrary key, transforms it into a numeric slot number, and retrieves the value instantly without searching through every item!
Terms used with hash maps
-
Hash map: This is a structure that stores pairs of things, so you can look one up by the other almost instantly. It is also called a hash table, a dictionary or
dictin Python, a map in C++ and Java, and an object in JavaScript. -
Key: This is the thing you look something up by — a username, a product code, a word. Keys must be unique within the map, and storing a pair with an existing key overwrites the old value.
-
Value: This is the thing stored against a key — the user’s profile, the product’s price. Values have no restrictions at all; they can repeat freely.
-
Hash function: This is a function that takes a key and returns a large integer. The same key always produces the same integer, and different keys usually produce different ones. It is what turns “look up this word” into “go to this array position”.
-
Bucket: This is one slot in the underlying array where entries are kept. The hash function’s job is to decide which bucket a key belongs in, usually by taking the hash value modulo the number of buckets.
-
Collision: This is when two different keys end up in the same bucket. Collisions are not a bug and cannot be avoided — there are more possible keys than buckets, so some must share. The design question is never how to prevent them, only how to handle them.
-
Chaining: This is one way of handling collisions. Each bucket holds a small list of all the entries that landed there, and a lookup walks that short list.
-
Open addressing: This is the other way. When a bucket is taken, the entry goes into some other bucket found by a fixed rule — the simplest being “try the next one along”, which is called linear probing.
-
Load factor: This is how full the map is: the number of stored entries divided by the number of buckets, written . As it rises, collisions become more common and lookups slow down.
-
Rehashing: This is what happens when the load factor gets too high. The map allocates a larger bucket array and recomputes the bucket for every existing entry, because the bucket depends on the array size. It is and it is why a hash map’s excellent average performance is amortised rather than guaranteed.
3. How a Hash Map Works (The 3-Step Pipeline)
When you write map["apple"] = 100, the Hash Map executes three fast steps:
1. Pass Key through Hash Function:
hash("apple") -> 2,166,136,261
2. Map Large Integer to Bucket Array Index (using Modulo %):
index = 2,166,136,261 % 8 (capacity) -> 5
3. Store Key-Value Pair in Bucket #5:
bucket[5] = ("apple", 100)
Bucket Array:
Slot 0: None
Slot 1: None
...
Slot 5: ("apple", 100) <-- Direct O(1) Access!
4. Handling Collisions (What Happens When Keys Clash?)
Because there are infinitely many possible strings/keys but a finite number of bucket slots, two different keys will eventually hash to the same bucket index. This is called a Collision.
Computer scientists use two primary strategies to resolve collisions:
Strategy 1: Separate Chaining (Linked Lists in Buckets)
Each bucket slot holds a small list of pairs. When a collision occurs, the new pair is appended to that bucket’s list.
Bucket 5: [ ("apple", 100) ] -> [ ("grape", 250) ] -> None
- Lookup Process: Hash to bucket #5, then walk the short list to find the matching key.
- Used by: Java
HashMap.
Strategy 2: Open Addressing (Probing for Next Available Slot)
All entries live directly in the flat array. When a slot is occupied, the table probes (scans) for the next open slot using a rule (e.g. check slot ).
Bucket 5: ("apple", 100)
Bucket 6: ("grape", 250) <-- Probed to next slot because Slot 5 was full!
Comparison of Collision Strategies
| Feature | Separate Chaining | Open Addressing |
|---|---|---|
| Storage Mechanism | Bucket contains a pointer to a list node. | Everything lives in one flat array. |
| Cache Behavior | Poor (list nodes scattered on heap). | Excellent (sequential array probing). |
| Max Load Factor | Can exceed (lists grow infinitely). | Must stay (fails when full). |
| Deletion Mechanism | Simple node removal from list. | Requires Tombstone markers so probe chains aren’t broken. |
| Modern Adoption | Textbook classic. | Python dict, Rust HashMap, C++ flat_map. |
5. Load Factor & Dynamic Resizing
As more items are added to a Hash Map, the buckets fill up and collisions become frequent. Left unchecked, lookups would slow down to linear scans.
To prevent this, Hash Maps maintain a Load Factor Threshold (typically ):
When :
- Allocate a new bucket array with double the capacity ().
- Re-hash every existing key into the new bucket array.
- Free the old array.
Because resizing happens exponentially rarely, Hash Map operations are Amortized .
6. Hash Sets (Instant Membership Checks)
A Hash Set is simply a Hash Map that stores only Keys without Values.
It answers one specific question instantly: “Have I seen this item before?”
# BAD: O(n) scan inside an O(n) loop = O(n²) total time
seen_list = []
for item in items:
if item in seen_list: # Scans entire list element-by-element!
print("Duplicate")
# GOOD: O(1) membership check inside an O(n) loop = O(n) total time
seen_set = set()
for item in items:
if item in seen_set: # Instant O(1) hash lookup!
print("Duplicate")TIP
The Golden Optimizations Rule: Replacing a
Listwith aSetfor membership testing is the single most common speedup in software engineering!
7. Trade-Offs: What Hash Maps Give Up to Buy
Hash Maps are extraordinarily fast, but they come with trade-offs:
- Destroys Order: Hashing scrambles keys across memory. A standard Hash Map cannot tell you the minimum key, maximum key, or display keys in sorted order.
- No Range Queries: You cannot query “all keys between 10 and 50” without scanning every entry in the map (). (For range queries, use a Binary Search Tree or B+ Tree).
- Keys Must Be Immutable: If a key changes its internal data after being inserted into a dict, its hash changes, rendering the item permanently lost inside the table! (In Python, lists cannot be keys, but immutable tuples can).
8. Summary of Complexity
| Operation | Average Time | Worst-Case Time (Hash Flooding / Collisions) |
|---|---|---|
Lookup (map[key]) | ||
Insert (map[key] = val) | Amortized | |
Delete (del map[key]) | ||
| Space Complexity |
The hash map ADT
A hash map answers one question extremely well: “what value did I store under this key?” It answers almost nothing else.
-
put(key, value)— Storesvalueunderkey, replacing any value already there. on average, in the worst case. -
get(key)— Returns the value stored underkey, or reports that there is none. on average. -
contains(key)— Returns whether the key is present. on average. A hash set is simply a hash map that stores keys and no values, exposing only this operation andadd. -
delete(key)— Removes the pair. on average. -
size()— How many pairs are stored. . -
keys(),values(),items()— Return everything, in no guaranteed order. .
What a hash map cannot do, and why
This list is short but decisive, and each absence follows from the same cause: hashing deliberately destroys order. A good hash function scatters similar keys to unrelated buckets — that scattering is what avoids collisions — and in scattering it throws away every relationship between keys.
So a hash map cannot answer:
- “What is the smallest key?” — the smallest key is in an arbitrary bucket. You would have to check all . A heap or a balanced tree answers this in or .
- “Which keys fall between 100 and 200?” — a range query. Nearby keys are nowhere near each other in memory. A B-tree answers this efficiently, which is exactly why databases index with B-trees rather than hash tables.
- “What comes after this key?” — there is no “after”. The order you get from iterating is an artefact of the bucket layout.
NOTE
Python’s
dictdoes preserve insertion order, as of Python 3.7. That is a guarantee about the order you added things, not about sorted order, and it comes from an extra list kept alongside the buckets. It does not give you any of the three operations above.
The average-case asterisk. Every above says “on average”. With a bad hash function, or an attacker deliberately choosing keys that collide, every entry can land in one bucket and lookups degrade to . That attack is real and has a name — a hash collision denial-of-service — and it is why languages now randomise their hash seed at startup.
Implementation - complete runnable example
Runnable example: save as hash_maps_lab.py and run python3 hash_maps_lab.py. Standard library only; writes no files. Everything is counted rather than timed, so your output will match this exactly.
"""Hash maps: a hash table with chaining, built from an array.
Shows where O(1) average comes from, and exactly how it degrades."""
class HashMap:
"""Separate chaining: an array of buckets, each holding a list of pairs."""
def __init__(self, capacity=8, hash_fn=None, max_load=0.75):
self.capacity, self.size = capacity, 0
self.buckets = [[] for _ in range(capacity)]
self.hash_fn = hash_fn or (lambda k: hash(k))
self.max_load, self.probes, self.resizes = max_load, 0, 0
def _index(self, key):
return self.hash_fn(key) % self.capacity
def put(self, key, value):
i = self._index(key)
for pair in self.buckets[i]:
self.probes += 1
if pair[0] == key:
pair[1] = value
return
self.buckets[i].append([key, value])
self.size += 1
if self.size / self.capacity > self.max_load:
self._resize()
def get(self, key, default=None):
for pair in self.buckets[self._index(key)]:
self.probes += 1
if pair[0] == key:
return pair[1]
return default
def _resize(self):
"""Rehash everything into a bigger array -- keeps chains short."""
old = self.buckets
self.capacity *= 2
self.buckets = [[] for _ in range(self.capacity)]
self.resizes += 1
for bucket in old:
for k, v in bucket:
self.buckets[self._index(k)].append([k, v])
def chain_lengths(self):
return [len(b) for b in self.buckets]
if __name__ == "__main__":
print("A GOOD HASH -- keys spread evenly across buckets")
m = HashMap(hash_fn=lambda k: k * 2654435761) # Knuth multiplicative
for i in range(1000):
m.put(i, i * i)
lens = m.chain_lengths()
print(f" 1000 keys, capacity {m.capacity}, {m.resizes} resizes")
print(f" load factor {m.size / m.capacity:.2f}")
print(f" chain lengths: min {min(lens)}, max {max(lens)}, "
f"mean {sum(lens)/len(lens):.2f}")
m.probes = 0
for i in range(1000):
m.get(i)
print(f" 1000 successful lookups cost {m.probes:,} probes "
f"({m.probes/1000:.2f} per lookup)")
print(" -> a short, bounded chain is why lookup is O(1) on AVERAGE.")
print()
print("A TERRIBLE HASH -- every key lands in the same bucket")
bad = HashMap(hash_fn=lambda k: 0)
for i in range(200):
bad.put(i, i)
lens = bad.chain_lengths()
print(f" 200 keys, capacity {bad.capacity}")
print(f" chain lengths: min {min(lens)}, max {max(lens)}")
before = bad.probes
bad.get(199)
print(f" one lookup of the last key cost {bad.probes - before} probes")
print(" -> the hash map has degenerated into a linked list: O(n).")
print(" 'O(1) average' assumes the hash SPREADS keys. It is an")
print(" assumption about your data, not a guarantee.")
print()
print("LOAD FACTOR AND RESIZING")
print(f" {'keys':>6s} {'capacity':>9s} {'load':>6s} {'resizes':>8s}")
m2 = HashMap(hash_fn=lambda k: k * 2654435761)
for n in (1, 10, 100, 1000):
while m2.size < n:
m2.put(m2.size, 0)
print(f" {m2.size:6d} {m2.capacity:9d} {m2.size/m2.capacity:6.2f} {m2.resizes:8d}")
print(" -> capacity grows to keep the load factor under 0.75, which")
print(" keeps the average chain short. Resizing is the cost.")
good = HashMap(hash_fn=lambda k: k * 2654435761)
for i in range(500): good.put(i, i)
assert max(good.chain_lengths()) <= 5, "a good hash keeps chains short"
assert max(bad.chain_lengths()) == 200, "a constant hash puts everything in one chain"
assert good.get(499) == 499 and good.get(9999) is None
good.put(1, "changed")
assert good.get(1) == "changed" and good.size == 500
print()
print("hash_maps_lab: passed")Expected output:
A GOOD HASH -- keys spread evenly across buckets
1000 keys, capacity 2048, 8 resizes
load factor 0.49
chain lengths: min 0, max 1, mean 0.49
1000 successful lookups cost 1,000 probes (1.00 per lookup)
-> a short, bounded chain is why lookup is O(1) on AVERAGE.
A TERRIBLE HASH -- every key lands in the same bucket
200 keys, capacity 512
chain lengths: min 0, max 200
one lookup of the last key cost 200 probes
-> the hash map has degenerated into a linked list: O(n).
'O(1) average' assumes the hash SPREADS keys. It is an
assumption about your data, not a guarantee.
LOAD FACTOR AND RESIZING
keys capacity load resizes
1 8 0.12 0
10 16 0.62 1
100 256 0.39 5
1000 2048 0.49 8
-> capacity grows to keep the load factor under 0.75, which
keeps the average chain short. Resizing is the cost.
hash_maps_lab: passed
9. Check Your Understanding (University Self-Assessment)
-
Question: Why are Python
lists invalid as dictionary keys (TypeError: unhashable type), whiletuples are valid?-
Click for Answer
Answer: Lists are mutable (their contents can change). If a key's contents change, its hash value changes, breaking the table's ability to locate it. Tuples are immutable and cannot change after creation.
-
-
Question: What is the difference between a Hash Map and a Balanced Binary Search Tree (BST)? When would you prefer a BST?
-
Click for Answer
Answer: A Hash Map provides faster average lookups (O(1) vs O(log n)), but destroys order. You prefer a BST when you need keys stored in sorted order or need to perform range queries (e.g. find all keys between X and Y).
-
-
Question: If a Hash Map has 70 entries and 100 bucket slots, what is its Load Factor? What action will the Hash Map take if 10 more entries are added?
-
Click for Answer
Answer: The Load Factor is 0.7 (70/100). Adding 10 more entries brings the load factor to 0.8, crossing the 0.7 threshold and triggering an automatic capacity resize (doubling buckets to 200) and re-hashing.
-
Practice - independent task
Implement open addressing with linear probing, as an alternative to chaining.
- Store entries directly in the bucket array; on collision, try the next slot.
- Implement
put,getand - the hard one -delete. - Deletion is the trap. Removing an entry can break the probe chain for later keys. Discover this yourself: insert three keys that collide, delete the middle one, then look up the third.
- Fix it with a tombstone marker.
- Compare probe counts against the chaining version at load factors 0.5 and 0.9.
Done when: your open-addressed map passes the delete-then-lookup case, and you can say which approach degrades worse at high load factor and why.
Hint - open only after an attempt
If keys A, B and C all hash to slot 5 and land in slots 5, 6 and 7, then deleting B leaves slot 6 empty. A lookup for C probes 5, finds A (not C), probes 6, finds empty, and concludes C is absent - even though C is sitting in slot 7.A tombstone marks the slot as "deleted, keep probing". The cost is that tombstones accumulate and must be cleared during a resize.
Before moving on
You are done with this module when you can, closed-book:
- Explain how a hash maps a key to a bucket index.
- Explain chaining, and what happens when every key collides.
- Explain load factor and why exceeding it triggers a resize.
- State what ‘O(1) average’ assumes about your data and your hash function.
Recap: A hash map turns a key into an array index by hashing, giving direct access rather than a search. Collisions are inevitable, and chaining stores colliding entries in a list per bucket. Keeping the load factor low - by resizing and rehashing - keeps chains short, which is where average O(1) comes from. That average assumes the hash spreads keys evenly; a degenerate hash puts everything in one chain and lookup becomes O(n).
Next: Linked Lists - the non-contiguous alternative, and the opposite bet about which operation should be cheap.
Related Modules
- Arrays — The bucket array foundation underneath
- Dynamic Arrays — Amortized resizing principles
- Trees — Binary Search Trees for ordered key-value storage
- Tries — Prefix trees for string key searches
Software engineering
Infrastructure & security
Computer science
Hardware & engineering