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

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.

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jaydeep

Jaydeep

Full Stack Programmer, love to solve problem’s during free time.