Hi There,
Continuing on the last topic of hashmap ..
HashCode method -
From JavaDocs - "Returns a hash code value for the object. This method is supported for the benefit of hash tables such as those provided by
Equals method -
From JavaDocs - "Indicates whether some other object is "equal to" this one."
When in hashmap, we do hashmap.get(key) based on key.hashCode() the hashmap is looked into appropriate bucket.
In ideal scenarios, the hashmaps will have one entry per bucket. But in real world scenarios, none of the hash functions are full proof. So there could be collisions.
Handling collisions:
In the following code
public class K {
Continuing on the last topic of hashmap ..
HashCode method -
From JavaDocs - "Returns a hash code value for the object. This method is supported for the benefit of hash tables such as those provided by
HashMap."Equals method -
From JavaDocs - "Indicates whether some other object is "equal to" this one."
When in hashmap, we do hashmap.get(key) based on key.hashCode() the hashmap is looked into appropriate bucket.
In ideal scenarios, the hashmaps will have one entry per bucket. But in real world scenarios, none of the hash functions are full proof. So there could be collisions.
Handling collisions:
In the following code
public class K {
@overwrite
public int hashCode(){
return 1;
}
}
public class V {
}
There is implementation of hashCode in K and returns 1 always. That means when we say:
K k = new K();
V v = new V();
}
public class V {
}
There is implementation of hashCode in K and returns 1 always. That means when we say:
K k = new K();
V v = new V();
hashmap.put(k,v);
K k2 = new K();
V v2 = new V();
V v2 = new V();
hashmap.put(k2,v2);
The two objects k and k2 fall in the same bucket and then they form a list of objects.
Very simply, if you imagine:
bucket1 [hashcode 1-10]
bucket2 [hashcode 11-20]
The storing of the entries will be like this
bucket1 - (k2,v2)->(k,v)->null
bucket2 -
In this particular case if we do hashmap.get(k2), because the hashcode for k and k2 is same, the equals method of class k will be called.
if(k.equals(k2)) then, k2 and k will be the same keys and the v2 will overwrite value v.
if(!k.equals(k2)) then k2 and k will be two separate entries.
The two objects k and k2 fall in the same bucket and then they form a list of objects.
Very simply, if you imagine:
bucket1 [hashcode 1-10]
bucket2 [hashcode 11-20]
The storing of the entries will be like this
bucket1 - (k2,v2)->(k,v)->null
bucket2 -
In this particular case if we do hashmap.get(k2), because the hashcode for k and k2 is same, the equals method of class k will be called.
if(k.equals(k2)) then, k2 and k will be the same keys and the v2 will overwrite value v.
if(!k.equals(k2)) then k2 and k will be two separate entries.
In second case where k & k2 are not equal, How it will search in given bucket?
ReplyDeleteHi Interstellar -
DeleteIn the second case, as I said earlier, it will form a linked list [k2 -> k]. Then if you do hashmap.get(k) it goes in bucket 1 and searches for the key in the linked list. Till it finds a entry with key matching. So we say in some worst cases, hashmap might not have O(1) retrieval. Hope that answers..