Quick answer: A HashSet stores unique hashable keys and supports add, remove, and contains operations. Python’s built-in set is the correct production choice for normal membership and uniqueness; implementing buckets yourself is mainly an educational exercise that demonstrates hashing, collision handling, and the requirement that keys be hashable.
A HashSet stores unique keys and supports three core operations: add(), remove(), and contains(). Python already has a built-in set type for real projects, but designing a HashSet from scratch is a useful exercise because it shows how hashing, buckets, duplicates, and membership checks fit together.
The official Python documentation covers set and frozenset types, and the Python tutorial has a concise section on sets. A custom HashSet is mainly for learning or interview-style problems where built-in hash tables are not allowed.
Use Python’s built-in set first
For normal code, prefer set. It is fast, readable, and already handles hashing, collisions, resizing, and duplicates.
seen = set()
seen.add(10)
seen.add(20)
seen.add(10)
print(10 in seen)
print(30 in seen)
seen.remove(20)
print(seen)
The duplicate 10 is stored only once. If your goal is removing duplicate list items, the convert list to set guide covers the direct approach.
Design the interface
A simple HashSet class should expose a small interface. The caller should not need to know whether the implementation uses direct addressing, buckets, or another storage strategy.
class MyHashSet:
def add(self, key):
raise NotImplementedError
def remove(self, key):
raise NotImplementedError
def contains(self, key):
raise NotImplementedError
This interface mirrors common HashSet exercises. The details can change later without changing the calling code. That is the main reason to wrap the behavior in a class instead of scattering list operations around a program.
Keep the public methods boring and predictable. add() should not create duplicates, remove() should be safe for missing keys, and contains() should return a Boolean result. That small contract makes the structure easy to test and easy to replace with a built-in set later.
Direct addressing for small keys
If keys are non-negative integers in a known range, direct addressing is the simplest design. Create a list of Boolean flags and use the key as the index.
class SmallHashSet:
def __init__(self, size=1001):
self._data = [False] * size
def add(self, key):
self._data[key] = True
def remove(self, key):
self._data[key] = False
def contains(self, key):
return self._data[key]
values = SmallHashSet()
values.add(42)
print(values.contains(42))
values.remove(42)
print(values.contains(42))
This is fast and easy, but it only works when the key range is small and known. It wastes memory when the largest key is huge but only a few keys are stored. It also needs bounds checks if callers may pass negative keys or keys beyond the chosen size.
Use buckets for a general design
A bucket-based HashSet maps each key to a bucket index. Each bucket stores the keys that land at that index. Multiple keys can share a bucket, so each bucket is a small list.
class BucketHashSet:
def __init__(self, bucket_count=8):
self._buckets = [[] for _ in range(bucket_count)]
def _bucket(self, key):
return hash(key) % len(self._buckets)
def add(self, key):
bucket = self._buckets[self._bucket(key)]
if key not in bucket:
bucket.append(key)
def remove(self, key):
bucket = self._buckets[self._bucket(key)]
if key in bucket:
bucket.remove(key)
def contains(self, key):
bucket = self._buckets[self._bucket(key)]
return key in bucket
values = BucketHashSet()
values.add("python")
print(values.contains("python"))
The hash() value decides the bucket. The modulo operation keeps the index inside the bucket list. The if key not in bucket check prevents duplicates.
Average performance is good when keys are spread across buckets. If too many keys land in the same bucket, operations slow down because the bucket list must be scanned. Real hash tables resize when they get crowded. This learning version keeps the code small, so the resizing step is left out intentionally.
Handle collisions
A collision happens when two different keys map to the same bucket. Chaining stores both keys in that bucket and then uses equality checks inside the bucket.
values = BucketHashSet(bucket_count=2)
for key in [12, 42, 73, 12]:
values.add(key)
print(values.contains(42))
print(values.contains(99))
print(values._buckets)
Small bucket counts make collisions easier to see, but they are not ideal for performance. A production hash table grows and rebalances over time. For this learning version, the bucket list is enough to explain the core idea.
Run basic behavior tests
A HashSet should not store duplicates, should report membership correctly, and should treat removing a missing key as a safe no-op.
def check_hashset(values):
values.add(5)
values.add(5)
assert values.contains(5)
values.remove(5)
assert not values.contains(5)
values.remove(5)
assert not values.contains(5)
check_hashset(BucketHashSet())
check_hashset(SmallHashSet())
print("ok")
Those tests cover the behavior users expect from a set. If you need more set syntax after this custom implementation, see the Python set comprehension guide and the combine sets guide.
Add more tests when the key range expands. Check strings, integers, repeated adds, repeated removes, and keys that collide. The important point is not only that the value is present, but that adding it again does not change the logical contents of the set.
When to use each approach
Use Python’s built-in set for application code. Use direct addressing only when the key range is small and numeric. Use buckets when you are learning how hashing works or solving a design exercise. If you are combining unique items from multiple sequences, the Python union of lists guide may be more practical.
HashSet keys must be hashable. Immutable types such as strings, integers, and tuples of hashable items work well. Mutable containers such as lists do not. If hashability errors show up in related code, the unhashable type guide explains the underlying issue.
Define The Small Interface
A useful exercise starts with a clear contract: add inserts a key, contains reports membership, and remove deletes a key or raises a documented result. Decide whether duplicate insertion is silent and what removing a missing key should do.
class HashSet:
def __init__(self):
self._values = set()
def add(self, value):
self._values.add(value)
def contains(self, value):
return value in self._values
def remove(self, value):
self._values.remove(value)
items = HashSet()
items.add("python")
print(items.contains("python"))
Understand Buckets And Collisions
A table maps a hash value to a bucket index, but distinct keys can share an index. Store multiple entries in the bucket and compare equality after hashing; hashing alone is not identity.
class BucketSet:
def __init__(self, size=8):
self.buckets = [[] for _ in range(size)]
def _bucket(self, value):
return self.buckets[hash(value) % len(self.buckets)]
def add(self, value):
bucket = self._bucket(value)
if value not in bucket:
bucket.append(value)
def contains(self, value):
return value in self._bucket(value)
Use Hashable Keys
Set membership requires hashable values whose hash and equality behavior remain compatible. Lists and dictionaries are mutable and unhashable; convert to an immutable representation only when that representation truly defines identity.
values = {(1, 2), (3, 4)}
print((1, 2) in values)
record_key = ("Ada", 1)
print(hash(record_key))
Test The Core Invariants
Test duplicate insertion, missing removal, collision-like keys, and membership after deletion. A small test matrix catches a broken bucket implementation before it is confused with a performance problem.
items = set()
items.add("a")
items.add("a")
print(items == {"a"})
items.remove("a")
print("a" not in items)
The official set and frozenset documentation defines uniqueness, unordered membership, and hashable elements. Use the related Python set guide for application code and set operations for unions and intersections.
For related uniqueness and membership, compare Python sets, set operations, and dictionary behavior before building custom storage.
Frequently Asked Questions
What is a HashSet?
A HashSet stores unique hashable keys and supports membership, insertion, and removal through a hash-based lookup structure.
Does Python have a built-in HashSet?
Python’s built-in set provides the HashSet-like behavior used in normal code, while frozenset provides an immutable hashable set.
What happens when two keys collide?
A hash collision means keys map to the same bucket; a bucket-based implementation must compare the actual keys after selecting the bucket.
When should I implement a HashSet myself?
Implement one for learning, an algorithm exercise, or a specialized storage constraint; use the optimized built-in set unless you have a measured reason not to.