# 706. Design HashMap

## Problem:

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`.

<pre><code><strong>Input
</strong>["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
<strong>Output
</strong>[null, null, null, 1, -1, null, 1, null, -1]

<strong>Explanation
</strong>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]]
</code></pre>

<https://leetcode.com/problems/design-hashmap/>

## Solution:

{% hint style="info" %}
While Python's dictionary uses open addressing, let's try implementing it using the separate chaining method
{% endhint %}

```python
import collections

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

class MyHashMap:
    def __init__(self):
        self.size = 1000
        self.bucket = collections.defaultdict(ListNode)
        
    def put(self, key: int, value: int) -> None:
        index = key % self.size

        # If the bucket is empty, insert the node
        if self.bucket[index].value is None:
            self.bucket[index] = ListNode(key, value)
            return

        # Otherwise, iterate through the linked list to either update or append the node
        p = self.bucket[index]
        while p:
            if p.key == key:
                p.value = value # Update
                return
            if p.next is None:
                break
            p = p.next
        # If the key was found at the end of the linked list, append it to the last
        p.next = ListNode(key, value)
        
    def get(self, key: int) -> int:
        index = key % self.size
        if self.bucket[index].value is None:
            return -1 

        # Key found
        p = self.bucket[index]
        while p:
            if p.key == key:
                return p.value
            p = p.next
        return -1 
        
    def remove(self, key: int) -> None:
        index = key % self.size
        if self.bucket[index].value is None:
            return
        # First node in the linked list
        p = self.bucket[index]
        if p.key == key:
            self.bucket[index] = ListNode() if p.next is None else p.next
            return
        # Somewhere in the middle or at the end of the linked list
        prev = p
        while p:
            if p.key == key:
                prev.next = p.next
                return
            prev, p = p, p.next

if __name__ == '__main__':
# Your MyHashMap object will be instantiated and called as such:
    obj = MyHashMap()
    obj.put(1,1)
    obj.put(2,2)
    obj.get(1)
    obj.get(3)
    obj.put(2, 1)
    obj.get(2)
    obj.remove(2)
    obj.get(2)
```

### \_\_init\_\_()

To implement conveniently, the `collections.defaultdict` was used which automatically creates a default value when querying a non-existing key. When `defaultdict` attempts to look up a non-existing index, **it does not raise an error** but instead immediately creates a default object.&#x20;

In this case, since it's `defaultdict(ListNode)`, when querying a non-existing index, it will immediately create an empty `ListNode`.

**More about defaultdict():** [#defaultdict-argument](https://sammitako.gitbook.io/mscs/string/819.-most-common-word#defaultdict-argument "mention")

### put()

1. If there's no node in the bucket, insert and then exit.
2. If there's a node in the bucket, handle it using a linked list.
   1. If the key already exists, update it.
   2. If a key is not already present in the hash map, it gets added at the end of the linked list at the calculated index.

### get()

1. **Initial Check:** If there's no node (or an empty node) at that index, it immediately concludes that the key is not present in the hash map and returns `-1`.
2. **After Traversing the Linked List**: If it finds the node (`if p.key == key:`), it returns the value associated with that key (`return p.value`). However, if the method completes the traversal of the linked list without finding the desired key, it reaches the final `return -1`. This means that even though there were nodes at the calculated index, none of them had the desired key.

### remove()

There are two main scenarios to consider when removing a node:

1. **The node to be removed is the first node in the linked list at that index.**
2. **The node to be removed is somewhere in the middle or at the end of the linked list.**

#### **Scenario 1: The node to be removed is the first node in the linked list.**

* If the key of the first node (`p`) matches the key to be removed (`p.key == key`), then we need to remove this node.
* If this node is the only node in the linked list (`p.next is None`), we replace it with a new empty node (`ListNode()`). This is equivalent to removing the node.
* If this node is not the only node (`p.next` exists), we set the next node as the new head of the linked list for that index. This effectively skips over the current node and removes it from the linked list.
* After handling this scenario, we `return` to exit the method.

To give a clearer understanding, consider this:

* If you have a linked list like: `A -> B -> C` and you want to remove `A`, then the list should look like `B -> C` after the removal.
* If you have a linked list like: `A` (just one node) and you want to remove `A`, then the list should be empty after the removal.

#### **Scenario 2: The node to be removed is somewhere in the middle or at the end of the linked list.**

* We start with `prev` as the first node.
* We then traverse the linked list using a `while` loop.
* If we find a node with the key to be removed (`p.key == key`), we adjust the `next` pointer of the previous node (`prev.next`) to point to the node after the current node (`p.next`). This effectively removes the current node from the linked list.
* After handling this scenario, we `return` to exit the method.

To summarize, the `p.next` in the first scenario is used to handle the special case where the node to be removed is the first node in the linked list. The second scenario handles all other cases.
