[link](https://leetcode.com/problems/design-hashmap/)

---

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.

#### Example 1:

Input
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
Output
[null, null, null, 1, -1, null, 1, null, -1]

Explanation
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // The map is now [[1,1]]
myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]
myHashMap.get(1);    // return 1, The map is now [[1,1], [2,2]]
myHashMap.get(3);    // return -1 (i.e., not found), The map is now [[1,1], [2,2]]
myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value)
myHashMap.get(2);    // return 1, The map is now [[1,1], [2,1]]
myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]]
myHashMap.get(2);    // return -1 (i.e., not found), The map is now [[1,1]]

#### Constraints:

- 0 <= key, value <= 106
- At most 104 calls will be made to put, get, and remove.

---

The ListNode class represents a node in a linked list. Each node has a key attribute that stores the integer key, a val attribute that stores the corresponding value, and a next attribute that points to the next node in the list.

The MyHashMap class is the main implementation of the hash map. It initializes a list of fixed size (10^4 in this case) with ListNode objects. The size of the list is chosen to balance the trade-off between memory usage and collision avoidance.

The put method adds or updates a key-value pair in the hash map. It calculates the hash value of the key by taking the modulus of the key with the size of the hash map. It then traverses the linked list at the calculated index and checks if the key already exists. If the key is found, it updates the corresponding value. If the key is not found, it creates a new ListNode with the key-value pair and appends it to the end of the linked list.

The get method retrieves the value associated with a given key from the hash map. It calculates the hash value of the key and traverses the linked list at the calculated index. If the key is found, it returns the corresponding value. If the key is not found, it returns -1.

The remove method removes a key-value pair from the hash map. It calculates the hash value of the key and traverses the linked list at the calculated index. If the key is found, it adjusts the pointers to skip the node containing the key, effectively removing it from the list.

#### Solution 1

class ListNode:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None


class MyHashMap:

    def __init__(self):
        self.hashMap = [ListNode(0, 0) for i in range(10 ** 4)]
        

    def put(self, key: int, value: int) -> None:
        index = key % len(self.hashMap)
        cur = self.hashMap[index]
        while cur.next:
            if cur.next.key == key:
                cur.next.val = value
                return
            cur = cur.next
        cur.next = ListNode(key, value)
        

    def get(self, key: int) -> int:
        index = key % len(self.hashMap)
        cur = self.hashMap[index]
        while cur.next:
            if cur.next.key == key:
                return cur.next.val
            cur = cur.next
        
        return -1
        

    def remove(self, key: int) -> None:
        index = key % len(self.hashMap)
        cur = self.hashMap[index]
        while cur.next:
            if cur.next.key == key:
                cur.next = cur.next.next
                return 
            cur = cur.next

        return
        

O(T): O(1)
O(S): O(N)