Building a HashMap
You'll learn to
- -Implement put, get, delete, and contains using separate chaining
- -Explain load factor and why real hashmaps resize as they fill up
- -Reason about the amortized average-case O(1) cost of hashmap operations
This chapter assembles the last chapter's pieces into a complete, working HashMap: a fixed array of buckets, the hash-and-modulo step to choose one, and a short linear scan within that one bucket to handle whatever collisions land there.
The Bucket Array
class HashMap:
def __init__(self, capacity=8):
self._capacity = capacity
self._buckets = [[] for _ in range(capacity)]
self._size = 0
def _bucket_index(self, key):
return hash(key) % self._capacityput, get, delete, and contains
def put(self, key, value):
index = self._bucket_index(key)
bucket = self._buckets[index]
for i, (existing_key, _) in enumerate(bucket):
if existing_key == key:
bucket[i] = (key, value) # overwrite an existing key
return
bucket.append((key, value)) # new key - append to the chain
self._size += 1
if self.load_factor() > 0.75:
self._resize()
def get(self, key):
bucket = self._buckets[self._bucket_index(key)]
for existing_key, value in bucket:
if existing_key == key:
return value
raise KeyError(key)
def delete(self, key):
bucket = self._buckets[self._bucket_index(key)]
for i, (existing_key, _) in enumerate(bucket):
if existing_key == key:
del bucket[i]
self._size -= 1
return
raise KeyError(key)
def contains(self, key):
bucket = self._buckets[self._bucket_index(key)]
return any(existing_key == key for existing_key, _ in bucket)
def size(self):
return self._size
def load_factor(self):
return self._size / self._capacityEvery one of put, get, delete, and contains follows the same two-step shape: hash the key once to find the right bucket (O(1)), then scan only that one bucket rather than the whole table. As long as buckets stay short, that scan stays close to free, which is why the overall operation is described as average-case O(1). Not because there is zero scanning, but because the scan only ever touches a tiny slice of the data.
Load Factor & Resizing
Load factor is the number of stored entries divided by the number of buckets, effectively the average chain length. As it climbs past roughly 0.7 to 0.75, buckets routinely start holding multiple entries, and the per-bucket scan stops being negligible. Real hashmaps, including Python's own dict, monitor load factor and, once it crosses a threshold, allocate a larger bucket array (commonly double the previous size) and rehash every existing key into it. That rehashing pass is O(n), but it happens only occasionally. Amortized across all the puts that led up to it, it barely dents the average-case O(1).
Python's real dict implementation is far more optimized than this, open addressing rather than chaining, plus guaranteed insertion-order preservation since Python 3.7, but the average-case O(1), resize-on-load-factor idea built here is the same mental model underneath every hashmap you will ever reach for.
Interview Signal is part of Pro
See a real weak answer next to a real strong one for this exact topic.
Quiz is part of Pro
Test what you just read with a short quiz, and bank the XP.
Level 4: HashMap from Scratch asks you to implement exactly this, a HashMap class with put, get, delete, contains, size, and load_factor, using separate chaining for collision resolution. Build it directly from the class above.