Introduction to Designing a HashSet in Python
A HashSet is one of the most fundamental data structures in computer science. It provides constant-time average complexity for insert, delete, and lookup operations, making it indispensable for solving a wide variety of algorithmic problems. In this tutorial, we will walk through how to design a HashSet from scratch in Python, without relying on the built-in set type. This is a classic interview question (LeetCode 705) and a great way to understand how hash-based data structures work under the hood.
What Is a HashSet?
A HashSet is a collection that stores unique elements and supports three core operations:
- Add: Insert a value into the set if it is not already present.
- Remove: Delete a value from the set if it exists.
- Contains: Check whether a value exists in the set.
The "Hash" part of the name comes from the use of a hash function that maps each value to an index in an underlying array. This mapping is what enables fast average-time operations.
Why Does It Matter?
Understanding how a HashSet works internally is crucial for several reasons. First, it deepens your knowledge of hashing, collisions, and load factors — concepts that appear in databases, caches, and distributed systems. Second, many coding interview questions assume you understand the internals of hash-based structures rather than just using them as black boxes. Finally, building your own HashSet teaches you how to handle edge cases such as collisions, resizing, and memory efficiency.
Core Concepts Behind a HashSet
The Hash Function
A hash function takes an input (in our case, an integer key) and returns an integer index within the bounds of our storage array. A simple and effective approach is to use the modulo operation:
def _hash(self, key):
return key % self.size
This ensures the index always falls within the range [0, size - 1]. For non-integer keys, you would first convert the key to an integer representation, but for this tutorial we will focus on integer keys, which is the standard version of the problem.
Collision Handling
Since multiple keys can map to the same index, we need a strategy to handle collisions. The two most common approaches are:
- Separate Chaining: Each bucket stores a list (or linked list) of all keys that hash to that index.
- Open Addressing: On collision, probe for the next available slot in the array.
In this tutorial, we will use separate chaining because it is simpler to implement and reason about.
Step-by-Step Implementation
Step 1: Define the Class and Constructor
We start by creating a class with an underlying array of buckets. Each bucket will be a list that holds the keys assigned to it.
class MyHashSet:
def __init__(self):
self.size = 1000
self.buckets = [[] for _ in range(self.size)]
Here we choose a fixed size of 1000 buckets. This is a reasonable starting point for a learning implementation. In production-grade hash sets, the size would dynamically grow as the number of elements increases.
Step 2: Implement the Hash Function
Next, we add a private helper method to compute the bucket index for a given key.
def _hash(self, key):
return key % self.size
This method is used by all three public operations to locate the correct bucket.
Step 3: Implement the Add Method
The add method inserts a key into the set. We first compute the bucket index, then check whether the key already exists in that bucket. If it does not, we append it.
def add(self, key):
bucket_index = self._hash(key)
bucket = self.buckets[bucket_index]
if key not in bucket:
bucket.append(key)
Checking for existence before appending ensures that we never store duplicate values, which is the defining property of a set.
Step 4: Implement the Remove Method
The remove method deletes a key from the set if it exists. We locate the bucket and remove the key from the list.
def remove(self, key):
bucket_index = self._hash(key)
bucket = self.buckets[bucket_index]
if key in bucket:
bucket.remove(key)
Using Python's built-in list.remove() is convenient, but note that it performs a linear scan. For larger buckets, a linked list or a more efficient structure would be preferable.
Step 5: Implement the Contains Method
The contains method returns True if the key is present in the set, and False otherwise.
def contains(self, key):
bucket_index = self._hash(key)
bucket = self.buckets[bucket_index]
return key in bucket
This is the simplest of the three operations because it only requires a lookup within the appropriate bucket.
Complete Implementation
Putting all the pieces together, here is the complete MyHashSet class:
class MyHashSet:
def __init__(self):
self.size = 1000
self.buckets = [[] for _ in range(self.size)]
def _hash(self, key):
return key % self.size
def add(self, key):
bucket_index = self._hash(key)
bucket = self.buckets[bucket_index]
if key not in bucket:
bucket.append(key)
def remove(self, key):
bucket_index = self._hash(key)
bucket = self.buckets[bucket_index]
if key in bucket:
bucket.remove(key)
def contains(self, key):
bucket_index = self._hash(key)
bucket = self.buckets[bucket_index]
return key in bucket
Testing the Implementation
Let us verify that our HashSet works correctly with a few operations:
hash_set = MyHashSet()
hash_set.add(1)
hash_set.add(2)
print(hash_set.contains(1)) # True
print(hash_set.contains(3)) # False
hash_set.add(2)
print(hash_set.contains(2)) # True
hash_set.remove(2)
print(hash_set.contains(2)) # False
The output matches our expectations: the set correctly adds, checks, and removes elements while preventing duplicates.
How to Use It in Practice
While you would typically use Python's built-in set in real projects, understanding this implementation helps you in several scenarios. For example, if you are working in a constrained environment where you cannot use built-in collections, or if you need a customized set with special behavior (such as bounded size or eviction policies), building your own is the way to go.
You can also extend this implementation to support additional operations like clear, size, or iteration:
def clear(self):
self.buckets = [[] for _ in range(self.size)]
def size_of(self):
return sum(len(bucket) for bucket in self.buckets)
def __iter__(self):
for bucket in self.buckets:
for key in bucket:
yield key
Best Practices
- Choose an appropriate bucket count: Too few buckets lead to long chains and degraded performance. Too many waste memory. A common rule of thumb is to keep the load factor (number of elements divided by number of buckets) below 0.75.
- Consider dynamic resizing: When the load factor exceeds a threshold, create a larger array and rehash all existing keys. This keeps average operations close to O(1).
- Use a good hash function: For integer keys, modulo works fine. For strings or complex objects, use a function that distributes keys uniformly to minimize collisions.
- Avoid storing duplicates: Always check for existence before adding. This is what makes a set different from a list.
- Handle edge cases: Consider what happens with negative keys, very large keys, or zero. The modulo operation handles these correctly in Python, but in other languages you may need extra care.
Adding Dynamic Resizing
For a more robust implementation, here is how you could add resizing when the load factor gets too high:
class MyHashSet:
def __init__(self):
self.size = 1000
self.count = 0
self.buckets = [[] for _ in range(self.size)]
def _hash(self, key, size=None):
if size is None:
size = self.size
return key % size
def _resize(self):
new_size = self.size * 2
new_buckets = [[] for _ in range(new_size)]
for bucket in self.buckets:
for key in bucket:
new_index = self._hash(key, new_size)
new_buckets[new_index].append(key)
self.size = new_size
self.buckets = new_buckets
def add(self, key):
bucket_index = self._hash(key)
bucket = self.buckets[bucket_index]
if key not in bucket:
bucket.append(key)
self.count += 1
if self.count / self.size > 0.75:
self._resize()
def remove(self, key):
bucket_index = self._hash(key)
bucket = self.buckets[bucket_index]
if key in bucket:
bucket.remove(key)
self.count -= 1
def contains(self, key):
bucket_index = self._hash(key)
bucket = self.buckets[bucket_index]
return key in bucket
This version doubles the number of buckets whenever the load factor exceeds 0.75, ensuring that operations remain efficient as the set grows.
Conclusion
Designing a HashSet from scratch in Python is an excellent exercise that reinforces your understanding of hashing, collision resolution, and amortized complexity. By using separate chaining with a fixed array of buckets, we built a working set that supports add, remove, and contains operations in average O(1) time. We also explored best practices such as dynamic resizing and load factor management, which are essential for building production-quality hash-based data structures. While Python's built-in set is highly optimized and should be your default choice in real applications, knowing how to implement one yourself gives you the confidence and depth of knowledge needed to tackle more complex data structure problems and technical interviews.