706. Design HashMap

Easy

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.

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

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

Solution:

While Python's dictionary uses open addressing, let's try implementing it using the separate chaining method

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.

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)

put()

If there's no node in the bucket, insert and then exit.
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()

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

The node to be removed is the first node in the linked list at that index.
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.

Last updated 2 years ago