How does a Java HashMap handle different objects w

Question

As per my understanding I think:

1. It is perfectly legal for two objects to have the same hashcode.
2. If two objects are equal (using the equals() method) then they have the same hashcode.
3. If two objects are not equal then they cannot have the same hashcode

Am I correct?

Now if am correct, I have the following question: The HashMap internally uses the hashcode of the object. So if two objects can have the same hashcode, then how can the HashMap track which key it uses?

Can someone explain how the HashMap internally uses the hashcode of the object?

Answer 1

I will not get into the details of how HashMap works, but will give an example so we can remember how HashMap works by relating it to reality.

We have Key, Value ,HashCode and bucket.

For sometime, we will relate each of them with the following:

• Bucket -> A Society
• HashCode -> Society's address(unique always)
• Value -> A House in the Society
• Key -> House address.

Using Map.get(key) :

Stevie wants to get to his friend's(Josse) house who lives in a villa in a VIP society, let it be JavaLovers Society. Josse's address is his SSN(which is different for everyone). There's an index maintained in which we find out the Society's name based on SSN. This index can be considered to be an algorithm to find out the HashCode.

• SSN Society's Name
• 92313(Josse's) -- JavaLovers
• 13214 -- AngularJSLovers
• 98080 -- JavaLovers
• 53808 -- BiologyLovers

---

1. This SSN(key) first gives us a HashCode(from the index table) which is nothing but Society's name.
2. Now, mulitple houses can be in the same society, so the HashCode can be common.
3. Suppose, the Society is common for two houses, how are we going to identify which house we are going to, yes, by using the (SSN)key which is nothing but the House address

Using Map.put(key,Value)

This finds a suitable society for this Value by finding the HashCode and then the value is stored.

I hope this helps and this is open for modifications.

Answer 2

HashMap is an array of Entry objects.

Consider HashMap as just an array of objects.

Have a look at what this Object is:

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;
… 
}

Each Entry object represents a key-value pair. The field next refers to another Entry object if a bucket has more than one Entry.

Sometimes it might happen that hash codes for 2 different objects are the same. In this case, two objects will be saved in one bucket and will be presented as a linked list. The entry point is the more recently added object. This object refers to another object with the next field and so on. The last entry refers to null.

When you create a HashMap with the default constructor

HashMap hashMap = new HashMap();

The array is created with size 16 and default 0.75 load balance.

Adding a new key-value pair

1. Calculate hashcode for the key
2. Calculate position hash % (arrayLength-1) where element should be placed (bucket number)
3. If you try to add a value with a key which has already been saved in HashMap, then value gets overwritten.
4. Otherwise element is added to the bucket.

If the bucket already has at least one element, a new one gets added and placed in the first position of the bucket. Its next field refers to the old element.

Deletion

1. Calculate hashcode for the given key
2. Calculate bucket number hash % (arrayLength-1)
3. Get a reference to the first Entry object in the bucket and by means of equals method iterate over all entries in the given bucket. Eventually we will find the correct Entry. If a desired element is not found, return null