Devin's Blog

Design Hashset

2 min read

Intuition

  • Same as

    Intuition

    • Brute force, this problem may be solved by using two arrays, one for the key, and the other for the value.
    • Otherwise, it can be solved by using buckets. Each bucket can hold key, value pairs. And, each bucket is hashed into. If there are 2069 buckets, there is a chance of collision to one of those buckets for every 2069 keys.
    • Therefore, this reduces the time complexity since we no longer have to search through one bucket of all the items (like was done in the brute force case).
    • Alternatively, you can use a Linked List to avoid having to use .get() and instead changing the elements in place.
    Link to original

Complexity

Complexity

Runtime

  • brute force due to having to do a linear search through all keys on each get, insertion, and removal
  • when using buckets, due to the hash function giving many buckets of lesser length.

Space

due to having to store the key, value pairs.

Link to original

Code

Linked List

class ListNode:
    def __init__(self, key=-1):
        self.key = key
        self.next = None
 
class Bucket:
    def __init__(self):
        self.bucket = ListNode()
 
    def add(self, key: int) -> None:
        itr = self.bucket
        prev = itr
        while itr:
            if itr.key == key:
                return
            prev = itr
            itr = itr.next
        prev.next = ListNode(key)
        
    def remove(self, key: int) -> None:
        itr = self.bucket
        while itr:
            if itr.key == key:
                prev.next = itr.next
                itr.next = None
                return
            prev = itr
            itr = itr.next
 
    def contains(self, key: int) -> bool:
        itr = self.bucket
        while itr:
            if itr.key == key:
                return True
            itr = itr.next
        return False
 
class MyHashSet:
    def __init__(self):
        self.prime = 2069
        self.set = [Bucket() for _ in range(self.prime)]
 
    def add(self, key: int) -> None:
        self.set[key % self.prime].add(key)
 
    def remove(self, key: int) -> None:
        self.set[key % self.prime].remove(key)
 
    def contains(self, key: int) -> bool:
        return self.set[key % self.prime].contains(key)

Bucket Array

class Bucket:
    def __init__(self):
        self.bucket = []
 
    def add(self, key: int) -> None:
        for k in self.bucket:
            if k == key:
                return
        self.bucket.append(key)      
        
    def remove(self, key: int) -> None:
        for i, k in enumerate(self.bucket):
            if k == key:
                self.bucket.pop(i)
 
    def contains(self, key: int) -> bool:
        return key in self.bucket
 
class MyHashSet:
    def __init__(self):
        self.prime = 2069
        self.set = [Bucket() for _ in range(self.prime)]
 
    def add(self, key: int) -> None:
        self.set[key % self.prime].add(key)
 
    def remove(self, key: int) -> None:
        self.set[key % self.prime].remove(key)
 
    def contains(self, key: int) -> bool:
        return self.set[key % self.prime].contains(key)

Brute Force

class MyHashSet:
 
    def __init__(self):
        self.set = []
 
    def add(self, key: int) -> None:
        if key in self.set:
            return
        self.set.append(key)
 
    def remove(self, key: int) -> None:
        if key in self.set:
            self.set.remove(key)
 
    def contains(self, key: int) -> bool:
        return key in self.set

Cards

START Basic Front: Design Hashset Back: Ammortize cost with buckets instead of one large bucket.

END

References

Graph View