How HashMap Works Internally in Java with Examples

HashMap is one of the most frequently used classes in Java and is a favourite topic in Java interviews. Almost every Java developer uses HashMap, but very few understand how it works internally. In this article, we will explore the internal working of HashMap, including buckets, hashCode(), collisions, linked lists, treeification, and performance optimizations.

What is HashMap?

HashMap is a part of the Java Collections Framework and is used to store data in key-value pairs. It allows one null key and multiple null values. HashMap does not maintain insertion order.

Map<Integer, String> employeeMap = new HashMap<>();

employeeMap.put(1, "John");
employeeMap.put(2, "David");
employeeMap.put(3, "Alex");

Important Characteristics of HashMap

• Stores data as key-value pairs
• Allows one null key
• Allows multiple null values
• Not synchronized
• Provides nearly O(1) lookup performance
• Uses hashing mechanism internally
  
  
  

Internal Structure of HashMap

Internally, HashMap stores data inside an array called buckets. Each bucket can contain multiple entries.

Bucket[0]
Bucket[1]
Bucket[2]
Bucket[3]
...
Bucket[n]

Whenever a key-value pair is inserted, HashMap calculates which bucket should contain the entry.

How put() Works Internally

When we add an element into HashMap:

map.put(101, "Java");

The following steps occur internally:

1. HashMap calls hashCode() on the key.
2. A hash value is generated.
3. The bucket index is calculated.
4. The key-value pair is stored in the bucket.
5. If the bucket already contains data, collision handling occurs.

Example

Integer key = 101;

int hash = key.hashCode();

The generated hash helps HashMap identify the correct bucket location.

How get() Works Internally

Retrieving a value from HashMap is fast because Java calculates the bucket directly.

String course = map.get(101);

HashMap performs these operations:

1. Calculate hashCode() of the key.
2. Identify bucket index.
3. Search inside the bucket.
4. Compare keys using equals().
5. Return matching value.

What is Collision in HashMap?

A collision occurs when two different keys generate the same bucket index.

map.put(1, "Java");
map.put(17, "Spring");

Both keys may point to the same bucket. In such cases HashMap stores multiple entries inside that bucket.

Collision Handling Before Java 8

Before Java 8, collisions were handled using Linked Lists.

Bucket 15

Key1 -> Key2 -> Key3 -> Key4

Searching becomes slower as the linked list grows.

Collision Handling in Java 8 and Later

Java 8 introduced Treeification. When the number of entries in a bucket exceeds a threshold, the linked list converts into a Red-Black Tree.

Bucket 15

         7
       /   \
      3     12
     / \   / \
    1  5 10 15

This improves lookup performance significantly.

Performance Comparison

Structure	Search Complexity
Linked List	O(n)
Red Black Tree	O(log n)

Why equals() and hashCode() Are Important

HashMap relies heavily on both hashCode() and equals().

hashCode() identifies the bucket and equals() identifies the exact object within that bucket.

Example

public class Employee {

    private int id;

    public Employee(int id) {
        this.id = id;
    }

    @Override
    public int hashCode() {
        return id;
    }

    @Override
    public boolean equals(Object obj) {

        if(this == obj)
            return true;

        if(obj == null || getClass() != obj.getClass())
            return false;

        Employee emp = (Employee)obj;

        return id == emp.id;
    }
}

Overriding both methods correctly ensures HashMap behaves properly.

Initial Capacity and Load Factor

HashMap uses two important parameters:

• Initial Capacity = 16
• Load Factor = 0.75

When capacity reaches 75%, HashMap automatically resizes.

Map<Integer,String> map =
new HashMap<>(32,0.75f);

Time Complexity of HashMap Operations

Operation	Complexity
put()	O(1)
get()	O(1)
remove()	O(1)
Worst Case	O(log n)

Real-World Example

Map<Integer,String> employees =
new HashMap<>();

employees.put(101,"John");
employees.put(102,"David");
employees.put(103,"Alex");

System.out.println(employees.get(102));

Output

David

Common HashMap Interview Questions

1. How does HashMap work internally?
2. What causes a collision?
3. What is Treeification?
4. Difference between HashMap and Hashtable?
5. Why override equals() and hashCode()?
6. What is Load Factor?
7. Can HashMap have null keys?
8. What is the default capacity of HashMap?

Conclusion

HashMap is one of the most important data structures in Java. It provides near constant-time performance using hashing techniques. Understanding buckets, hashCode(), equals(), collisions, linked lists, and red-black trees will help developers write efficient applications and perform well in Java interviews.

Related Articles

• Difference Between HashMap and ConcurrentHashMap in Java

Keywords

HashMap Internal Working, How HashMap Works in Java, HashMap Interview Questions, Java Collections Framework, HashMap Collision Handling, HashMap Java 8, HashMap Buckets, hashCode and equals in Java, Java HashMap Examples, HashMap Performance, Treeification in HashMap, Java Collection Interview Questions, HashMap Time Complexity, Java Core Concepts, Java Programming Tutorial