Hashmap Internal Implementation Analysis in Java

Full detailed analysis of java.util.HashMap’s implementation, its internals and working concepts.

java.util.HashMap.java

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

It says the maximum size to which hashmap can expand, i.e, till 2^(30) = 1,073,741,824

java.util.HashMap.java

    /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 16;

    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

It says default size of an array is 16 (always power of 2, we will understand soon why it is always power of 2 going further) and load factor means whenever the size of the hashmap reaches to 75% of its current size, i.e, 12, it will double its size by recomputing the hashcodes of existing data structure elements.

Hence to avoid rehashing of the data structure as elements grow it is the best practice to explicitly give the size of the hashmap while creating it.

Do you foresee any problem with this resizing of hashmap in java? Since java is multi threaded it is very possible that more than one thread might be using same hashmap and then they both realize the need for re-sizing the hashmap at the same time which leads to race condition.

What is race condition with respect to hashmaps? When two or more threads see the need for resizing the same hashmap, they might end up adding the elements of old bucket to the new bucket simultaneously and hence might lead to infinite loops. FYI, in case of collision, i.e, when there are different keys with same same hashcode, internally we use single linked list to store the elements. And we store every new element at the head of the linked list to avoid tail traversing and hence at the time of resizing the entire sequence of objects in linked list gets reversed, during which there are chances of infinite loops.

For example, lets assume there are 3 keys with same hashcode and hence stored in linked list inside a bucket [below format is in object_value(current_address, next_address) ]
Initial structure: 1(100, 200) –> 2(200, 300) –> 3(300, null)
After resizing by thread-1: 3(300, 200) –> 2(200, 100) –> 1(100, null)
When thread-2 starts resizing, its again starts with 1st element by placing it at the head:
1(100, 300) –> 3(300, 200) –> 2(200, 100) ==> which becomes a infinite loop for next insertion and thread hangs here.

