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.
Create a ListNode class. It is the node for LinkedList. It stores key and value pair.
Create an array named nodes of ListNode type. It basically works like the HashMap .
In the constructor initialize the array.
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.
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 .
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.
Time Complexity: O(1) on average, O(n) for worst-case
Space Complexity:O(1), the number of entries is fixed.
The code can be found here.
LeetCode
I have been solving Leetcode problems for around a year or so. Suddenly I have developed a passion of writing tutorials for these problems. I am starting with Leetcode problem, in future I will try to make tutorials on Spring,Android,Java,Algorithms and many more.
Follow me on medium - https://sourav-saikia.medium.com
Follow me on dev.to - https://dev.to/sksaikia
Follow me on twitter - https://twitter.com/sourav__saikia
Connect on Linkedin - www.linkedin.com/in/sourav-kumar-saikia
The following table contains all the problems with their respective solution tutorials. I will try to add more articles to it soon.
| Problem Name | Problem No | Article Links |
|---|---|---|
| Contains Duplicate | 217 | https://sourav-saikia.medium.com/leetcode-217-contains-duplicate-solution-36f48793bce0 |
| Jewels and Stones | 771 | https://sourav-saikia.medium.com/leetcode-771-jewels-and-stones-e35a368fc37 |
March LeetCoding Challenge
| Problem Name | Problem No | Article Links |
|---|---|---|
| Distribute Candies | 575 | https://medium.com/dev-genius/march-leetcoding-challenge-2021-problem-1-distribute-candies-f37f66ea7ee9 |
| Set Mismatch | 645 | https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-2-set-mismatch-4abd5ee491c9 |
| Missing Number | 268 | https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-3-missing-number-ae8ee45a58cb |
| Intersection of Two Linked Lists | 160 | https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-4-intersection-of-two-linked-lists-a775449b5563 |
| Average of Levels in Binary Tree | 637 | https://medium.com/dev-genius/march-leetcoding-challenge-2021-day-5-average-of-levels-in-binary-tree-ac886b2b42e8 |
| Short Encoding of Words | 820 | https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-6-short-encoding-of-words-7fed4bfae557 |
| Remove Palindromic Subsequences | 1332 |
Check the previous problems for the March LeetCoding Challenge 2021.
Top comments (0)