How Does HashMap Work Internally in Java

                 One of the most frequently asked Core Java interview questions is "How does HashMap work internally in Java?" Many candidates struggle to explain the internal implementation of HashMap clearly, which can negatively impact their interview performance.

This question helps interviewers assess a candidate's understanding of the Java Collections Framework and core Java concepts. Therefore, it should be on your preparation checklist before attending any Core Java interview.

HashMap works on the principle of hashing. To understand how HashMap works internally, you should first be familiar with the following concepts:

• Hash Function

• Hash Value (Hash Code)

• Bucket

What Are a Hash Function, Hash Value, and Bucket?

          The hashCode() method is the hash function in Java that returns an integer value representing an object. One important point to note is that this method is defined in the Object class, which is the superclass of all Java classes.

The following is the implementation (method declaration) of the hashCode() method in the Object class:

    public native int hashCode();

       The most important point to note from the above method declaration is that the hashCode() method returns an int value.

The integer value returned by the hashCode() method is known as the hash value (or hash code) of the object.

      What is bucket ?

           
           A bucket is used to store key-value pairs in a HashMap. A single bucket can contain multiple key-value pairs if multiple keys are mapped to the same bucket due to a hash collision. In a HashMap, each bucket is internally represented as a linked list. Starting from Java 8, when the number of entries in a bucket exceeds a threshold, the linked list is converted into a Red-Black Tree to improve performance.

Before understanding the internal working of HashMap, you should be familiar with the following important concepts:

• Two unequal objects can return the same hashCode().

• If two objects are equal according to the equals() method, they must return the same hashCode().

HashMap primarily uses the following two methods to store and retrieve data:

1. put() – Stores a key-value pair in the HashMap.

2. get() – Retrieves the value associated with a given key.

1) How put(Key key, Value v) method works internally?

Let's look at the implementation of the put() method:

public V put(K key, V value) {
      if (key == null)
         Nreturn 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;
 }

Let's understand the above code step by step.

1. The key is first checked for null. If the key is null, the entry is stored in bucket index 0 because the hash code for a null key is always treated as 0.

2. If the key is not null, the key's hashCode() method is called to generate the hash code. This hash code is used to determine the bucket index where the entry should be stored. Since a poorly implemented hashCode() method may not distribute keys uniformly, HashMap applies an additional hash function to spread the hash values more evenly across the buckets, reducing the chances of collisions.

3. The processed hash value is then used to calculate the bucket index in the internal table array. In older JDK versions, this was done using the indexFor(hash, table.length) method.

   The indexFor() method calculates the bucket index based on the hash value and the length of the table array. Internally, it performs a bitwise AND (&) operation to determine the appropriate bucket index, as shown below:

 static int indexFor(int h, int length) {
    return h & (length-1);
 }

 

4. If two key objects produce the same hash code (a situation known as a hash collision), they are stored in the same bucket as a linked list. Therefore, HashMap iterates through the linked list to check whether the key already exists before inserting a new entry.

  2) How get(Key key) method works internally?

        
        The following steps are performed when you call the get() method with a key to retrieve the corresponding value from a hash-based collection such as HashMap.

Let's look at the code:

public V get(Object key) {

        if (key == null)
           return getForNullKey();

        int hash = hash(key.hashCode());
        for (Entry<k , V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
               Object k;
               if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                   return e.value;
         }
         return null;
 }

1. The key is first checked for null. If the key is null, HashMap returns the value associated with the null key, which is stored in bucket index 0.

2. If the key is not null, the key's hashCode() method is called to compute its hash code.

3. The hash code is then used to calculate the bucket index in the internal table array (using the hash and the table size) to locate the appropriate bucket.

4. After locating the bucket, HashMap traverses the linked list (or Red-Black Tree in Java 8 and later) and compares the given key with each stored key using the equals() method. If a matching key is found, the corresponding value is returned; otherwise, null is returned.

What happens if two keys has same hashCode?

           If multiple keys produce the same hashCode(), a hash collision occurs during the put() operation. This means that multiple entries are stored in the same bucket. Each entry maintains a reference to the next entry, forming a linked list. (In Java 8 and later, if the number of entries in a bucket exceeds a certain threshold, the linked list is converted into a Red-Black Tree.)

When retrieving a value in this situation, HashMap performs the following steps:

1. It calls the hashCode() method of the key to determine the bucket index.

2. It traverses the linked list (or Red-Black Tree) in that bucket and compares the search key with each stored key using the equals() method.

3. When equals() returns true, HashMap returns the corresponding value associated with that key.

This is why it is important to correctly override both the hashCode() and equals() methods when using custom objects as keys in a HashMap.

       

Key Notes:--

1. The data structure used to store entries in a HashMap is an array named table, whose elements are of type Node (called Entry in Java 7 and earlier).

2. Each index in the array is called a bucket because it can hold the first node of a linked list (or a Red-Black Tree in Java 8 and later when the bucket becomes heavily populated).

3. The key object's hashCode() method is used to compute the bucket index where the key-value pair should be stored.

4. The key object's equals() method is used to ensure the uniqueness of keys in the HashMap and to identify the correct entry during retrieval.

5. The value object's hashCode() and equals() methods are not used by the HashMap's put() and get() operations. Only the key's hashCode() and equals() methods are used.

6. The hash code for a null key is always treated as 0. Therefore, the entry with a null key is always stored in bucket index 0.

Related Posts:-- 
1) Internal Implementation of TreeMap in Java  
2) How to iterate the TreeMap in reverse order in Java  
3) Java Program to Count Occurrence of Word in a Sentence  
4) Internal implementation of ArrayList in Java  
5) String Interview Questions and Answers
6) Exception Handling Interview questions and answers