How HashMap works internally

Question

HashMap objHashMap = new HashMap();

objHashMap.put("key1", "Value1");
objHashMap.put("key1", "Value2");

System.out.println(objHashMap.get("key1"));

Above code displaying "Value2" how and why

The very logic of the hash map is to store one item per key, if you want multiple values you need hash map of the lists, or you can use multimap — cerkiewny, Aug 06 '14 at 15:53
And also possible duplicate of http://stackoverflow.com/questions/18992101/how-is-hashmap-internally-implemented-in-java-using-linkedlist-or-array it would be nice if you could add language information because the implementation may be different in different languages. — cerkiewny, Aug 06 '14 at 15:55
You can always read [the documentation on HashMap](http://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html#put%28K,%20V%29) (though I know that seems like a pretty rash thing to do). — Hot Licks, Aug 06 '14 at 15:56

score 4 · Answer 1 · answered Jan 05 '15 at 06:20

check this

/**
* Associates the specified value with the specified key in this map. If the
* map previously contained a mapping for the key, the old value is
* replaced.
*
* @param key
*            key with which the specified value is to be associated
* @param value
*            value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or <tt>null</tt>
*         if there was no mapping for <tt>key</tt>. (A <tt>null</tt> return
*         can also indicate that the map previously associated
*         <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
    if (key == null)
    return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K , V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

Lets note down the steps one by one:

1) First of all, key object is checked for null. If key is null, value is stored in table[0] position. Because hash code for null is always 0.

2) Then on next step, a hash value is calculated using key’s hash code by calling its hashCode() method. This hash value is used to calculate index in array for storing Entry object. JDK designers well assumed that there might be some poorly written hashCode() functions that can return very high or low hash code value. To solve this issue, they introduced another hash() function, and passed the object’s hash code to this hash() function to bring hash value in range of array index size.

3) Now indexFor(hash, table.length) function is called to calculate exact index position for storing the Entry object.

4) Here comes the main part. Now, as we know that two unequal objects can have same hash code value, how two different objects will be stored in same array location [called bucket]. Answer is LinkedList. If you remember, Entry class had an attribute “next”. This attribute always points to next object in chain. This is exactly the behavior of LinkedList.

So, in case of collision, Entry objects are stored in LinkedList form. When an Entry object needs to be stored in particular index, HashMap checks whether there is already an entry?? If there is no entry already present, Entry object is stored in this location.

If there is already an object sitting on calculated index, its next attribute is checked. If it is null, and current Entry object becomes next node in LinkedList. If next variable is not null, procedure is followed until next is evaluated as null.

What if we add the another value object with same key as entered before. Logically, it should replace the old value. How it is done? Well, after determining the index position of Entry object, while iterating over LinkedList on calculated index, HashMap calls equals method on key object for each Entry object. All these Entry objects in LinkedList will have similar hash code but equals() method will test for true equality. If key.equals(k) will be true then both keys are treated as same key object. This will cause the replacing of value object inside Entry object only.

In this way, HashMap ensure the uniqueness of keys.

Hi Sameer the point 2 you have mentioned, getting the hash value by calling the hash() because of some poorly written code, have you checked if you create a separate class and dont override equals() and hashCode() then you can insert duplicate key in HashMap, So I don't think there is a separate hash() function is there. — subhashis, Dec 20 '16 at 05:41

score 1 · Answer 2 · answered Aug 06 '14 at 15:57

Because Hash maps store only unique keys for each value, this means that you can't put 2 keys with the same name in it, when you do you will overwrite the value for that key, so if you want to store 2 different values you need to store two different keys in it.

HashMap objHashMap = new HashMap();
objHashMap.put("key1", "Value1");
objHashMap.put("key2", "Value2"); //CHANGED THIS KEY to "key2"

System.out.println(objHashMap.get("key1"));

Babulal Mandal · Answer 3 · 2023-04-01T17:29:03.533

HashMap in Java is a widely used data structure, which allows key-value pairs to be stored and retrieved in constant time. In this article, we will look into how the get() and put() methods work internally, along with the process of hashing, fetching, and storing the key-value pairs.

The HashMap in Java contains an array of Node, where Node represents a class with four objects: hash, key, value, and next. The hashing process involves converting an object into an integer using the hashCode() method, which needs to be implemented properly for the HashMap to perform better.

Internal Working of HashMap in Java I have read your blog it's a fantastic article I request you sir please share my blog

How HashMap works internally

3 Answers3

Linked