Design HashSet - LeetCode Design a HashSet without using any built-in hash table libraries. Implement MyHashSet class:
void add(key) Inserts the value key into the HashSet.
bool contains(key) Returns whether the value key exists in the HashSet or not.
void remove(key) Removes the value key in the HashSet. If key does not exist in the HashSet, do nothing.
- code
class MyHashSet {
LinkedList[] list;
public MyHashSet() {
list = new LinkedList[713];
// Arrays.fill(list, new LinkedList<Integer>());
for (int i = 0; i < 713; i++)
list[i] = new LinkedList<Integer>();
}
public int hash(int k){
return k % 713;
}
public void add(int key) {
if (!contains(key))
list[hash(key)].add(key);
}
public void remove(int key) {
list[hash(key)].removeFirstOccurrence(Integer.valueOf(key));
}
public boolean contains(int key) {
return list[hash(key)].contains(key);
}
}
- code java linkedlist
class Bucket{
LinkedList<Integer> bucket;
public Bucket(){
bucket = new LinkedList();
}
public void add(int key){
if (!bucket.contains(key)){
bucket.offerFirst(key);
}
}
public void remove(int key){
// bucket.remove(Integer.valueOf(key));
bucket.removeFirstOccurrence(Integer.valueOf(key));
}
public boolean contains(int key){
return bucket.contains(key);
}
}
class MyHashSet {
Bucket[] hs;
public int getIndex(int key){
return key % 769;
}
public MyHashSet() {
hs = new Bucket[769];
// Arrays.fill(hs, new Bucket()); don't know why very slow
for (int i = 0; i < 769; ++i){
hs[i] = new Bucket();
}
}
public void add(int key) {
int index = getIndex(key);
hs[index].add(key);
}
public void remove(int key) {
int index = getIndex(key);
hs[index].remove(key);
}
public boolean contains(int key) {
int index = getIndex(key);
return hs[index].contains(key);
}
}
/**
* 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);
*/
- code linkedlist python
class ListNode:
def __init__(self, key, val):
self.key = key
self.val = val
self.next = None
class MyHashSet:
def __init__(self):
"""
Initialize your data structure here.
"""
self.size = 1000
self.m = [None]*self.size
def add(self, key: int) -> None:
index = key%self.size
#If the node at given index is None then set it with given key
if self.m[index] == None:
self.m[index] = ListNode(key,True)
else:
currNode = self.m[index]
#If there are nodes at given index then traverse the linked-list and attach the key at the end.
tempHead = currNode
self.m[index] = ListNode(key,True)
self.m[index].next = currNode
def remove(self, key: int) -> None:
index = key%self.size
#If node at given index is None then do nothing.
if self.m[index] == None:
return
#Otherwise find given key in the linked-list at current index and set its value to False.
else:
currNode = self.m[index]
while currNode:
if currNode.key == key:
currNode.val = False
break
currNode = currNode.next
def contains(self, key: int) -> bool:
"""
Returns true if this set contains the specified element
"""
index = key%self.size
#If there's no linked-list at given index then return False.
if self.m[index] == None:
return False
#Otherwise traverse the linked-list to check if the desired element is present and its value is True.
else:
currNode = self.m[index]
while currNode:
if currNode.key == key:
if currNode.val == True:
return True
else:
return False
currNode = currNode.next
return False
- code use bytearray Built-in Types — Python 3.9.7 documentation
class MyHashSet:
def __init__(self):
self.hash_set = bytearray(1000001)
def add(self, key: int) -> None:
self.hash_set[key] = True
def remove(self, key: int) -> None:
self.hash_set[key] = False
def contains(self, key: int) -> bool:
return self.hash_set[key]