java.util.HashMap.java

	/**
     * 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;
    }

Here it
1. re-generates the hashcode using hash(int h) method by passing user defined hashcode as an argument
2. generates index based on the re-generated hashcode and length of the data structure.
3. if key exists, it over-rides the element, else it will create a new entry in the hashmap at the index generated in Step-2

Step-3 is straight forward but Step-1&2 needs to have deeper understanding. Let us dive into the internals of these methods…

Note: These two methods are very very important to understand the internal working functionality of hashmap in openjdk

java.util.HashMap.java

	/**
     * Applies a supplemental hash function to a given hashCode, which
     * defends against poor quality hash functions.  This is critical
     * because HashMap uses power-of-two length hash tables, that
     * otherwise encounter collisions for hashCodes that do not differ
     * in lower bits. Note: Null keys always map to hash 0, thus index 0.
     */
    static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

	/**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

here:
‘h’ is hashcode(because of its int data type, it is 32 bit)
‘length’ is DEFAULT_INITIAL_CAPACITY(because of its int data type, it is 32 bit)

Comment from above source code says…
Applies a supplemental hash function to a given hashCode, which defends against poor quality hash functions. This is critical because HashMap uses power-of-two length hash tables, that otherwise encounter collisions for hashCodes that do not differ in lower bits. What do this means???

It means that if in case the algorithm we wrote for hashcode generation does not distribute/mix lower bits evenly, it will lead to more collisions. For example, we have hashcode logic of “empId*deptId” and if deptId is even, it would always generate even hashcodes because any number multiplied by EVEN is always EVEN. And if we directly depend on these hashcodes to compute the index and store our objects into hashmap then
1. odd places in the hashmap are always empty
2. because of #1, it would leave us to use only even places and hence double the number of collisions

For example,
I am considering some hash codes which our code might generate, which are very valid as they are different, but we will prove these to be useless soon

1111110111011010101101010111110
1100110111011010101011010111110
1100000111011010101110010111110

I am considering these sequences directly (without using hash function) and pass it for indexFor method, where we do AND operation between ‘hashcode’ and ‘length-1(which will always give sequence of 1’s as length is always power of 2)’. Why is hashmap length always power of 2? it is because when we do (user_hash_code & size-1), it will consider only the first few bits (in this case 4 bits) which are used to decide the bucket location.
As we are considering the length as default length, i.e, 16, binary representation of (16-1) is 1111
this is what happens inside indexFor method

1111110111011010101101010111110 & 0000000000000000000000000001111 = 1110
1100110111011010101011010111110 & 0000000000000000000000000001111 = 1110
1100000111011010101110010111110 & 0000000000000000000000000001111 = 1110

From this we understand that all the objects with these different hascodes would have same index which means they would all go into the same bucket, which is a BIG-FAIL as it leads to arraylist complexity O(n) instead of O(1)

Comment from above source code says…
that otherwise encounter collisions for hashCodes that do not differ in lower bits.

Notice this sequence of 0-15 (2-power-4), its the default size of Hashtable

0000 - 0	1000 - 8
0001 - 1	1001 - 9
0010 - 2	1010 - 10
0011 - 3	1011 - 11
0100 - 4	1100 - 12
0101 - 5	1101 - 13
0110 - 6	1110 - 14
0111 - 7	1111 - 15

If we notice here, hashmap with power-of-two length 16(2^4), only last four digits matter in the allocation of buckets, and these are the 4 binary lower bit digit variations that play prominent role in identifying the right bucket.

Keeping the above sequence in mind, we re-generated the hashcode from hash(int h) by passing the existing hascode which makes sure there is enough variation in the lower bits of the hashcode and then pass it to indexFor() method , this will ensure the lower bits of hashcode are used to identify the bucket and the rest higher bits are ignored.
For example, taking the same hascode sequences from above example

Our hash code 1111110111011010101101010111110 when regenerated with hash(int h) method, it generates new hashcode ==> 1111001111110011100110111011010

this is what happens inside indexFor method
1111110111011010101101010111110 ==> 1111001111110011100110111011010
1100110111011010101011010111110 ==> 1100000010010000101101110011001
1100000111011010101110010111110 ==> 1100110001001000011011110001011

passing these set of new hashcodes to indexFor() method
1111001111110011100110111011010 & 0000000000000000000000000001111 = 1010
1100000010010000101101110011001 & 0000000000000000000000000001111 = 1001
1100110001001000011011110001011 & 0000000000000000000000000001111 = 1011

so here it is clear that because of the regenerated hashcode, the lower bits are will distributed/mixed leading to unique index which leads to different buckets avoiding collisions.

Why only these magic numbers 20, 12, 7 and 4. It is explained in the book: “The Art of Computer Programming” by Donald Knuth.
Here we are XORing the most significant bits of the number into the least significant bits (20, 12, 7, 4). The main purpose of this operation is to make the hashcode differences visible in the least significant bits so that the hashmap elements can be distributed evenly across the buckets.

java.util.HashMap.java

	/**
     * 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;
    }

Going back to previous steps:
1. re-generates the hashcode using hash(int h) method by passing user defined hashcode as an argument
2. generates index based on the re-generated hashcode and length of the data structure.
3. if key exists, it over-rides the element, else it will create a new entry in the hashmap at the index generated in STEP-2

Steps1&2 must be clear by now.

Step3:
What happens when two different keys have same hashcode?
1. if the keys are equal, i.e, to-be-inserted key and already-inserted key’s hashcodes are same and keys are same (via reference or via equals() method) then over-ride the previous key-value pair with the current key-value pair.
2. if keys are not equal, then store the key-value pair in the same bucket as that of the existing keys.

When collision happens in hashmap? it happens in case-2 of above question.

How do you retrieve value object when two keys with same hashcode are stored in hashmap? Using hashcode wo go to the right bucket and using equals we find the right element in the bucket and then return it.

How does different keys with same hashcode stored in hashmap? Usual answer is in bucket but technically they are all stored in a single linked list. Little difference is that insertion of new element to the linked list is made at the head instead of tail to avoid tail traversal.

What is bucket and what can be maximum number of buckets in hashmap? A bucket is an instance of the linked list (Entry Inner Class in my previous post) and we can have as many number of buckets as length of the hashmap at maximum, for example, in a hashmap of length 8, there can be maximum of 8 buckets, each is an instance of linked list.

java.util.HashMap.java

	/**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *
     * <p>More formally, if this map contains a mapping from a key
     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
     * key.equals(k))}, then this method returns {@code v}; otherwise
     * it returns {@code null}.  (There can be at most one such mapping.)
     *
     * <p>A return value of {@code null} does not <i>necessarily</i>
     * indicate that the map contains no mapping for the key; it's also
     * possible that the map explicitly maps the key to {@code null}.
     * The {@link #containsKey containsKey} operation may be used to
     * distinguish these two cases.
     *
     * @see #put(Object, Object)
     */
    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        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)))
                return e.value;
        }
        return null;
    }

