1. What is a Map?
Answer: Map does not directly implement java.utill.Collection interface unlike List and Set. It is part of Java Collection but doesn't carry the behavior like add(), remove() etc.
Map store the elements in key-value pair provided key should be unique. If you try to add two different values with same key, Map overwrites the old value with new value if key is same. So we can say that Map doesn't allow the duplicate keys.
Example:
Map store the elements in key-value pair provided key should be unique. If you try to add two different values with same key, Map overwrites the old value with new value if key is same. So we can say that Map doesn't allow the duplicate keys.
Example:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | import java.util.HashMap; import java.util.Map; public class MapTest { public static void main(String[] args) { //1. Initializing Map Map<Integer, String> myMap = new HashMap<>(); //2. Putting values in Map with corresponding keys myMap.put(1, "John"); myMap.put(2, "Tom"); myMap.put(3, "Jerry"); myMap.put(4, "John"); //There won't be any overwriting as key is unique, Map allows duplicate values. myMap.put(1, "Alan"); //It will overwrite the value against key "1" to "Alan" from "John" //3. Iterating over Map for(Integer key : myMap.keySet()){ System.out.println("key: "+ key + ", value: "+myMap.get(key)); } } } |
and second at line number 14 Map won't overwrite as duplicate values are allowed inside Map provided keys are different.
2. Explain class hierarchy of Map?
Answer: Class hierarchy of Map is as follows:
 |
| Fig : Map class hierarchy |
Map has following implementation classes :
1. HashMap : It is default implementation of Map interface based on concept of hashing. It does not maintain the insertion order.
2. LinkedHashMap : It provides all the behavior of HashMap additionally it maintain the insertion order of keys.
3. TreeMap : It provides all the behavior of HashMap additionally it stores the keys in sorted order.
4. ConcurrentHashMap : It provides all the behavior of HashMap additionally it is designed for Multithreading environment. So we can say that it is concurrent version of HashMap.
3. How HashMap works?
Answer: In order to explain how HashMap works you actually need to explain two behavior:
1. How we put values inside HashMap?
Answer : put(key, value) method defined to put value into HashMap.
2. How we get (retrieve) values from HashMap?
Answer : get(key) method defined to retrieve value from HashMap.
Before I will discuss how HashMap works first look at following three important methods which are use by HashMap internally :
1. hashCode() : It is defined in Object class. hashCode() method returns a unique(except Hash-collision) number for every different object. For two different object it can return same hash code. It gives the hash code of current object.
2. equals(Object o) : It is also defined in Object class. It always returns true if two object are same otherwise false. For two different object it will never return true. It takes one object as input and compare it with current object.
3. hash() : It is defined in HashMap class. Since hashCode() method returns long number hence in order to fit these big numbers in bucket (array of Entry object) size, HashMap takes help of hash() method.
1. hashCode() : It is defined in Object class. hashCode() method returns a unique(except Hash-collision) number for every different object. For two different object it can return same hash code. It gives the hash code of current object.
2. equals(Object o) : It is also defined in Object class. It always returns true if two object are same otherwise false. For two different object it will never return true. It takes one object as input and compare it with current object.
3. hash() : It is defined in HashMap class. Since hashCode() method returns long number hence in order to fit these big numbers in bucket (array of Entry object) size, HashMap takes help of hash() method.
put(key, value) : put(key, value) method performs below steps internally :
1. It computes hash code of key by using hashCode() method declare in Object class.
2. It passes hascode returned in step 1 to internal hash(hash code) method. Output of hash() function gives the bucket location where value should store.
Bucket is nothing but array of entry object, You can assume it is like Entry<K,V> entry[];
So output of step 2 (hash() method) is nothing but just the index of entry array where new entry need to stored.
 |
| Fig : Entry array structure |
Entry is a class which has two fields Key and Value. So HashMap first create object of Entry class with provided input key and input value and then stores this entry object in entry array(bucket).
3. It uses bucket location returned in above step which is the location where value(Entry object) need to be stored.
4. It checks whether or not some other Entry object is already stored in that location in order to check for duplicate key.
HashMap has created entry object with input key and value so far. Now it checks whether any other entry object already stored in that location.
5. if it found any Entry object at that location then It checks whether the key that already stored at the location is same as input key. If it finds both are same key then it simply replace the old Entry object with new Entry object otherwise it simply add new Entry object there with new key and value.
In order to verify both the keys are same or not HashMap checks for following scenario out of which only one holds true:
In order to verify both the keys are same or not HashMap checks for following scenario out of which only one holds true:
I. It first calls hashcode() method on both the keys(input key and already stored key). If hascode value of both the keys are same then HashMap call equals() method on both the keys and if equals() method returned true then it means both the keys are same(duplicate key). In this case HashMap replaces the old entry object with new entry object.
II. If hashCode() of both the keys are same but equals() method returned false then it means both are two different keys. In this case HashMap creates a LinkedList at given index and stored new entry object and old entry object both there. So in future if same scenario repeats for some different key then that will also get added to same linked list.
 |
In above figure we try to insert key = 6 and value = "NZ", now assume hash() method returned index location as 2 due to Hash- Collision. Since we already have one entry at index 2 with key = 3 hence Hashmap will take help of hashCode() and equals() method as mentioned above.
hashCode() method will return same hashCode (hashCode() method always returns same hashCode for same object every time)as it is case of Hash-Collision but equals() method will return false since key = 3 and key = 6 are two different object. HashMap will create a linked list here as shown and will store both the Entry object.
Note:
-> Two different objects can produce same hash code, this scenario know as Hash-Collision. To handle this scenario HashMap does double check using equals() (since equals() method never returns true for two different object) method in order to ensure whether it's Hash-Collision(two different keys) or duplicate keys.
hashCode() method will return same hashCode (hashCode() method always returns same hashCode for same object every time)as it is case of Hash-Collision but equals() method will return false since key = 3 and key = 6 are two different object. HashMap will create a linked list here as shown and will store both the Entry object.
Note:
-> Two different objects can produce same hash code, this scenario know as Hash-Collision. To handle this scenario HashMap does double check using equals() (since equals() method never returns true for two different object) method in order to ensure whether it's Hash-Collision(two different keys) or duplicate keys.
-> Since input of hash() method of HashMap is hash code returned by hashCode() method. Hence if you pass same hash code the output(index location) will always be same. If the hash code of two different object are same then also hash() method will always return same index location for both the object.
-> There are rare scenarios where collision occurs in hash() method itself in this cases it returned the same index location for two different hash codes. To resolve this collision HashMap takes help of hashCode() and equals() method same as in case of HashCode-Collision.
-> Please not from Java 8 Linked-list get converted into binary tree after it reaches to a defined size to improve performance.
get(key) : get(key) method performs below steps internally :
1. It computes hash code of key by using hashCode() method declare in Object class. As we discussed above hashCode() method always return same value for same object no matter how many time you invoke the method.
2. It passes hascode returned in step 1 to internal hash(hash code) method. Output of hash() function gives the bucket location from where we need to retrieve the value. It will return same bucket location as It returned in case of put() method for same key.
3. Next it will verify key using equals() method in order to handle Linked-list case. There are two possible scenario:
i. There will be only one entry object at given bucket location.
ii. There will be a Linked list at given bucket location.
First case is very straight forward where it will directly retrieve value form Entry object and will return the same.
In second case it will iterate over all the nodes of Linked-list and will call equals() method on key stored at each node till equals method returns true. Node at which equals() method will return true, it will retrieve value from there and return the same.
4. What is the contract between equals() and hashCode() method?
Answer: Contract is as follows "Two object can produce two different hash code but they may or may not be equal(equals() method can return true of false) but if equals() method returns true for two object then they should produce same hash code".
Note: If you are using object of custom class(for example Employee) as key in HashMap then your class should fulfill above mentioned contract.
If your custom class fails to fulfill above contract then HashMap won't work as it should.
If you are using object of predefined classes like String, Integer etc as key in HashMap then contract is already in place.
Note: If you are using object of custom class(for example Employee) as key in HashMap then your class should fulfill above mentioned contract.
If your custom class fails to fulfill above contract then HashMap won't work as it should.
If you are using object of predefined classes like String, Integer etc as key in HashMap then contract is already in place.
5. What are the prerequisites to use object of custom class as key?
Answer: There are no as such prerequisites to use any custom class' object as key. As I mentioned above that your class should follow contract of hashCode() and equals() method in order to use them as key.
But as we know these two methods are defined in Object class and as per their default implementation in Object class they follow the contract.
So as far as your custom class doesn't override any of these two methods your custom class will get default behavior of these two methods. Hence you can use object of your custom class as key in Hashmap.
Note: If you want to overrides(modify) any of these two method in your custom class then you should override both the methods in order to maintain their contract.
Answer: In above code we have overrided both hashCode() and equals() method. We kept the default implementation for equals() method and modified the hashCode() as such that it will always return 1 for all object.
If we use objects of MyCustomKey as key for HashMap then HashMap will behave as follows:
1. For all keys(objects of MyCustomKey) HashMap will get same hash code(which is 1) which will lead to same bucket location.
2. It will be a Hash-Collision scenario and to handle it HashMap will take help of equals() method.
3. Since we have not modified equals() method and kept the default implementation hence equals will return false for two different keys(objects), hence HashMap will create Linked-List to store the input value.
So all the keys(objects) will end up to same bucket location and HashMap will add all of them in same Linked-list one after one.
It will hurt the performance of HashMap since It has to go through entire linked list to add or get value every time.
6. What will be behavior of HashMap in below case if we use object of MyCustomKey as key?
1 2 3 4 5 6 7 8 9 10 11 12 13 | class MyCustomKey{ @Override public int hashCode() { return 1; } @Override public boolean equals(Object obj) { return super.equals(obj); } } |
If we use objects of MyCustomKey as key for HashMap then HashMap will behave as follows:
1. For all keys(objects of MyCustomKey) HashMap will get same hash code(which is 1) which will lead to same bucket location.
2. It will be a Hash-Collision scenario and to handle it HashMap will take help of equals() method.
3. Since we have not modified equals() method and kept the default implementation hence equals will return false for two different keys(objects), hence HashMap will create Linked-List to store the input value.
So all the keys(objects) will end up to same bucket location and HashMap will add all of them in same Linked-list one after one.
It will hurt the performance of HashMap since It has to go through entire linked list to add or get value every time.
No comments:
Post a Comment