Introduction to Designing a HashMap in Python
A HashMap (also known as a hash table or dictionary) is one of the most fundamental data structures in computer science. It provides average O(1) time complexity for insertions, deletions, and lookups, making it incredibly efficient for storing key-value pairs. While Python ships with a built-in dict type that implements a highly optimized hash map, understanding how to build one from scratch is a rite of passage for every developer.
The "Design a HashMap" problem is a popular coding interview question (LeetCode 706) that asks you to implement a hash map without using the built-in hash table libraries. This tutorial walks you through the entire process — from understanding the underlying mechanics to writing production-quality Python code.
What Is a HashMap?
A HashMap is a data structure that maps keys to values using a technique called hashing. When you insert a key-value pair, the hash map applies a hash function to the key, which converts it into an integer. This integer is then used as an index into an underlying array (often called a "bucket array"). The value is stored at that index.
The key insight is that hashing allows us to skip linear searches. Instead of scanning every element, we compute where the element should be and go directly there. This is what gives hash maps their characteristic O(1) average-case performance.
Core Operations
put(key, value)— Insert or update a key-value pair.get(key)— Retrieve the value associated with a key, or -1 if not found.remove(key)— Delete a key-value pair from the map.
Why Designing a HashMap Matters
You might wonder why you should reinvent the wheel when Python's dict already exists. There are several compelling reasons:
- Interview readiness: Tech companies frequently ask candidates to implement hash maps to test their understanding of data structures, hashing, and collision resolution.
- Deep understanding: Building one yourself forces you to confront edge cases like hash collisions, load factors, and resizing — concepts you'll use every day as a developer.
- Customization: In specialized scenarios (caching systems, bounded maps, concurrent access), you may need a hash map with custom behavior that built-in types don't offer.
- Foundation for advanced structures: Hash sets, LRU caches, and bloom filters all build on hash map principles.
Understanding Hash Collisions
No matter how good your hash function is, collisions are inevitable. A collision occurs when two different keys hash to the same index. There are two primary strategies for handling collisions:
1. Separate Chaining
Each bucket in the array holds a linked list (or another collection) of all key-value pairs that hash to that index. When a collision happens, the new entry is simply appended to the list at that bucket. Lookups require scanning the list, but with a good hash function, lists remain short.
2. Open Addressing
When a collision occurs, the hash map probes for the next available slot in the array using a strategy like linear probing, quadratic probing, or double hashing. This avoids the overhead of linked lists but complicates deletions and resizing.
For this tutorial, we'll use separate chaining because it's simpler to implement and reason about.
Step-by-Step Implementation
Let's build our HashMap incrementally. We'll start with a basic version using separate chaining with Python lists, then refine it.
Step 1: Setting Up the Structure
We begin by defining the class and choosing a fixed size for our bucket array. For the LeetCode problem, keys are integers in the range [0, 1000000], so we can use a simple modulo-based hash function.
class MyHashMap:
def __init__(self):
self.size = 1000
self.buckets = [[] for _ in range(self.size)]
def _hash(self, key):
return key % self.size
Here, self.buckets is a list of empty lists. Each inner list will hold tuples of (key, value) pairs that collide at the same index.
Step 2: Implementing put()
The put method must handle two cases: inserting a new key and updating an existing key. We hash the key to find the bucket, then scan that bucket to see if the key already exists.
def put(self, key, value):
index = self._hash(key)
bucket = self.buckets[index]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
If we find the key, we replace the tuple at that position. Otherwise, we append a new tuple to the bucket.
Step 3: Implementing get()
The get method returns the value for a given key, or -1 if the key doesn't exist.
def get(self, key):
index = self._hash(key)
bucket = self.buckets[index]
for k, v in bucket:
if k == key:
return v
return -1
Step 4: Implementing remove()
To remove a key, we locate its bucket and filter out the matching tuple.
def remove(self, key):
index = self._hash(key)
bucket = self.buckets[index]
for i, (k, v) in enumerate(bucket):
if k == key:
del bucket[i]
return
The Complete Basic Implementation
Putting it all together, here's the complete basic HashMap:
class MyHashMap:
def __init__(self):
self.size = 1000
self.buckets = [[] for _ in range(self.size)]
def _hash(self, key):
return key % self.size
def put(self, key, value):
index = self._hash(key)
bucket = self.buckets[index]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
def get(self, key):
index = self._hash(key)
bucket = self.buckets[index]
for k, v in bucket:
if k == key:
return v
return -1
def remove(self, key):
index = self._hash(key)
bucket = self.buckets[index]
for i, (k, v) in enumerate(bucket):
if k == key:
del bucket[i]
return
Testing the Implementation
hash_map = MyHashMap()
hash_map.put(1, 10)
hash_map.put(2, 20)
print(hash_map.get(1)) # Output: 10
print(hash_map.get(3)) # Output: -1
hash_map.put(2, 30) # Update existing key
print(hash_map.get(2)) # Output: 30
hash_map.remove(2)
print(hash_map.get(2)) # Output: -1
Advanced Implementation with Linked Lists
While using Python lists for buckets is convenient, a more traditional approach uses linked lists. This better demonstrates the classic hash map design and avoids the O(n) cost of list deletions.
class ListNode:
def __init__(self, key=-1, value=-1, next=None):
self.key = key
self.value = value
self.next = next
class MyHashMap:
def __init__(self):
self.size = 1000
self.buckets = [ListNode() for _ in range(self.size)]
def _hash(self, key):
return key % self.size
def put(self, key, value):
index = self._hash(key)
curr = self.buckets[index]
while curr.next:
if curr.next.key == key:
curr.next.value = value
return
curr = curr.next
curr.next = ListNode(key, value)
def get(self, key):
index = self._hash(key)
curr = self.buckets[index].next
while curr:
if curr.key == key:
return curr.value
curr = curr.next
return -1
def remove(self, key):
index = self._hash(key)
curr = self.buckets[index]
while curr.next:
if curr.next.key == key:
curr.next = curr.next.next
return
curr = curr.next
Each bucket is a dummy head node, which simplifies insertion and deletion logic by eliminating special cases for the first element. The put method traverses the list to find duplicates before appending. The remove method relinks the previous node to skip the deleted node.
Adding Dynamic Resizing
Our implementations so far use a fixed bucket count. As more elements are added, chains grow longer and performance degrades toward O(n). A production-quality hash map dynamically resizes when the load factor (ratio of elements to buckets) exceeds a threshold.
class DynamicHashMap:
def __init__(self, initial_capacity=16, load_factor=0.75):
self.capacity = initial_capacity
self.load_factor = load_factor
self.count = 0
self.buckets = [[] for _ in range(self.capacity)]
def _hash(self, key):
return hash(key) % self.capacity
def put(self, key, value):
index = self._hash(key)
bucket = self.buckets[index]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
self.count += 1
if self.count / self.capacity > self.load_factor:
self._resize()
def _resize(self):
old_buckets = self.buckets
self.capacity *= 2
self.buckets = [[] for _ in range(self.capacity)]
self.count = 0
for bucket in old_buckets:
for key, value in bucket:
self.put(key, value)
def get(self, key):
index = self._hash(key)
bucket = self.buckets[index]
for k, v in bucket:
if k == key:
return v
return -1
def remove(self, key):
index = self._hash(key)
bucket = self.buckets[index]
for i, (k, v) in enumerate(bucket):
if k == key:
del bucket[i]
self.count -= 1
return
When the load factor exceeds 0.75, we double the capacity and rehash all existing entries. This keeps chains short and maintains O(1) average performance. The amortized cost of resizing is O(1) per insertion because resizing happens infrequently relative to the number of operations.
Best Practices
- Choose an appropriate bucket count: A prime number of buckets can reduce collision clustering when keys have patterns. For interview problems, 1000 or 10000 is usually sufficient.
- Use a good hash function: Python's built-in
hash()function works well for most types. For custom objects, implement__hash__and__eq__consistently. - Handle collisions gracefully: Separate chaining is simple and robust. Open addressing can be faster but requires careful implementation of probing and deletion.
- Monitor load factor: Keep it below 0.75 for separate chaining. Resize proactively rather than waiting for severe degradation.
- Make keys immutable: If a key's hash value changes after insertion, the entry becomes unreachable. Use tuples, strings, or numbers as keys rather than mutable objects.
- Use dummy head nodes in linked list implementations: They eliminate edge cases when inserting or removing the first node in a chain.
- Consider thread safety: Python's
dictis not thread-safe for concurrent writes. If you need concurrency, use locks or a concurrent data structure.
Time and Space Complexity Analysis
Understanding the complexity of each operation is crucial for interviews and real-world design decisions:
- put(key, value): O(1) average, O(n) worst case (all keys collide to one bucket).
- get(key): O(1) average, O(n) worst case.
- remove(key): O(1) average, O(n) worst case.
- Space: O(n) where n is the number of stored key-value pairs.
With dynamic resizing, the worst case becomes extremely unlikely because the load factor is kept bounded. The amortized cost of put including resizing remains O(1).
Common Pitfalls to Avoid
- Forgetting to update existing keys: A common bug is always appending instead of checking for duplicates, leading to duplicate keys in the same bucket.
- Using mutable default arguments: Never write
[[]] * size— this creates references to the same list. Always use a list comprehension. - Ignoring hash distribution: If all keys map to the same bucket, your hash map degrades to a linked list. Test with diverse key sets.
- Not handling the empty case: Make sure
getandremovebehave correctly when the map is empty or the key doesn't exist.
Conclusion
Designing a HashMap from scratch is an excellent exercise that deepens your understanding of one of the most important data structures in software engineering. By implementing separate chaining with either Python lists or linked lists, you've seen how hashing, collision resolution, and dynamic resizing work together to deliver efficient key-value storage. The basic implementation handles the core operations cleanly, while the advanced versions with linked lists and dynamic resizing demonstrate how production-grade hash maps maintain performance under load. Whether you're preparing for a coding interview or building a custom data structure for a specialized use case, the principles covered here — choosing a good hash function, managing load factors, and handling collisions gracefully — will serve you well across countless programming challenges.