1. re-generates the hashcode using hash(int h) method by passing user defined hashcode as an argument
2. generates index based on the re-generated hashcode and length of the data structure.
3. point to the right bucket, i.e, table[i], and traverse through the linked list, which is constructed based on Entry inner class
4. when keys are equal and their hashcodes are equal then return the value mapped to that key

Also look at
creating our own hashmap in java

About these ads

22 Responses to Hashmap Internal Implementation Analysis in Java

  1. FoxKid says:

    Nice explanation .. Thanks..

  2. Pingback: order of hashmap/hashtable in BIG-O Notation | java tech stack

  3. Pingback: Creating our own hashmap in java | java tech stack

  4. Devendra says:

    very much deep explanation it is

  5. janardhan bommineni says:

    keep it up boss. How did you learn all this stuff ?

  6. gaurav Aggarwal says:

    thanks Niranjan, it was of big help, Can you explain one thing when does resizing of an hash map occurs, and may be if possible you can elaborate more on the resizing and the race conditions associated with it..

  7. Akshay Zunke says:

    Great article…

  8. sarvesh Pawar says:

    Awesome! !! Just what I wanted.. Thanks…

  9. Aditya Arora says:

    Very nice description of hash method.
    If you have seen code for putForNullKey() or getForNullKey(), there they have used a for loop. Don’t you think that for loop will always run only once. Because there can be only single entry with null key and that will be stored in table[0].
    So my question is Can we have more than one values in table[0]??

  10. naveen1051 says:

    This article helps us to understand the interanal algorithms in many of collection framework’s implementation classes.

    Good job Niranjan.

    -Naveen Matta

  11. Nitin says:

    Hi Niranjan,

    I am adding some few question on Hashmap asked by interviewer. Please post these ans in your blog it will be helpful to others.

    1. Can hashMap store 2 Diff value with same key?
    2. Hashcode and Equals method overriding is compulsory for HashMap and why?
    3. What is importance for overriding hashcode and equals method, Key or value or both and how?

    • Someone says:

      Hi Nitin..
      Following are the answers as per my knowledge…
      1. If you provide the same key name…then it will overwrite the previous value… and put method will return you the original value..
      2. If you don’t override hashCode method..then you won’t be able to locate you bucket when you use get method…. it is because default hashCode of Object class will return you different hashCode every time.
      If you are overriding hashCode then its compulsory that you override equals too… or if you are overriding equals then you should override hashCode too (in case you need hashCodes). This is a contract between hashCode and equals and if you break it…the program will work unpredictable.
      3. Importance is for Key mainly….. as hashCode is calculated on Keys

  12. Rajdeo Kumar says:

    please can you explain >>>>> case scnario—-
    it is because when we do (user_hash_code & size-1),

  13. Shivanand Amalyal says:

    Different keys with same hash codes will be stored in the same bucket.But what it is difference between adding the next link at the head instead of tail.
    While retrieving,based on the hash code it identifies the bucket and there are 2 entries in the bucket.Now it applies equals on keys and gets the value.Assume key does not match with the 1st key in the bucket.So how it will go to the next key.Is it based on the address of the next element in the 1st node?Please explain me clearly.

  14. Someone says:

    This is amazing explanation and it made by life easy..Thanks! :)

  15. diya says:

    Hi Niranjan,
    Can you explain me the below part:

    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
    ..I was not able to understand and also y specifically using 20, 12, 7, 4

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

amintabar

Amir Amintabar's personal page

101 Books

Reading my way through Time Magazine's 100 Greatest Novels since 1923 (plus Ulysses)

Seek, Plunnge and more...

My words, my world...

ARRM Foundation

Do not wait for leaders; do it alone, person to person - Mother Teresa

Executive Management

An unexamined life is not worth living – Socrates

Diabolical or Smart

Nitwit, Blubber, Oddment, Tweak !!

javaproffesionals

A topnotch WordPress.com site

thehandwritinganalyst

Just another WordPress.com site

java coding algorithms

before software can be reusable it first has to be usable - Ralph Johnson

Follow

Get every new post delivered to your Inbox.

Join 152 other followers