# 706. Design hash map

Design HashMap - LeetCode

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 {

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)
if head.k == key:
return -1

def remove(self, key: int) -> None:
index = self.hash(key)
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

``````