057.md

706. Design HashMap

Difficulty: 🟢 Easy

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.

Examples:

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.

Solutions

Example solution

Python 3

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

class MyHashMap:
    def __init__(self):
        self.capacity = 101
        self.bucket = [None] * self.capacity

    def _hash(self, key: int) -> int:
        return hash(key) % self.capacity

    def put(self, key: int, value: int) -> None:
        index = self._hash(key)
        if self.bucket[index] is None:
            self.bucket[index] = ListNode(key, value)
        else:
            curr = self.bucket[index]
            while curr:
                if curr.key == key:
                    curr.value = value
                    return
                if curr.next is None:
                    break
                curr = curr.next
            curr.next = ListNode(key, value)

    def get(self, key: int) -> int:
        index = self._hash(key)
        curr = self.bucket[index]
        while curr:
            if curr.key == key:
                return curr.value
            curr = curr.next
        return -1

    def remove(self, key: int) -> None:
        index = self._hash(key)
        prev = None
        curr = self.bucket[index]
        while curr:
            if curr.key == key:
                if prev:
                    prev.next = curr.next
                else:
                    self.bucket[index] = curr.next
                return
            prev = curr
            curr = curr.next

# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)

The given solution uses a simple implementation of a HashMap using a hash function and an array of linked lists.

Here is a step-by-step overview of the solution:

1. Define a ListNode class that represents a node in the linked list. Each node contains a key, a value, and a reference to the next node (next).
2. Initialize the MyHashMap class with a fixed capacity of 101 and an array called bucket of size capacity to store the linked lists.
3. Implement a private _hash function that takes a key as input and returns the hash value (index) based on the built-in hash function and the capacity of the HashMap.
4. Implement the put method that adds or updates a (key, value) pair in the HashMap:
   • Calculate the hash value using the _hash function.
   • If the bucket at the calculated index is None, create a new ListNode with the key and value and assign it to the bucket.
   • If the bucket at the calculated index is not None, iterate through the linked list at that index:
     • If the current node's key is equal to the key we want to put, update the value of the current node and return (no duplicates are allowed).
     • If the current node's next is None, break the loop and add a new ListNode with the key and value at the end of the linked list.
5. Implement the get method that returns the value associated with a given key in the HashMap:
   • Calculate the hash value using the _hash function.
   • Iterate through the linked list at the calculated index and check if any node's key matches the given key. If found, return the value of that node.
   • If the loop completes without finding a match, return -1.
6. Implement the remove method that removes a (key, value) pair from the HashMap:
   • Calculate the hash value using the _hash function.
   • Iterate through the linked list at the calculated index:
     • If the current node's key is equal to the given key, update the previous node's next reference to skip the current node and remove it from the linked list.
7. The MyHashMap class is now ready to be instantiated and used.

Complexity Analysis

The time complexity for the put, get, and remove methods is O(1) on average. In the worst case, when there are many collisions and all keys are hashed to the same index, the time complexity becomes O(n), where n is the number of elements in the HashMap. However, since the capacity of the HashMap is fixed at 101, the worst case is limited.

The space complexity is O(capacity + n), where capacity is the fixed size of the HashMap (101) and n is the number of elements in the HashMap. The space is used to store the array of linked lists and the nodes in the linked lists.

Summary

The given solution implements a HashMap without using built-in hash table libraries. It uses a hash function and an array of linked lists to store the (key, value) pairs. The time complexity of the put, get, and remove methods is O(1) on average. The space complexity is O(capacity + n), where capacity is the fixed size of the HashMap and n is the number of elements in the HashMap.

NB: If you want to get community points please suggest solutions in other languages as merge requests.