Solution: Design HashMap (ver. 2)
Tags: algorithms, javascript, java, python
Published: 2021-03-08 02:11:25

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/design-hashmap/discuss/1097755).*

---

*__Note__: This is my second version of a solution for this problem. [The first version](https://dev.to/seanpgallivan/solution-design-hashmap-19ee) is more in line with an Easy problem, but it doesn't really address the actual nature of a hashmap. This solution breaks down in detail what a hashmap accomplishes and why it's beneficial.*

---

#### [Leetcode Problem #706 (*Easy*): Design HashMap](https://leetcode.com/problems/design-hashmap/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
Design a HashMap without using any built-in hash table libraries.
>
To be specific, your design should include these functions:
 -   `put(key, value)`: Insert a `(key, value)` pair into the HashMap. If the value already exists in the HashMap, update the value.
 -   `get(key)`: Returns the value to which the specified key is mapped, or `-1` if this map contains no mapping for the key.
 -   `remove(key)`: Remove the mapping for the value key if this map contains the mapping for the key.

---

#### ***Examples:***
>
Example:||
|---:|---|
Input:|["MyHashMap","put","put","get","get","put","get", "remove", "get"]<br>[[],[1,1],[2,2],[1],[3],[2,1],[2],[2],[2]]
Output:|[null,null,null,1,-1,null,1,null,-1]
Explanation:|MyHashMap hashMap = new MyHashMap();<br>hashMap.put(1, 1);<br>hashMap.put(2, 2);<br>hashMap.get(1); // returns 1<br>hashMap.get(3); // returns -1 (not found)<br>hashMap.put(2, 1); // update the existing value<br>hashMap.get(2); // returns 1<br>hashMap.remove(2); // remove the mapping for 2<br>hashMap.get(2); // returns -1 (not found)

---

#### ***Constraints:***
>
 - All keys and values will be in the range of `[0, 1000000]`.
 - The number of operations will be in the range of `[1, 10000]`.
 - Please do not use the built-in HashMap library.

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

Hashmaps were created to speed up the lookup time of data to a hopefully **O(1) time**. **Arrays** do this naturally with index lookups, but it becomes more complicated if you're trying to look up an entry by some other non-index value instead.

We can see from a simple Array solution that it's easy enough to mimic a **key** lookup if the keys themselves are integers that are constrained enough to act as their own indexes. But what if they're not? Or what if they're some other data type, like strings?

Surprisingly, the idea in that case is somewhat similar. We can still use an Array to store the data, but we must first find a way to transform the key into an index. For that, we look to a **hashing function**. Hashing functions exist to convert data into a randomized, but reproduceable, integer version of themselves.

In this case, we can use a hashing function to convert the key into an integer within the bounds of our hashmap array's index range. In an ideal situation, that would allow us to reduce the size of the hashmap array to the maximum number of entries, which is **10^4**. Unfortunately, however, it's always possible for **collisions** to exist when two keys devolve to the same integer via the hashing function.

To deal with collisions, we can just make each of our hashmap array's elements a **linked list**. This will allow us to treat them like a simple stack, where we look first at the most recently added **node** and then move to the next until we find the correct key.

Since navigating a linked list will drop our lookup time past **O(1)**, the goal of a good hashing function is to randomize the keys' hashes enough to limit collisions as much as possible for a given hashmap array size, thus keeping down the **average lookup time complexity**.

Therefore, the size of our hashmap array should probably be *at least* equal to the number of entries. Increasing the size of the hashmap array will naturally reduce collisions (and therefore time complexity) at the expense of **space complexity**, and vice versa. The tradeoff is highly dependent on the quality of the hashing function.

There are many, many hashing functions out there, but for this problem we'll use a very simple **multiplicative hashing function** utilizing a **large prime multiplier** and then **modulo** the result to the desired size (also a prime) of our hashmap array. This should hopefully result in an even distribution of the entries throughout the hashmap array.

The **get()** method is fairly easy, then. We just **hash()** our **key**, access the corresponding bucket in our hashmap array (**data**), and navigate through the linked list (if necessary) and return the correct **val**, or **-1** if the **key** is not found.

For the **put()** method, we should first **remove()** any earlier instance of that **key** to avoid chaining multiple versions of a **key** definition in our linked list. Then we simply form a **new ListNode** at the head of the proper hashmap bucket, pushing any others back.

The **remove()** method will be similar to the **get()** method, except that we need to find and stitch together the nodes on either side of the **node** that matches the **key**, removing it from the linked list entirely.

---

#### ***Implementation:***

Python has **deque** and Java has **LinkedList** that can do the work of the linked list management, but it comes at the cost of efficiency. In this case, it's not really worth using over a custom **ListNode** class implementation.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
class ListNode {
    constructor(key, val, next) {
        this.key = key
        this.val = val
        this.next = next
    }
}
class MyHashMap {
    constructor() {
        this.size = 19997
        this.mult = 12582917
        this.data = new Array(this.size)
    }
    hash(key) {
        return key * this.mult % this.size
    }
    put(key, val) {
        this.remove(key)
        let h = this.hash(key)
        let node = new ListNode(key, val, this.data[h])
        this.data[h] = node
    }
    get(key) {
        let h = this.hash(key), node = this.data[h]
        for (; node; node = node.next)
            if (node.key === key) return node.val
        return -1
    }
    remove(key) {
        let h = this.hash(key), node = this.data[h]
        if (!node) return
        if (node.key === key) this.data[h] = node.next
        else for (; node.next; node = node.next)
            if (node.next.key === key) {
                node.next = node.next.next
                return
            }
    }
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class ListNode:
    def __init__(self, key, val, nxt):
        self.key = key
        self.val = val
        self.next = nxt
class MyHashMap:
    def __init__(self):
        self.size = 19997
        self.mult = 12582917
        self.data = [None for _ in range(self.size)]
    def hash(self, key):
        return key * self.mult % self.size
    def put(self, key, val):
        self.remove(key)
        h = self.hash(key)
        node = ListNode(key, val, self.data[h])
        self.data[h] = node
    def get(self, key):
        h = self.hash(key)
        node = self.data[h]
        while node:
            if node.key == key: return node.val
            node = node.next
        return -1
    def remove(self, key: int):
        h = self.hash(key)
        node = self.data[h]
        if not node: return
        if node.key == key:
            self.data[h] = node.next
            return
        while node.next:
            if node.next.key == key:
                node.next = node.next.next
                return
            node = node.next
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class ListNode {
    int key, val;
    ListNode next;
    public ListNode(int key, int val, ListNode next) {
        this.key = key;
        this.val = val;
        this.next = next;
    }
}
class MyHashMap {
    static final int size = 19997;
    static final int mult = 12582917;
    ListNode[] data;
    public MyHashMap() {
        this.data = new ListNode[size];
    }
    private int hash(int key) {
        return (int)((long)key * mult % size);
    }
    public void put(int key, int val) {
        remove(key);
        int h = hash(key);
        ListNode node = new ListNode(key, val, data[h]);
        data[h] = node;
    }
    public int get(int key) {
        int h = hash(key);
        ListNode node = data[h];
        for (; node != null; node = node.next)
            if (node.key == key) return node.val;
        return -1;
    }
    public void remove(int key) {
        int h = hash(key);
        ListNode node = data[h];
        if (node == null) return;
        if (node.key == key) data[h] = node.next;
        else for (; node.next != null; node = node.next)
            if (node.next.key == key) {
                node.next = node.next.next;
                return;
            }
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
struct Node {
public:
    int key, val;
    Node* next;
    Node(int k, int v, Node* n) {
        key = k;
        val = v;
        next = n;
    }
};
class MyHashMap {
public:
    const static int size = 19997;
    const static int mult = 12582917;
    Node* data[size];
    int hash(int key) {
        return (int)((long)key * mult % size);
    }
    void put(int key, int val) {
        remove(key);
        int h = hash(key);
        Node* node = new Node(key, val, data[h]);
        data[h] = node;
    }    
    int get(int key) {
        int h = hash(key);
        Node* node = data[h];
        for (; node != NULL; node = node->next)
            if (node->key == key) return node->val;
        return -1;
    }    
    void remove(int key) {
        int h = hash(key);
        Node* node = data[h];
        if (node == NULL) return;
        if (node->key == key) data[h] = node->next;
        else for (; node->next != NULL; node = node->next)
            if (node->next->key == key) {
                node->next = node->next->next;
                return;
            }
    }
};
```