Home / java

HashMap Internal Working in Java Explained with Examples | hashCode(), equals(), Buckets & Collisions

HashMap Internal Working in Java

HashMap is one of the most commonly used classes in the Java Collections Framework. It stores data in key-value pairs and provides very fast insertion, retrieval, and deletion of data. Because of its efficiency, HashMap is widely used in enterprise applications, REST APIs, caching systems, configuration management, and interview coding problems.

Many Java developers know how to use a HashMap, but understanding how HashMap works internally is one of the most frequently asked Java interview questions. In this guide, you'll learn everything from hashing and buckets to collision handling, resizing, and performance optimization with simple explanations and practical examples.

What is HashMap?

HashMap is a class available in the java.util package that implements the Map interface.

It stores data in the form of a unique key and its corresponding value. Every key maps to exactly one value, making data lookup extremely fast.

HashMap<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

Features of HashMap

Stores data as key-value pairs.
Allows one null key and multiple null values.
Keys must be unique.
Does not maintain insertion order.
Not synchronized (not thread-safe).
Provides average O(1) lookup performance.

Real World Example

Imagine a company's employee database. Instead of searching every employee one by one, the employee ID can be used as a unique key.

Employee ID (Key)	Employee Name (Value)
101	John
102	David
103	Alex

When you search for Employee ID 102, HashMap directly jumps to the correct location instead of searching every record.

How Does HashMap Work Internally?

Internally, HashMap stores data inside an array called buckets. Every key is converted into an integer using its hashCode() method.

The generated hash value determines which bucket will store the key-value pair.

The process looks like this:

Key

 │

 ▼

hashCode()

 │

 ▼

Hash Value

 │

 ▼

Bucket Index

 │

 ▼

Store Key-Value Pair

Whenever you insert or retrieve data, HashMap performs the same calculation to find the correct bucket.

Step-by-Step Internal Working

Step 1: Create a HashMap

HashMap<Integer, String> map = new HashMap<>();

Initially, HashMap creates an internal bucket array. The default capacity is 16 buckets.

Bucket Array

[0]
[1]
[2]
[3]
...
[15]

Step 2: Insert a Key-Value Pair

map.put(101, "John");

HashMap first calculates the hash code of the key.

hashCode(101)

↓

101

It then calculates the bucket index using an internal formula.

Bucket Index = hash & (capacity - 1)

Suppose the calculated bucket index is 5. The data will be stored inside Bucket 5.

[0]

[1]

[2]

[3]

[4]

[5] → (101, John)

[6]

...

[15]

Step 3: Retrieve a Value

map.get(101);

HashMap again calculates the hash code of key 101, finds Bucket 5, and immediately returns the stored value.

This direct bucket lookup makes HashMap extremely fast.

Understanding hashCode()

Every Java object inherits the hashCode() method from the Object class.

The hash code is simply an integer representation of an object. HashMap uses this integer to determine where the object should be stored.

Integer key = 101;

System.out.println(key.hashCode());

Output

For custom objects, developers can override the hashCode() method to generate meaningful hash values.

Why hashCode() Alone Is Not Enough?

Different objects can sometimes produce the same hash code. This situation is called a Hash Collision.

For example:

Key A

↓

Hash = 5

Key B

↓

Hash = 5

Both keys point to the same bucket. HashMap must therefore use another mechanism to distinguish between them.

The Role of equals()

Whenever two keys generate the same hash code, HashMap calls the equals() method.

If equals() returns true, the existing value is updated.
If equals() returns false, both entries are stored separately.

This combination of hashCode() and equals() ensures data accuracy even when collisions occur.

Example

map.put(101, "John");

map.put(101, "David");

Since both keys are equal, the second value replaces the first one.

Output

{101=David}

Key Points So Far

HashMap stores data in key-value pairs.
Data is stored inside buckets.
hashCode() decides the bucket.
equals() verifies duplicate keys.
Average lookup time is O(1).
Collisions are handled automatically.

What is a Hash Collision?

A Hash Collision occurs when two different keys generate the same bucket index. Since multiple keys cannot occupy the exact same position in the bucket array, HashMap uses additional data structures to store them efficiently.

For example:

Key A  → hash = 5

Key B  → hash = 5

Key C  → hash = 5

All three keys point to Bucket 5. Instead of replacing existing data, HashMap stores each entry in the same bucket.

Collision Handling Before Java 8

Before Java 8, every bucket stored entries as a Linked List. Whenever a collision occurred, the new node was simply added to the list.

Bucket 5

↓

(101, John)
      ↓
(117, David)
      ↓
(133, Alex)

When retrieving a value, HashMap traversed the linked list one node at a time until the required key was found.

If many collisions occurred, searching became slower because the linked list continued to grow.

Collision Handling in Java 8 and Above

Starting from Java 8, HashMap introduced an important optimization.

If the number of nodes in a bucket becomes greater than 8, the linked list is converted into a Red-Black Tree.

This significantly improves search performance for heavily populated buckets.

Entries in Bucket	Data Structure Used
Less than 8	Linked List
8 or more	Red-Black Tree

Internal Bucket Structure

A HashMap internally looks similar to the following structure:

Bucket Array

[0]

[1]

[2] → (105, Mike)

[3]

[4]

[5] → (101, John)
        ↓
      (117, David)
        ↓
      (133, Alex)

[6]

...

[15]

Only Bucket 5 contains multiple entries because all three keys generated the same bucket index.

How HashMap Retrieves Data

Suppose we execute the following code:

map.get(117);

HashMap performs these steps:

Calculate the hash code of key 117.
Calculate the bucket index.
Go directly to that bucket.
Compare keys using equals().
Return the matching value.

