# Design HashSet

Design a HashSet without using any built-in hash table libraries.

To be specific, your design should include these functions:

• `add(value)`

: Insert a value into the HashSet.

• `contains(value)`

: Return whether the value exists in the HashSet or not.

• `remove(value)`

: Remove a value in the HashSet. If the value does not exist in the HashSet, do nothing.

Example:

``````MyHashSet hashSet = new MyHashSet();
hashSet.contains(1);    // returns true
hashSet.contains(2);    // returns true
hashSet.remove(2);
hashSet.contains(2);    // returns false (already removed)``````

Note:

• All values will be in the range of`[0, 1000000]`.

• The number of operations will be in the range of `[1, 10000]`.

• Please do not use the built-in HashSet library.

## Solution

``````class MyHashSet {
private final int MAX_LEN = 100000; // the amount of buckets
private List<Integer>[] set;      // hash set implemented by array

/** Returns the corresponding bucket index. */
private int getIndex(int key) {
return key % MAX_LEN;
}

/** Search the key in a specific bucket. Returns -1 if the key does not existed. */
private int getPos(int key, int index) {
// Each bucket contains a list.
List<Integer> temp = set[index];
if (temp == null) {
return -1;
}
// Iterate all the elements in the bucket to find the target key.
for (int i = 0; i < temp.size(); ++i) {
if (temp.get(i) == key) {
return i;
}
}
return -1;
}

/** Initialize your data structure here. */
public MyHashSet() {
set = (List<Integer>[])new ArrayList[MAX_LEN];
}

int index = getIndex(key);
int pos = getPos(key, index);
if (pos < 0) {
// Add new key if key does not exist.
if (set[index] == null) {
set[index] = new ArrayList<Integer>();
}
}
}

public void remove(int key) {
int index = getIndex(key);
int pos = getPos(key, index);
if (pos >= 0) {
// Remove the key if key exists.
set[index].remove(pos);
}
}

/** Returns true if this set did not already contain the specified element */
public boolean contains(int key) {
int index = getIndex(key);
int pos = getPos(key, index);
return pos >= 0;
}
}

/**
* Your MyHashSet object will be instantiated and called as such:
* MyHashSet obj = new MyHashSet();