Design HashMap without using any built-in hash table libraries.
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 thekey
already exists in the map, update the correspondingvalue
.int get(int key)
returns thevalue
to which the specifiedkey
is mapped, or-1
if this map contains no mapping for thekey
.void remove(key)
removes thekey
and its correspondingvalue
if 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
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 toput
,get
, andremove
.
Solution
So in this problem, we are asked to design a HashMap without using any library functions. Here we are going to discuss two approaches to this problem.
Approach 1 — Array: With this approach, we will initialize an array of a certain size with -1. We will use the given key
as the index of the array and will store the given value
in the array with that index and when remove will assign -1 for that key(index position). We can use this method because the key
is always positive. This is a pretty straight forward code.
Time Complexity :O(1),for get, put, remove methods.
Space Complexity :O(1), the array will occupy 1000001 spaces.
Approach 2- List of custom class: With this approach, we will create a class with two property key and value. Initialize a List of custom class. For a given key will check the list has any object with the key ? If not will add a new item into the list else will update the value of the found item in the list.
Time Complexity :O(N),for get, put, remove methods.
Space Complexity :O(N).