Instead of searching every element, HashMap jumps directly to the correct bucket, making retrieval extremely fast.

Load Factor

The Load Factor determines when HashMap should increase its capacity.

The default load factor is:

0.75

This means once the HashMap becomes 75% full, it automatically resizes itself.

For example:

Capacity	Resize Happens At
16	12 entries
32	24 entries
64	48 entries

Initial Capacity

By default, a new HashMap starts with:

Initial Capacity: 16
Load Factor: 0.75

You can customize both values if you already know approximately how many entries will be stored.

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

What is Resizing?

When the number of entries exceeds the load factor threshold, HashMap creates a larger bucket array.

The capacity is generally doubled.

16 Buckets

↓

32 Buckets

↓

64 Buckets

↓

128 Buckets

This process is called Resizing.

What is Rehashing?

After resizing, every existing key is inserted again into the new bucket array.

Because the bucket count has changed, the bucket index for many keys also changes.

Old Bucket

↓

Calculate New Hash

↓

Find New Bucket

↓

Move Entry

This process is known as Rehashing.

Time Complexity of HashMap

Operation	Average Case	Worst Case
Insert (put)	O(1)	O(n)
Search (get)	O(1)	O(n)
Delete (remove)	O(1)	O(n)

In normal situations, HashMap provides constant-time performance. The worst case occurs only when a large number of keys collide into the same bucket.

When Should You Use HashMap?

HashMap is an excellent choice when:

You need fast data retrieval.
Insertion order is not important.
Keys are unique.
You frequently search data using a key.
Performance is a priority.

Common Applications of HashMap

User session management
Database result caching
Configuration settings
REST API response caching
Product catalog lookup
Employee records
Student management systems
Shopping cart applications

Using Custom Objects as Keys

When using custom Java objects as keys in a HashMap, it is important to override both the hashCode() and equals() methods. Otherwise, HashMap may treat logically identical objects as different keys, resulting in duplicate entries or failed lookups.

Example

class Employee {

    private int id;
    private String name;

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

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

    @Override
    public boolean equals(Object obj) {

        if (this == obj)
            return true;

        if (!(obj instanceof Employee))
            return false;

        Employee emp = (Employee) obj;

        return this.id == emp.id;
    }
}

With proper implementations of hashCode() and equals(), HashMap can correctly identify duplicate keys and retrieve values efficiently.

HashMap vs Hashtable vs ConcurrentHashMap

Feature	HashMap	Hashtable	ConcurrentHashMap
Thread Safe	No	Yes	Yes
Performance	Fast	Slower	Very Fast
Allows Null Key	Yes	No	No
Allows Null Values	Yes	No	No
Recommended For	Single-threaded applications	Legacy applications	Multi-threaded applications

Best Practices for Using HashMap

Use immutable objects such as String or Integer as keys whenever possible.
Always override hashCode() and equals() when using custom objects.
Choose an appropriate initial capacity for large datasets to reduce resizing operations.
Avoid modifying key objects after they have been inserted into the map.
Use ConcurrentHashMap instead of HashMap in multi-threaded environments.
Keep hash functions well distributed to minimize collisions.

Common Mistakes

1. Forgetting to Override hashCode() and equals()

This is one of the most common mistakes made by beginners. Without overriding these methods, HashMap may fail to locate existing keys.

2. Using Mutable Objects as Keys

If a key object changes after being inserted into a HashMap, its hash code may also change, making it impossible to retrieve the value.

3. Assuming HashMap Maintains Order

HashMap does not guarantee insertion order. If ordering is required, consider using LinkedHashMap or TreeMap.

Frequently Asked Interview Questions

What is HashMap in Java?
How does HashMap work internally?
What is a bucket in HashMap?
What is the default capacity of HashMap?
What is the default load factor?
What happens when two keys generate the same hash code?
What is a hash collision?
How are collisions handled in Java 8?
Why are both hashCode() and equals() required?
What is rehashing?
What is resizing?
Why is HashMap so fast?
Can HashMap have duplicate keys?
Can HashMap store null values?
Difference between HashMap and Hashtable?
Difference between HashMap and ConcurrentHashMap?
Why is the average time complexity O(1)?
What happens if hashCode() always returns the same value?

Frequently Asked Questions (FAQ)

Does HashMap allow duplicate keys?

No. Keys must always be unique. If an existing key is inserted again, its value is updated.

Can HashMap contain null keys?

Yes. HashMap allows one null key and multiple null values.

Is HashMap synchronized?

No. HashMap is not thread-safe. For concurrent applications, use ConcurrentHashMap.

Why is HashMap faster than a List?

HashMap directly calculates the bucket location using the key's hash code, whereas a List searches elements one by one.

When should I use TreeMap instead of HashMap?

Use TreeMap when you need data to remain sorted based on the keys.

Key Takeaways

HashMap stores data as key-value pairs.
Data is stored internally in buckets.
hashCode() determines the bucket location.
equals() verifies whether keys are identical.
Hash collisions are handled using Linked Lists or Red-Black Trees.
Java 8 converts long collision chains into Red-Black Trees for better performance.
Default initial capacity is 16.
Default load factor is 0.75.
Average lookup, insertion, and deletion operations take O(1) time.

Conclusion

HashMap is one of the most efficient and widely used data structures in Java. Its ability to provide near constant-time insertion, retrieval, and deletion makes it the preferred choice for storing key-value pairs in most applications.

Understanding the internal working of HashMap—including buckets, hashing, hashCode(), equals(), collision handling, resizing, rehashing, and load factor—not only helps you write optimized Java applications but also prepares you for technical interviews at top companies.

If you're preparing for Java interviews, mastering HashMap internals is essential because it is one of the most frequently asked topics for both freshers and experienced developers.