It seems like I lost track of time this week. It is early morning on Wednesday December 23, 2020 and the weather forecast calls for 8 inches of fresh snow and a low of -1 F. This would be the first time this season that we experience subzero temperatures in the city where I live.
We always should look at the positive side of things. With the snow less people will be out and about which is good for restraining new COVID-19 infections. In addition, the days are starting to get longer. We will not be able to notice it for a few weeks, but it is happening.
I brought in from the refrigerator we keep in the garage, a 24 lbs. turkey, which we will roast tomorrow morning and will consume it mostly as sandwiches. Given that it will be my wife and I consuming this bird, it will last for several weeks. We will freeze most of it and consume it as needed.
I selected LeetCode 706 Design HashMap problem. I found the subject very interested. I tinkered with three different implementations. As I was working on them I noticed that it was becoming too long and hard to follow. At that point I decided on separate projects and posts. I plan to get all of them done no later than the end of the long weekend of Christmas. Yes it is that time again!
As usual, I will develop the solution in Java using a Windows 10 computer and the VSCode IDE. If you have not tried VSCode yet, I highly recommended it. For many years, mostly for work development, I have been using different versions of Microsoft Visual Studio. Today for work related tasks, I use Visual Studio Enterprise Edition 2019. That said, for personal use, not too many IDEs work so well. In addition you can download it for free!
Design a HashMap without using any built-in hash table libraries. To be specific, your design should include these functions: o put(key, value) : Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value. o get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key. o remove(key) : Remove the mapping for the value key if this map contains the mapping for the key. Note: o All keys and values will be in the range of [0, 1000000]. o The number of operations will be in the range of [1, 10000]. o Please do not use the built-in HashMap library.
The requirements are interesting and simple. We need to implement a hash map class. In addition to the constructor, we need to implement three other methods.
It is important to note the range of key values and the number of operations. In this first attempt implementation we will go for the simplest and not considering the second note provided by LeetCode. We will talk more about it when we get to the implementation.
class MyHashMap {
/** Initialize your data structure here. */
public MyHashMap() {
}
/** value will always be non-negative. */
public void put(int key, int value) {
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
public int get(int key) {
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
public void remove(int key) {
}
}
/**
* Your MyHashMap object will be instantiated and called as such:
* MyHashMap obj = new MyHashMap();
* obj.put(key,value);
* int param_2 = obj.get(key);
* obj.remove(key);
*/
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)
As we discussed, we will need to implement four methods in our class. We also need to declare the data structures we will be using.
LeetCode has provided an example on how the solution will be tested. We will use it to test our simple implementation.
main <<< hm: 1=1 2=2 main <<< hm.get(1): 1 main <<< hm.get(3): -1 main <<< hm: 1=1 2=1 main <<< hm.get(2): 1 main <<< hm: 1=1 main <<< hm.get(2): -1
I could have chosen to read input values for pairs and operations. I decided to just implement the test in the scaffolding. Please note that the test scaffolding IS NOT PART OF THE SOLUTION.
It seems that the test code has provided a couple key and value pairs. We could assume that they were entered using the put() method. The contents of our hash map are displayed.
We then perform a couple get() calls. The first one uses an existing key value while the second a non-existing one.
The next thing we see is a dump of the contents of the hash map. Note that key 2 is now associated with value 1. We must have called the put() method.
As expected the next get(2) call returns a 1.
It seems we must have called remove(2). This is illustrated by the dump of the hash map. It is confirmed by the fact that the get(2) call returns -1 indicating the key has been removed from the hash map.
/**
* Test scaffolding
*/
public static void main(String[] args) {
// **** create my hash map ****
MyHashMap hm = new MyHashMap();
// **** put key:value pair ****
hm.put(1, 1);
// **** put key:value pair ****
hm.put(2, 2);
// ???? ????
System.out.println("main <<< hm: " + hm.toString());
// **** get value for specified key ****
System.out.println("main <<< hm.get(1): " + hm.get(1));
// **** get value for specified key ****
System.out.println("main <<< hm.get(3): " + hm.get(3));
// **** put key:value pair ****
hm.put(2, 1);
// ???? ????
System.out.println("main <<< hm: " + hm.toString());
// **** get value for specified key ****
System.out.println("main <<< hm.get(2): " + hm.get(2));
// *** remove key value pair for specified key ****
hm.remove(2);
// ???? ????
System.out.println("main <<< hm: " + hm.toString());
// **** get value for specified key ****
System.out.println("main <<< hm.get(2): " + hm.get(2));
/*
// ???? ????
System.out.println();
// **** put key ****
hm.put(12345, 67890);
// ???? ????
System.out.println("main <<< hm: " + hm.toString());
// **** get value for specified key ****
System.out.println("main <<< hm.get(12345): " + hm.get(12345));
// **** put key ****
hm.put(1000000, 1000000);
// ???? ????
System.out.println("main <<< hm: " + hm.toString());
// **** get value for specified key ****
System.out.println("main <<< hm.get(1000000): " + hm.get(1000000));
// **** put key ****
hm.put(0, 0);
// ???? ????
System.out.println("main <<< hm: " + hm.toString());
// **** get value for specified key ****
System.out.println("main <<< hm.get(0): " + hm.get(0));
// **** loop checking some additional keys ****
for (int i = 65536 - 10; i < 65536 + 10; i++) {
// **** put key:value ****
hm.put(i, i);
// ???? ????
System.out.println("main <<< hm: " + hm.toString());
}
*/
}
This is the test scaffolding I wrote. I need it because I am using my machine to develop and test the code as I go. The code IS NOT PART OF THE SOLUTION.
We start by creating a hash map. We then make the same calls listed in the example from LeetCode. They all seem to match. Let’s now look at the actual code for the hash map.
/**
* Designs and implements a HashMap without using
* any built-in hash table libraries.
*
* Runtime: 32 ms, faster than 27.20% of Java online submissions.
* Memory Usage: 45.9 MB, less than 37.26% of Java online submissions
*/
class MyHashMap {
// **** constant ****
final int INITIAL_CAPACITY = 1000000 + 1;
// **** class variables ****
private int[] values;
// **** constructor ****
public MyHashMap() {
this.values = new int[INITIAL_CAPACITY];
Arrays.fill(this.values, -1);
}
// **** value will always be non-negative ****
public void put(int key, int value) {
this.values[key] = value;
}
// **** returns the value to which the specified key is mapped,
// or -1 if this map contains no mapping for the key ****
public int get(int key) {
return this.values[key];
}
// **** remove the mapping of the specified value key
// if this map contains a mapping for the key ****
public void remove(int key) {
this.values[key] = -1;
}
// **** for testing purpose only ****
@Override
public String toString() {
// **** initialization ****
StringBuilder sb = new StringBuilder();
// **** traverse the array of keys and values ****
for (int i = 0; i < this.values.length; i++) {
// **** have a key:value pair ****
if (values[i] != -1)
sb.append(i + "=" + this.values[i] + " ");
}
// **** return string ****
return sb.toString();
}
}
For starters, in general calls to a hash map should operate in O(1) time. In this implementation we do so by declaring an array with enough entries to hold all possible values. In addition, we do not use a hash function to go from a key to a bucket in the map (implemented by an array).
In general, hash maps grow and shrink in order to avoid collisions. If collisions are allowed by declaring a smaller map, then we need to deal with them using some type of data structure backing up the operation of each bucket in the map.
Note that the number of operations has been specified. We could support a map with only 10,000 entries and a mechanism to store the key and the values. We do not implement such mechanism. We will do so in an upcoming post.
Our constructor instantiates the array of values and initializes them to -1 to indicate there are no associated values yet.
The put() method assigns a value with an entry in the array.
The get() method reads the value from the array. Note that each possible key has an associated entry in the array so there is nothing else to do. We do not have to deal with collisions in buckets.
The remove() method flags that the associate value for the specified key has been removed by setting the entry to -1.
The toString() method IS NOT PART OF THE SOLUTION. I just implemented it to be able to display the contents of the hash map.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset.
One last thing, many thanks to all 5,209 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.
Regards;
John
john.canessa@gmail.com