Today is Christmas Eve Day 2020 and we woke up with -3 F. In addition snow and wind started yesterday afternoon. Looks like a perfect day to stay in and roast a turkey.
As a matter of fact, my wife and I prepared the turkey early this morning and put it in the oven. The raw turkey came in at 24 lbs. It had giblets and a bag of liquid for basting. We disposed of those items. Next time we roast a turkey will get a smaller one (about 11 lbs.) and from a different brand (not Jennie-O). The breast of this turkey is not in proportion to the weight. Will see how the sandwiches on ciabatta bread turned out later this afternoon.
Now let’s get to the main subject of this post.
We will tackle a second time LeetCode problem 706 Design HashMap.
On my last post Design HashMap I mentioned that the implementation was as simple as possible. That solution seemed to use too much memory. If you pay attention to the Note provided by LeetCode, each test will not exceed 10,000 operations. This means that if we only put() 10,000 key value pairs, we have no use for 90,000 entries. Based on intuition, I decided to make some changes and attempt to reduce the size of the map. This was just a guess that did not work that well. That said; you might wish to compare the execution times between this and the previous implementation.
As usual I will generate the solution using Java on a Windows 10 computer and VSCode IDE. Because of this I will need to generate a test scaffolding. Such code is NOT PART OF THE SOLUTION.
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 for us to generate a hash map with a reduced set of methods. Since this is a second pass on the problem I assume you are familiar with the requirements.
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)
This is a summary of the hash map class we need to implement and how it will be tested by LeetCode.
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
Our test code follows the test description by LeetCode. As before, we implemented a toString() method which is used to display the contents of the hash map. This is done for testing and experimentation.
/**
* Test scaffolding
*/
public class DesignHashMap2 {
/**
* 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));
}
}
This is very similar to what LeetCode described for testing. I just copied and pasted the code from the previous post. Note that I just discarded the additional loop.
/**
* Auxiliary class used to track hashmap key:value pairs.
*/
class KVNode {
// **** members ****
public int key;
public int value;
// **** constructor ****
public KVNode(int key, int value) {
this.key = key;
this.value = value;
}
}
This class was not used in our previous approach. We will use it to hold the key-value pairs for our hash map. It is a shame that Java does not support the Pair class. You can find it in other libraries (i.e., Apache Commons and Java 11). I will check if LeetCode would allow Java 11 features.
/**
* Designs and implements a HashMap without using
* any built-in hash table libraries.
*
* Runtime: 11 ms, faster than 99.41% of Java online submissions.
* emory Usage: 43.4 MB, less than 70.92% of Java online submissions.
*/
class MyHashMap {
// **** constant ****
final int INITIAL_CAPACITY = 100000;
// **** class variables ****
private KVNode[] map;
public int capacity;
// **** constructor ****
public MyHashMap() {
this.map = new KVNode[INITIAL_CAPACITY];
this.capacity = INITIAL_CAPACITY;
}
// **** map a key to a bucket number ****
private int hashFc(int key) {
return key % capacity;
}
// **** value will always be non-negative ****
public void put(int key, int value) {
// **** compute the bucket number ****
int bucket = hashFc(key);
// **** set the key value pair in the map ****
if (this.map[bucket] == null) {
this.map[bucket] = new KVNode(key, value);
} else {
this.map[bucket].key = key;
this.map[bucket].value = 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) {
// **** compute the bucket number ****
int bucket = hashFc(key);
// **** return the associated value ****
if (this.map[bucket] == null) {
return -1;
} else {
return this.map[bucket].value;
}
}
// **** remove the mapping of the specified value key
// if this map contains a mapping for the key ****
public void remove(int key) {
// **** compute the bucket number ****
int bucket = hashFc(key);
// **** remove key value pair from map ****
this.map[bucket] = null;
}
// **** for testing purpose only ****
@Override
public String toString() {
// **** initialization ****
StringBuilder sb = new StringBuilder();
// **** traverse the map collecting key value pairs ****
for (int i = 0; i < this.map.length; i++) {
if (this.map[i] != null) {
sb.append(this.map[i].key + "=" + this.map[i].value + " ");
}
}
// **** return string ****
return sb.toString();
}
}
We start the class by defining the initial (actually final) size of the map. In our previous version we set this constant to 1,000,000. I thought that perhaps the 10,000 referenced in the Notes section on the LeetCode site was a hint that we could use to reduce the number of entries in the map. It did not work, but we were able to reduce it to 100,000. Some progress but not there yet.
Our map is of type KVNode. We also declared a capacity which was not needed for this pass yet. We could have directly used the INITIAL_CAPACITY constant due to the fact that the capacity is static.
Note the hashFc() method. Hash maps use a hash function in order to reduce the space of the map. We will do so in this implementation. The hash map maps the key to an entry in the map.
On the rest of the functions we use the hashFc() to map the key to an entry in the map.
I believe the code in the methods is easy to follow. Once we get a bucket in the map we can determine if it is null or not. At that point, if needed, we create or use the KVNode to store or retrieve the key value pair. We just need to set a map entry to null to remove a key value pair.
The toString() method is only used to display the hash map. It is not required by LeetCode.
Note that if two keys collide the associated bucket can only hold one key. We could implement a mechanism to extend the bucket. We could also start with a smaller map and extend it or contract it as needed. The drawback of extending and contracting is that it is a costly operation. On the other hand, we could implement a deeper bucket and the operations will no longer be O(1). This is a design issue that must be taken into account.
We will cover two more implementations of a hash map in the next couple posts.
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,233 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