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
1 2 3 4 5 6 7 8 9
|
MyHashSet hashSet = new MyHashSet(); hashSet.add(1); hashSet.add(2); hashSet.contains(1); hashSet.contains(3); hashSet.add(2); hashSet.contains(2); hashSet.remove(2); hashSet.contains(2);
|
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.
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
|
private int size = 1000; private LinkedList[] map;
public () { map = new LinkedList[size];
for (int i = 0; i < size; i++) map[i] = new LinkedList<Integer>(); }
public void add(int key) { if (!contains(key)) { int hash = hash(key); map[hash].add(key); } }
public void remove(int key) { if (contains(key)) { int hash = hash(key); int idx = map[hash].indexOf(key); map[hash].remove(idx); } }
public boolean contains(int key) { int hash = hash(key); return map[hash].contains(key); }
private int hash(Integer x){ return x.hashCode() % size; }
|
近期评论