Hash Function Internals and Collision Handling
Understand how Python hashes objects, how open addressing and chaining resolve collisions, and why average-case O(1) can degrade to O(n).
Hash Function Internals and Collision Handling is a free DSA Interview Prep lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
What Is a Hash Map?
A hash map (dictionary in Python) maps keys to values using a hash function that converts any key into an integer index into an underlying array. An ideal hash function spreads keys uniformly across the array, enabling O(1) average-case lookup, insertion, and deletion. The underlying array is called the hash table or bucket array.
In Python, dict is a highly optimised hash map. Understanding its internals helps you reason about worst-case behaviour and choose appropriate keys.
# Python dict is a hash map
hm = {}
hm['alice'] = 95
hm['bob'] = 87
hm['carol'] = 91
print(hm['alice']) # O(1) lookup: 95
print('bob' in hm) # O(1) membership: True
del hm['bob'] # O(1) deletion
print(hm) # {'alice': 95, 'carol': 91}Hash Functions and the __hash__ Method
Python calls __hash__(key) to compute an integer from the key, then takes that integer modulo the table size to find the bucket index. Built-in types like int, str, and tuple have fast built-in hash implementations. list and dict are not hashable (they are mutable, and mutating them would invalidate any stored hash).
A good hash function distributes keys uniformly, is deterministic, and is fast to compute. Python's string hash randomises across runs (a security feature) — use PYTHONHASHSEED=0 to disable for reproducibility in testing.
# Built-in hash in Python
print(hash(42)) # integer hashes to itself (CPython)
print(hash('hello')) # string hash (randomised per run)
print(hash((1, 2, 3))) # tuple hash: depends on contents
# Unhashable types
try:
hash([1, 2, 3]) # lists are mutable -> not hashable
except TypeError as e:
print('Error:', e)
# Custom class: define __hash__ and __eq__
class Point:
def __init__(self, x, y): self.x = x; self.y = y
def __hash__(self): return hash((self.x, self.y))
def __eq__(self, other): return self.x == other.x and self.y == other.y
points = {Point(1, 2): 'A', Point(3, 4): 'B'}
print(points[Point(1, 2)]) # 'A'Collisions: When Two Keys Hash to the Same Bucket
A collision occurs when two distinct keys produce the same bucket index. Collisions are inevitable (pigeonhole principle: infinitely many keys, finitely many buckets). Two standard resolution strategies are chaining and open addressing. Python uses a variant of open addressing with pseudo-random probing.
Chaining stores a linked list (or dynamic array) at each bucket; all keys colliding at that bucket form a chain. Open addressing seeks the next empty bucket according to a probe sequence.
# Simplified chaining hash map
class ChainingHashMap:
def __init__(self, capacity=8):
self.capacity = capacity
self.buckets = [[] for _ in range(capacity)]
def _idx(self, key):
return hash(key) % self.capacity
def put(self, key, val):
bucket = self.buckets[self._idx(key)]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, val)
return
bucket.append((key, val))
def get(self, key):
for k, v in self.buckets[self._idx(key)]:
if k == key:
return v
return None
hm = ChainingHashMap()
hm.put('a', 1); hm.put('b', 2)
print(hm.get('a')) # 1
print(hm.get('c')) # NoneOpen Addressing: Linear Probing
In linear probing, when a collision occurs at index i, the map checks i+1, i+2, ... (wrapping around) until an empty slot is found. Lookup must probe the same sequence to find the key. Deletions require a 'tombstone' marker rather than clearing the slot, to avoid breaking the probe chain.
Clustering is the main drawback: once a cluster of filled slots forms, future insertions into that area extend the cluster, degrading performance toward O(n).
class LinearProbingHashMap:
DELETED = object() # tombstone sentinel
def __init__(self, capacity=8):
self.capacity = capacity
self.keys = [None] * capacity
self.vals = [None] * capacity
self.size = 0
def _probe(self, key):
idx = hash(key) % self.capacity
while self.keys[idx] is not None and self.keys[idx] != key:
idx = (idx + 1) % self.capacity
return idx
def put(self, key, val):
idx = self._probe(key)
if self.keys[idx] is None:
self.size += 1
self.keys[idx] = key
self.vals[idx] = val
def get(self, key):
idx = self._probe(key)
if self.keys[idx] == key:
return self.vals[idx]
return None
hm = LinearProbingHashMap()
hm.put('x', 10); hm.put('y', 20)
print(hm.get('x')) # 10Load Factor and Resizing
The load factor is the ratio of stored entries to total capacity: α = n/m. As α increases, collision probability rises and performance degrades. Python's dict resizes (doubles capacity) when the load factor exceeds about 2/3. Resizing rehashes all existing entries into the new larger table — an O(n) operation that occurs infrequently, keeping amortised insert cost at O(1).
import sys
d = {}
prev_size = sys.getsizeof(d)
for i in range(30):
d[i] = i
new_size = sys.getsizeof(d)
if new_size != prev_size:
print(f'Resized at n={i+1}: {prev_size} -> {new_size} bytes')
prev_size = new_sizeAverage O(1) vs Worst-Case O(n)
Under a good hash function, collisions are rare and expected chain length is constant regardless of n. Average-case lookup, insert, and delete are therefore O(1). However, a worst-case scenario — for example, a deliberately adversarial input that maps all keys to the same bucket — degrades all operations to O(n). Python's randomised hash seed mitigates this attack but does not eliminate worst-case theoretically.
For interview analysis, say 'O(1) average, O(n) worst case due to collisions'.
# Python randomised hash seed prevents worst-case hash-flooding
import os
print('PYTHONHASHSEED:', os.environ.get('PYTHONHASHSEED', 'random'))
# By default Python randomises the hash of strings each run
# This prevents an attacker from crafting keys that all collide
# To reproduce results in testing: PYTHONHASHSEED=0 python script.pyPython dict vs defaultdict vs Counter
Python provides three hash map variants worth knowing. dict is the general-purpose map; accessing a missing key raises KeyError. defaultdict(factory) returns a default value on missing key access (useful for collecting lists or counting). Counter is a specialised subclass for counting hashable objects; it also supports arithmetic operations between counters.
from collections import defaultdict, Counter
# defaultdict for grouping
groups = defaultdict(list)
for word in ['apple', 'ant', 'banana', 'bee', 'avocado']:
groups[word[0]].append(word)
print(dict(groups))
# {'a': ['apple','ant','avocado'], 'b': ['banana','bee']}
# Counter for frequency
c = Counter('abracadabra')
print(c.most_common(3)) # [('a',5),('b',2),('r',2)]
print(c['a'] - Counter('aa')['a']) # counter subtractionHash Map vs Hash Set
A hash set stores only keys (no associated values), supporting O(1) membership testing, insert, and delete. Python's set is a hash set. Use a set when you only need to answer 'does this element exist?' without storing associated data. Use a dict when you need to associate values (counts, results, etc.) with keys.
# set for membership testing
visited = set()
for node in [1, 3, 5, 3, 7, 1]:
if node not in visited:
print('New node:', node)
visited.add(node)
# Set operations: union, intersection, difference
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
print('Union:', A | B) # {1,2,3,4,5,6}
print('Intersection:', A & B) # {3,4}
print('Difference:', A - B) # {1,2}Implementing a Hash Map from Scratch (Interview Version)
Interviewers sometimes ask you to implement a basic hash map. The key components: a fixed-size array of buckets (use 16 or 1024), each bucket is a list of (key, value) pairs for chaining, a hash function (use Python's built-in hash % capacity), and resize when the load factor exceeds 0.7. Mentioning resize and load factor proactively demonstrates depth of knowledge.
class HashMap:
def __init__(self, capacity=16):
self.capacity = capacity
self.size = 0
self.buckets = [[] for _ in range(capacity)]
def _hash(self, key):
return hash(key) % self.capacity
def put(self, key, val):
b = self.buckets[self._hash(key)]
for i, (k, v) in enumerate(b):
if k == key:
b[i] = (key, val)
return
b.append((key, val))
self.size += 1
if self.size / self.capacity > 0.7:
self._resize()
def get(self, key, default=None):
for k, v in self.buckets[self._hash(key)]:
if k == key:
return v
return default
def _resize(self):
old = self.buckets
self.capacity *= 2
self.buckets = [[] for _ in range(self.capacity)]
self.size = 0
for bucket in old:
for k, v in bucket:
self.put(k, v)
hm = HashMap()
for i in range(20):
hm.put(i, i * 2)
print(hm.get(10)) # 20
print(hm.capacity) # should have resizedWhen Hash Maps Fail: Unhashable Keys
Only hashable objects can be dictionary keys. In Python, an object is hashable if it has a __hash__ method and an __eq__ method, and its hash value does not change during its lifetime. Lists, sets, and dicts are mutable and therefore not hashable. Tuples and frozensets are hashable alternatives to lists and sets when used as keys.
A common interview trap: grouping anagrams requires using a sorted tuple (not a sorted list) as the dict key.
from collections import defaultdict
def groupAnagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # tuple is hashable; list is not
groups[key].append(s)
return list(groups.values())
print(groupAnagrams(['eat','tea','tan','ate','nat','bat']))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]Summary: Hash Map Complexity
Hash maps provide O(1) average-case for insert, delete, and lookup — the foundation of many optimal interview solutions. The key assumptions: a good hash function distributes keys uniformly, the load factor stays bounded (resizing maintains this), and key objects are immutable and hashable. When these assumptions hold, hash maps convert O(n) linear scans to O(1) lookups, enabling solutions like two-sum in O(n) instead of O(n²).
Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: a hash map maps keys to bucket indices using a hash function and achieves O(1) average-case operations, collisions are resolved by chaining (linked list per bucket) or open addressing (probing for next empty slot), and only immutable, hashable objects can be dictionary keys — use tuples instead of lists when a sequence key is needed. Next up we solve two-sum and its many interview variants.
Frequently asked questions
Is the “Hash Function Internals and Collision Handling” lesson free?
Yes — the full text of “Hash Function Internals and Collision Handling” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Hash Function Internals and Collision Handling”?
Understand how Python hashes objects, how open addressing and chaining resolve collisions, and why average-case O(1) can degrade to O(n). You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Hash Function Internals and Collision Handling” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Hash Function Internals and Collision Handling
- Two-Sum and Its Many Variants
- Frequency Counting and Grouping
- Longest Consecutive Sequence and LRU Cache