Design HashSet

easy design hash table

Problem

Implement add, remove, contains for ints.

Inputadd(1); add(2); contains(1); contains(3); remove(2); contains(2)

OutputTrue False False

Standard hash set ops.

input

class MyHashSet:
    def __init__(self): self.k = 769; self.buckets = [[] for _ in range(self.k)]
    def _h(self, x): return x % self.k
    def add(self, x):
        b = self.buckets[self._h(x)]
        if x not in b: b.append(x)
    def remove(self, x):
        b = self.buckets[self._h(x)]
        if x in b: b.remove(x)
    def contains(self, x): return x in self.buckets[self._h(x)]

class MyHashSet {
  constructor() { this.k = 769; this.b = Array.from({length: 769}, () => []); }
  h(x) { return x % this.k; }
  add(x) { const b = this.b[this.h(x)]; if (!b.includes(x)) b.push(x); }
  remove(x) { const b = this.b[this.h(x)]; const i = b.indexOf(x); if (i >= 0) b.splice(i, 1); }
  contains(x) { return this.b[this.h(x)].includes(x); }
}

class MyHashSet {
    int k = 769; List> b;
    public MyHashSet() { b = new ArrayList<>(); for (int i = 0; i < k; i++) b.add(new ArrayList<>()); }
    int h(int x) { return x % k; }
    public void add(int x) { List l = b.get(h(x)); if (!l.contains(x)) l.add(x); }
    public void remove(int x) { b.get(h(x)).remove((Integer) x); }
    public boolean contains(int x) { return b.get(h(x)).contains(x); }
}

class MyHashSet {
    int k = 769; vector> b;
public:
    MyHashSet() : b(k) {}
    int h(int x) { return x % k; }
    void add(int x) { auto& l = b[h(x)]; if (find(l.begin(), l.end(), x) == l.end()) l.push_back(x); }
    void remove(int x) { auto& l = b[h(x)]; l.erase(std::remove(l.begin(), l.end(), x), l.end()); }
    bool contains(int x) { auto& l = b[h(x)]; return find(l.begin(), l.end(), x) != l.end(); }
};

Explanation

A hash set needs to answer "is this number here?" quickly. The idea is to spread numbers across many small lists called buckets, so each lookup only has to scan one short list instead of everything.

We pick a fixed number of buckets k = 769 (a prime, which spreads values evenly). The bucket for a number x is just x % k. Each bucket is a tiny list that holds the values landing there — this is called chaining.

add(x) finds the bucket and appends x only if it is not already there. remove(x) finds the bucket and deletes x if present. contains(x) simply checks whether x is in its bucket's list.

Because numbers are spread over 769 buckets, each list stays short on average, so all three operations are fast.

Example: add(1) goes to bucket 1 % 769 = 1, add(2) to bucket 2. contains(1) scans bucket 1 and finds it (true). After remove(2), bucket 2 is empty, so contains(2) returns false.

Time: O(n/k) avg Space: O(n + k)