Build a set with no built-in hash table: hash each key into one of 769 buckets, and keep a short list in each bucket for collisions.
▼The problem
LeetCode 705 (Easy). Design a hash set without any built-in hash table library: add(key), remove(key) and contains(key). Keys are 0..10^6, at most 10^4 calls. (Cousins in the series: ../design-hashmap (the cloakroom, keys with values), ../contains-duplicate, ../two-sum, ../lru-cache, ../insert-delete-getrandom, ../time-based-key-value-store; this one has its own look.)
Example (LeetCode's): add(1), add(2), contains(1) -> true, contains(3) -> false, add(2), contains(2) -> true, remove(2), contains(2) -> false, walked through in scene 6.
The solution
class MyHashSet:
def __init__(self):
self.size = 769
self.buckets = [[] for _ in range(self.size)]
def add(self, key):
b = self.buckets[key % self.size]
if key not in b:
b.append(key)
def remove(self, key):
b = self.buckets[key % self.size]
if key in b:
b.remove(key)
def contains(self, key):
return key in self.buckets[key % self.size]Transcript
Design HashSet. Build a set of numbers without any built-in hash set. Add puts a key in, remove takes it out, and contains asks if it's there.
Add one, add two. Contains one: true. Contains three: false. Add two again: it's already there, so nothing changes. Contains two: true. Remove two, and now it's false.
The simple way keeps one list and scans it on every call: order n. Or keep a slot for every possible key, a million and one of them, almost all empty.
Better: use buckets. A key's bucket is the key mod the bucket count. With seven buckets, fifteen goes to bucket one. Each bucket holds a short chain of keys. One also lands in bucket one: a collision, so that chain just grows. To look up a key, scan only its chain. A set keeps keys only; a map would add a value to each.
In code, make seven hundred sixty-nine buckets. Add appends the key unless its chain already has it. Remove deletes it if it's there. Contains scans that one chain.
Let's walk it. One goes to bucket one, two to bucket two. Contains one: found. Contains three: bucket three is empty, false. Add two again: already there, skip. Contains two: true. Remove two, and contains two is false.
The load factor is keys per bucket. Keep it small with enough buckets, and each call is order one on average. Space is order of buckets plus keys.
Mod picks the bucket, scan one short chain, store each key once. That's Design HashSet.