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.add(1);
hashSet.add(2);
hashSet.contains(1); // returns true
hashSet.contains(3); // returns false (not found)
hashSet.add(2);
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];
}
public void add(int key) {
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>();
}
set[index].add(key);
}
}
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();
* obj.add(key);
* obj.remove(key);
* boolean param_3 = obj.contains(key);
*/
Last updated
Was this helpful?