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 {
    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