Today, we will solve the 7th problem of the March LeetCoding Challenge.

Problem Statement

Design a HashMap without using any built-in hash table libraries.

To be specific, your design should include these functions:

• put(key, value) : Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value.

• get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.

• remove(key) : Remove the mapping for the value key if this map contains the mapping for the key.

Example:

MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);          
hashMap.put(2, 2);         
hashMap.get(1);            // returns 1
hashMap.get(3);            // returns -1 (not found)
hashMap.put(2, 1);          // update the existing value
hashMap.get(2);            // returns 1 
hashMap.remove(2);          // remove the mapping for 2
hashMap.get(2);            // returns -1 (not found)

Note:

• All keys and values will be in the range of [0, 1000000].

• The number of operations will be in the range of [1, 10000].

• Please do not use the built-in HashMap library.

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. 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 — LinkedList: **The previous solution was accepted because the key values are not negative. But in general, that is not the case. So we will try to improve the solution and find the hashed index value and store it in the array. To understand the core concepts behind HashMap and it’s internal implement, check out this amazing youtube playlist. (Youtube).

So, by checking the videos we can understand that we may get the same hashed index for different keys(called collision). In order to resolve it, we will use LinkedList.

Let’s go through the whole algorithm once.

1. Create a ListNode class. It is the node for LinkedList. It stores key and value pair.

2. Create an array named nodes of ListNode type. It basically works like the HashMap .

3. In the constructor initialize the array.

4. put method: At first, find the hashed value for the given key . Check whether any other value is stored at that place or not. If not, create a ListNode with (-1,-1) key-value pair and store it in the nodes array. If it is present, then get the reference to the node (prev). If prev.next is null, then create a new ListNode with key-value pair. Else replace the value of the prev.next node.

5. get method: Repeat the process of finding hashed value and getting reference to the ListNode(prev). If prev.next is null , then return -1 else return prev.next.value .

6. remove method: Repeat the process of finding hashed value and getting the reference to the ListNode(prev).To remove that key-value pair from the array, do prev.next=prev.next.next .(Deleting a node from the LinkedList)

The detailed code along with comments is given below.

Space Complexity:O(1), the number of entries is fixed.

The code can be found here.

Check the previous problems for the March LeetCoding Challenge 2021.

1. March LeetCoding Challenge — Day 1 — Distribute Candies

2. March LeetCoding Challenge — Day 2 — Set Mismatch

3. March LeetCoding Challenge — Day 3 — Missing Number

4. March LeetCoding Challenge — Day 4 — Intersection of Two Linked Lists

5. March LeetCoding Challenge — Day 5 — Average of Levels in Binary Tree

6. March LeetCoding Challenge — Day 6— Short Encoding of Words