Technology and Me - Java HashMap n Equals/HashCode methods

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 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();

hashmap.put(k,v);

K k2 = new K();
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.

  

Technology and Me - Java HashMap Intro

Hi,
As a techie one general thing I have learnt is to have good understanding about how HashMap in Java works. This is also often asked in almost all the technical interviews.

So today, let's visit hashMaps in java.

Hashmap is a data structure where the pairs of key and value are stored. The operation on hashmap are insert, delete and retrieve.

For understanding hashmap working, its important to understand that hash map uses a nested class called Entry (Map.Entry<K,V>) for actually storing key, value pair.

So actually entry is the object created to store the key and value. Hashmap is just a wrapper around entry. Hashmap manages the operations performed on the entries.

One more important point to remember Java collections only allow objects to be keys and values. So is for hashmap. Which means you can not have primitive data types as key or value in hashmap.

So lets see how hashmap works in a simple approach:

Lets say we have K [key class] and V [value class]
public class K {
}

public class V {
}

There is default implementation of hashCode and equals in K and V classes inherited from java.lang.Object class.

When we say
K k = new K();
V v = new V();
hashmap.put(k,v)

Hashmap creates a Map.Entry instance with (k,v).  hashmap implementation gets k.hashCode() value, figures out which bucket to place this Entry.
The buckets can be imagined as range in array of storage location.

When we say, hashmap.get(k) hashmap will again calls k.hashcode() and then figures out which bucket to look into for getting this entry.

It is general practice that, when you overwrite hashCode method, you should also overwrite equals method.

Please feel free to comment.


To be continued...
Next post  - how equals and hashcode play role in creating entry in hashmap