13.3 Design HashSet

13.3.1 Problem Metadata

13.3.2 Description

Create a HashSet supporting add(key), contains(key), and remove(key) without using built-in hash table libraries.

13.3.3 Examples

MyHashSet set = new MyHashSet();
set.add(1);
set.add(2);
set.contains(1); // true
set.contains(3); // false
set.add(2);
set.contains(2); // true
set.remove(2);
set.contains(2); // false

13.3.4 Constraints

  • 0 <= key <= 10^6
  • At most 10^4 operations

13.3.5 Solution - Separate Chaining Buckets

13.3.5.1 Walkthrough

Create an array of buckets; each bucket holds a linked lc-list of stored keys. The hash function is key % capacity. add inserts if absent, remove deletes from the chain, contains scans the lc-list.

13.3.5.2 Analysis

  • Time Complexity: Average O(1); worst-case O(n) if all keys collide
  • Space Complexity: O(n)

13.3.5.3 Implementation Steps

  1. Choose bucket count (e.g., 1000) and allocate arrays of lc-lists.
  2. Map keys to bucket index via modulo.
  3. Implement linked-lc-list helpers to search, insert, remove within each bucket.

13.3.5.4 Code - Java

class MyHashSet {
    private static class Node {
        int key;
        Node next;
        Node(int key) { this.key = key; }
    }

    private final Node[] buckets;
    private final int size = 1000;

    public MyHashSet() {
        buckets = new Node[size];
    }

    public void add(int key) {
        int idx = key % size;
        Node head = buckets[idx];
        Node curr = head;
        while (curr != null) {
            if (curr.key == key) {
                return;
            }
            curr = curr.next;
        }
        Node node = new Node(key);
        node.next = head;
        buckets[idx] = node;
    }

    public void remove(int key) {
        int idx = key % size;
        Node dummy = new Node(-1);
        dummy.next = buckets[idx];
        Node prev = dummy;
        Node curr = dummy.next;
        while (curr != null) {
            if (curr.key == key) {
                prev.next = curr.next;
                break;
            }
            prev = curr;
            curr = curr.next;
        }
        buckets[idx] = dummy.next;
    }

    public boolean contains(int key) {
        int idx = key % size;
        Node curr = buckets[idx];
        while (curr != null) {
            if (curr.key == key) {
                return true;
            }
            curr = curr.next;
        }
        return false;
    }
}