Design a HashMap without using any built-in hash table libraries. Implement the MyHashMap class:
MyHashMap() initializes the object with an empty map.
void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.
- code
class Pair{
public int k;
public int v;
public Pair (int k, int v){
this.k = k;
this.v = v;
}
}
class MyHashMap {
LinkedList<Pair>[] map;
public MyHashMap() {
map = new LinkedList[2069];
for (int i = 0; i < 2069; i++){
map[i] = new LinkedList<Pair>();
}
}
public int hash(int k){
return k % 2069;
}
public void put(int key, int value) {
for (Pair p :map[hash(key)]){
if (p.k == key){
p.v = value;
return;
}
}
map[hash(key)].offer(new Pair(key, value));
}
public int get(int key) {
for (Pair p :map[hash(key)]){
if (p.k == key){
return p.v;
}
}
return -1;
}
public void remove(int key) {
for (Pair p :map[hash(key)]){
if (p.k == key){
map[hash(key)].remove(p);
break;
}
}
}
}
- code Naive array
class MyHashMap:
def __init__(self):
self.hm = [-1] * (10 ** 6 + 1)
def put(self, key: int, value: int) -> None:
self.hm[key] = value
def get(self, key: int) -> int:
return self.hm[key]
def remove(self, key: int) -> None:
self.hm[key] = -1
- code new linkedlist
class Node:
def __init__(self, k, v, nex):
self.k = k
self.v = v
self.next = nex
class MyHashMap:
def __init__(self):
self.hm = [None] * 20000
def hash(self, k):
return k % 20000
def put(self, key: int, value: int) -> None:
self.remove(key)
index = self.hash(key)
newNode = Node(key, value, self.hm[index])
self.hm[index] = newNode
def get(self, key: int) -> int:
index = self.hash(key)
head = self.hm[index]
while head:
if head.k == key:
return head.v
head = head.next
return -1
def remove(self, key: int) -> None:
index = self.hash(key)
head = self.hm[index]
res = pre = Node(0, 0, head)
while pre and pre.next:
if pre.next.k == key:
pre.next = pre.next.next
pre = pre.next
self.hm[index] = res.next
- code Old linkedlist
class MyNode:
def __init__(self, key, value, next) -> None:
self.key = key
self.value = value
self.next = next
class MyHashMap:
def __init__(self):
"""
Initialize your data structure here.
"""
self.size = 20000
self.myHashMap = [None] * self.size
def getIndex(self, key):
return key % self.size
def put(self, key: int, value: int) -> None:
"""
value will always be non-negative.
"""
# put in the end, gonna exceed time limit
# index = self.getIndex(key)
# newNode = MyNode(key, value, None)
# curNode = self.myHashMap[index]
# if not curNode:
# self.myHashMap[index] = newNode
# else:
# while curNode.next:
# if curNode.next.key != key:
# curNode = curNode.next
# else:
# curNode.value = value
# # cur node is the last
# if curNode.key != key:
# curNode.next = newNode
# else:
# curNode.value = value
# try to remove key, then put in the first one
self.remove(key)
index = self.getIndex(key)
newNode = MyNode(key, value, self.myHashMap[index])
self.myHashMap[index] = newNode
def get(self, key: int) -> int:
"""
Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
"""
index = self.getIndex(key)
curNode = self.myHashMap[index]
while curNode:
if curNode.key != key:
curNode = curNode.next
else:
return curNode.value
return -1
def remove(self, key: int) -> None:
"""
Removes the mapping of the specified value key if this map contains a mapping for the key
"""
index = self.getIndex(key)
curNode = self.myHashMap[index]
if not curNode:
return
if curNode.key == key:
# self.myHashMap[index] = None
self.myHashMap[index] = curNode.next
return
while curNode.next:
if curNode.next.key != key:
curNode = curNode.next
else:
curNode.next = curNode.next.next