Design HashSet

Easy Design Data Structures Pre-processing + tradeoffs Original on LeetCode

Reported atFlipkart

Design HashSet is a easy design data structures problem solved with the pre-processing + tradeoffs pattern. The best approach, optimal (separate chaining), runs in O(1) average per operation time and O(B + n) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (one list of keys) up.

Problem

Build your own hash set for integer keys without using any built-in hash table or hash set library. Implement the class MyHashSet:

  • MyHashSet() creates an empty set.
  • void add(int key) inserts key (adding a key that is already present has no effect).
  • void remove(int key) deletes key if it is present; otherwise nothing happens.
  • boolean contains(int key) returns whether key is currently in the set.

Examples

Example 1

Input
add(4), add(9), contains(4), contains(5), add(4), remove(4), contains(4), contains(9)
Output
true, false, false, true
Why
Adding 4 a second time changes nothing, and after one remove it is gone while 9 stays.

Example 2

Input
remove(0), add(0), contains(0), remove(0), remove(0), contains(0)
Output
true, false
Why
Removing a key that is not in the set is allowed and does nothing; 0 is an ordinary key.

Constraints

  • 0 <= key <= 10^6
  • At most 10^4 calls in total to add, remove and contains.
  • Do not use a built-in hash set or hash table library.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (one list of keys)O(n) per operationO(n)
Better (direct addressing)O(1) per operationO(U), U = 10^6 + 1
Optimal (separate chaining)O(1) average per operationO(B + n)

1Brute force (one list of keys)

TimeO(n) per operationA scan may visit all n stored keys.
SpaceO(n)One slot per stored key.

Store every key once in a single dynamic list. Each operation scans the whole list for the key.

  1. add: if the key is not already in the list, append it.
  2. remove: find the key and delete it if present.
  3. contains: scan the list and report whether the key was found.
class MyHashSet {
    private final List<Integer> keys = new ArrayList<>();

    public MyHashSet() {}

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

    public void remove(int key) {
        keys.remove(Integer.valueOf(key));
    }

    public boolean contains(int key) {
        for (int k : keys) if (k == key) return true;
        return false;
    }
}

2Better (direct addressing)

TimeO(1) per operationEach call is one array read or write.
SpaceO(U), U = 10^6 + 1The array covers the whole key universe regardless of how many keys are stored.

Keys are integers in [0, 10^6], so a boolean array with one slot per possible key answers every call with a single array access. The price is memory for all possible keys, even if only a few are ever stored.

  1. Allocate a boolean array of size 10^6 + 1, all false.
  2. add sets present[key] = true; remove sets it to false.
  3. contains returns present[key].
class MyHashSet {
    private final boolean[] present = new boolean[1_000_001];

    public MyHashSet() {}

    public void add(int key) { present[key] = true; }

    public void remove(int key) { present[key] = false; }

    public boolean contains(int key) { return present[key]; }
}

3Optimal (separate chaining)

TimeO(1) average per operationWith n keys over B buckets each bucket holds about n / B keys, which is constant when B is at least the number of keys.
SpaceO(B + n)B bucket headers plus one entry per stored key.

Keep a fixed number B of buckets (a prime such as 10007). Key k belongs to bucket k % B, which is a short list. Every call only scans that one bucket, so with keys spread evenly each call touches O(1) entries on average while memory grows with the number of stored keys rather than with the key range.

  1. Create B empty bucket lists.
  2. add: look in bucket key % B; append the key only if it is not there.
  3. remove: delete the key from bucket key % B if present.
  4. contains: scan bucket key % B for the key.
class MyHashSet {
    private static final int B = 10007;
    private final List<List<Integer>> buckets = new ArrayList<>();

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

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

    public void remove(int key) {
        buckets.get(key % B).remove(Integer.valueOf(key));
    }

    public boolean contains(int key) {
        return buckets.get(key % B).contains(key);
    }
}

Edge cases to test

  • Adding the same key twice (the set must still hold it once)
  • Removing a key that is not present
  • Key 0 and key 10^6, the two ends of the range
  • Keys that fall into the same bucket, such as k and k + B
  • Adding a key again after it was removed

Hints

Hint 1

Start with the simplest structure that works: a plain list of the stored keys. How expensive is each call?

Hint 2

Since keys are small non-negative integers, you could index an array directly by the key. What does that cost in memory?

Hint 3

To use memory in proportion to the keys actually stored, split them into B buckets chosen by key % B and scan only one bucket per call.

FAQ

What is the best time complexity for Design HashSet?

Optimal (separate chaining) runs in O(1) average per operation time and O(B + n) extra space. With n keys over B buckets each bucket holds about n / B keys, which is constant when B is at least the number of keys.

Which pattern does Design HashSet use?

It is a design data structures problem that uses the pre-processing + tradeoffs pattern. Other problems with the same pattern: Design Neighbor Sum Service, Simple Bank System, Design File System.

Is there a brute force solution for Design HashSet?

Yes. Brute force (one list of keys) takes O(n) per operation time and O(n) space. Store every key once in a single dynamic list.

Which edge cases should I test for Design HashSet?

Adding the same key twice (the set must still hold it once); Removing a key that is not present; Key 0 and key 10^6, the two ends of the range; Keys that fall into the same bucket, such as k and k + B; Adding a key again after it was removed.