Design HashMap
Problem Description
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 thekeyalready exists in the map, update the correspondingvalue.int get(int key)returns thevalueto which the specifiedkeyis mapped, or-1if this map contains no mapping for thekey.void remove(key)removes thekeyand its correspondingvalueif the map contains the mapping for thekey.
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:
Constraints:
- 0 <= key, value <= 106
- At most 104 calls will be made to
put,get, andremove.
Solve it on LeetCode
Approaches
1. Array of List Nodes
Intuition:
The simplest way to implement a hashmap is to use an array where each index holds a linked list of key-value pairs. This method handles collisions by chaining entries together in the form of a linked list. When adding a new entry, we first compute its hash code which gives us the index to put the key-value pair into, and we toggle through the linked list to either update the value or insert a new node.
Code:
- Time Complexity:
O(N/B), whereNis the number of all possible keys andBis the number of buckets. - Space Complexity:
O(M + N), whereMis the given element size andNis the bucket size which is 10000 here.
2. Double Hashing
Intuition:
By using a secondary hashing technique, we can better address the issue of collision. This involves using an open addressing scheme where slots are utilized in alternative locations if collisions occur. Double hashing uses two hash functions to compute bucket locations.
Code:
- Time Complexity:
O(1)for put, get, and delete operations. - Space Complexity:
O(U)where U is the universe of keys. In this approach, space can be large if the range of key values is vast.
3. Binary Search Tree in Buckets
Intuition:
Instead of using linked lists for collisions, we can use a Binary Search Tree (BST). This gives faster operations in a scenario with worst-case time complexity, and makes the performance more stable by reducing the potential of long chains experienced with a basic linked list structure. This approach provides O(log N) operations where N is the number of keys stored in the bucket.
Code:
- Time Complexity:
O(log N)whereNis the number of elements in a bucket. - Space Complexity:
O(N)whereNis the total number of elements.