Design HashSet

NeetCode: Design HashSet · LeetCode: 705. Design HashSet · Difficulty: Easy

Design a MyHashSet without using the built-in HashSet or HashMap. It supports add(key), remove(key) and contains(key). Keys are integers in 0 to 1000000. Adding an existing key or removing a missing one does nothing.

Example

Text

add(1), add(2), contains(1) -> true, contains(3) -> false,
add(2), contains(2) -> true, remove(2), contains(2) -> false

Brute force: one list, linear scan

Store every key in a single ArrayList<Integer>. Membership requires scanning the whole list, so every operation costs time proportional to the number of stored keys.

Java

import java.util.ArrayList;
import java.util.List;

class MyHashSet {
    private final List<Integer> items = new ArrayList<>();

    public void add(int key) {
        if (!contains(key)) {
            items.add(key);
        }
    }

    public void remove(int key) {
        int pos = items.indexOf(key);
        if (pos >= 0) {
            int last = items.remove(items.size() - 1); // remove(int) removes by index
            if (pos < items.size()) {
                items.set(pos, last); // fill the gap with the last item
            }
        }
    }

    public boolean contains(int key) {
        return items.contains(key);
    }
}

public class Main {
    public static void main(String[] args) {
        MyHashSet s = new MyHashSet();
        s.add(1);
        s.add(2);
        System.out.println(s.contains(1));
        System.out.println(s.contains(3));
        s.add(2);
        System.out.println(s.contains(2));
        s.remove(2);
        System.out.println(s.contains(2));
        s.remove(99);
        System.out.println(s.contains(1));
    }
}

Output

true
false
true
false
true

remove finds the position, then moves the last item into the gap and drops the last slot. ArrayList.remove(int index) removes by position and shifts every later item left, which costs O(n); removing the last slot costs O(1). The call items.remove(items.size() - 1) takes an int, so it removes by index and does not look for the value.

Time: O(n) per operation, where n is the number of stored keys. Space: O(n).

Optimal: array of buckets (separate chaining)

A hash function maps a key to a bucket index, here Math.floorMod(key, BUCKETS), which never returns a negative index (the % operator keeps the sign of the dividend, so -5 % 769 is -5). Each bucket is a small ArrayList holding the keys that landed there; a collision means two keys share a bucket. An operation scans only one bucket. With a prime bucket count such as 769 and evenly spread keys, the expected cost is O(n / BUCKETS), which is O(1) while the load factor stays bounded.

The bucket count is fixed. A growing table would rehash into twice as many buckets once the average bucket length passes a threshold, keeping the amortised cost O(1).

Java

import java.util.ArrayList;
import java.util.List;

class MyHashSet {
    private static final int BUCKETS = 769;
    private final List<List<Integer>> buckets = new ArrayList<>();

    public MyHashSet() {
        for (int i = 0; i < BUCKETS; i++) {
            buckets.add(new ArrayList<>());
        }
    }

    private List<Integer> bucket(int key) {
        return buckets.get(Math.floorMod(key, BUCKETS));
    }

    public void add(int key) {
        List<Integer> b = bucket(key);
        if (!b.contains(key)) {
            b.add(key);
        }
    }

    public void remove(int key) {
        List<Integer> b = bucket(key);
        int pos = b.indexOf(key);
        if (pos >= 0) {
            int last = b.remove(b.size() - 1);
            if (pos < b.size()) {
                b.set(pos, last);
            }
        }
    }

    public boolean contains(int key) {
        return bucket(key).contains(key);
    }
}

public class Main {
    public static void main(String[] args) {
        MyHashSet s = new MyHashSet();
        s.add(1);
        s.add(2);
        System.out.println(s.contains(1));
        System.out.println(s.contains(3));
        s.add(2);
        System.out.println(s.contains(2));
        s.remove(2);
        System.out.println(s.contains(2));
        // 1 and 770 collide in the same bucket
        s.add(770);
        System.out.println(s.contains(1) + " " + s.contains(770));
        s.remove(1);
        System.out.println(s.contains(1) + " " + s.contains(770));
        s.remove(99);
    }
}

Output

true
false
true
false
true true
false true

Time: expected O(1) per operation for a bounded load factor (worst case O(n) if every key collides). Space: O(BUCKETS + n).

For this key range, a boolean array of 1,000,001 entries is also valid: worst-case O(1) per operation, but it always uses about 1 MB regardless of how many keys are stored.