Understanding the internal implementation of HashMap is essential for every Java developer, especially when building high-performance backend applications and microservices.
We use HashMap almost everywhere in Java applications.
Whether we are caching API responses, storing configuration properties, processing transactions, maintaining session data, or building in-memory lookup structures, HashMap is one of the most frequently used data structures.
But have you ever wondered:
- How does HashMap store key-value pairs internally?
- How does it identify the bucket for a particular key?
- What happens when two keys generate the same hash?
- How does HashMap handle collisions?
- Why does HashMap resize automatically?
- Why does Java 8 introduce Red-Black Trees inside HashMap?
- What makes HashMap operations approximately O(1)?
Let's understand the internal implementation step by step, using Java 21 examples.
1. What Is HashMap?
HashMap is a part of the Java Collections Framework and implements the Map interface.
It stores data in key-value pairs.
Map<Integer, String> employees = new HashMap<>(); employees.put(101, "John"); employees.put(102, "David"); employees.put(103, "Michael"); System.out.println(employees.get(102)); Output:
David Unlike a List, HashMap does not maintain insertion order.
Important characteristics:
- Stores key-value pairs.
- Allows one null key.
- Allows multiple null values.
- Does not guarantee iteration order.
- Is not thread-safe.
- Provides approximately O(1) average-time performance for basic operations.
But internally, how does it achieve this performance?
Let's explore.
2. Internal Data Structure of HashMap
Internally, HashMap uses an array of nodes.
Each node stores:
- Hash
- Key
- Value
- Reference to the next node
The simplified internal structure looks like this:
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; } The important field here is:
Node<K,V>[] table; This is the internal bucket array.
Each array position represents a bucket, and each bucket can contain one or more entries.
3. How HashMap Calculates the Hash
When we insert an entry using put(), HashMap first calculates the hash of the key.
Simplified Java 8+ implementation:
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } Let's understand this expression:
h ^ (h >>> 16) Here:
-
hrepresents the original hashCode. -
>>>performs an unsigned right shift. -
^represents the bitwise XOR operation.
Why does HashMap perform this additional calculation?
Because Java hashCode is a 32-bit integer, but HashMap uses a power-of-two-sized array to determine the bucket index.
The index calculation uses the lower bits of the hash.
By XORing the upper 16 bits with the lower 16 bits, HashMap helps distribute information from the higher bits into the lower bits.
This improves hash distribution in many cases.
Important: Hash spreading does not eliminate collisions. It helps reduce poor distribution.
4. How HashMap Calculates the Bucket Index
After calculating the hash, HashMap determines where the entry should be stored.
The bucket index is calculated using:
index = (n - 1) & hash; Where:
-
nis the capacity of the internal array. -
hashis the spread hash value. -
&is the bitwise AND operator.
Why not use the modulo operator?
index = hash % n; HashMap uses bitwise AND because its capacity is always a power of two.
For example:
Capacity = 16 n - 1 = 15 15 in binary = 00001111 The operation:
index = (n - 1) & hash; is efficient and selects the bucket using the lower bits.
Example:
Capacity = 16 Hash = 35 Index = (16 - 1) & 35 Index = 15 & 35 Index = 3 Therefore, the entry is stored in bucket index 3.
5. What Happens When Two Keys Have the Same Hash?
This is called a hash collision.
Consider:
Map<String, Integer> map = new HashMap<>(); map.put("Aa", 100); map.put("BB", 200); Interestingly:
System.out.println("Aa".hashCode()); System.out.println("BB".hashCode()); Both produce the same hashCode:
2112 2112 Both entries are directed to the same bucket.
Does HashMap overwrite the existing value?
No.
HashMap handles collisions by storing multiple entries in the same bucket.
In Java 8 and later, the bucket initially uses a linked list.
Bucket 3 Node("Aa", 100) | v Node("BB", 200) | v null When retrieving a value, HashMap:
- Calculates the hash of the key.
- Identifies the bucket.
- Compares the hash.
- Checks key equality using reference equality or
equals(). - Returns the matching value.
This is why implementing equals() and hashCode() correctly is extremely important.
6. How HashMap Handles Collisions: Linked List to Red-Black Tree
This is one of the most important improvements introduced in Java 8.
Before Java 8, HashMap used linked lists to handle collisions.
In a heavily populated bucket, searching could degrade to O(n).
Java 8 introduced a mechanism called Treeification.
When a bucket contains too many entries, HashMap can convert its linked list into a Red-Black Tree.
Important implementation constants:
static final int TREEIFY_THRESHOLD = 8; static final int UNTREEIFY_THRESHOLD = 6; static final int MIN_TREEIFY_CAPACITY = 64; Let's understand them.
TREEIFY_THRESHOLD = 8
When a bucket reaches the treeification threshold, HashMap may convert the linked list into a Red-Black Tree.
MIN_TREEIFY_CAPACITY = 64
If the overall HashMap capacity is below 64, HashMap prefers resizing the table instead of treeifying the bucket.
UNTREEIFY_THRESHOLD = 6
During resizing, a tree bin can convert back into a linked list when its population becomes sufficiently small.
Why use a Red-Black Tree?
Because searching a balanced tree takes approximately O(log n), compared with O(n) for a linked list.
The actual implementation has additional details, including collision distribution and tree balancing.
7. How HashMap Resizing Works
HashMap does not allocate an unlimited array.
It grows automatically when the number of entries crosses a threshold.
Two important concepts:
Initial Capacity
Default initial capacity:
16 Load Factor
Default load factor:
0.75 The resize threshold is calculated as:
threshold = capacity * loadFactor; For example:
Initial Capacity = 16 Load Factor = 0.75 Threshold = 16 * 0.75 Threshold = 12 When the number of mappings exceeds the threshold, HashMap resizes its internal array.
The new capacity is generally doubled:
16 → 32 → 64 → 128 → 256 Why does HashMap resize?
As the number of entries increases, collisions may become more frequent.
Increasing capacity helps distribute entries across more buckets.
What happens during resizing?
During resizing:
- A new, larger bucket array is allocated.
- Existing entries are redistributed into the new array.
- Entries are placed into their appropriate new buckets.
- The new array becomes the internal table.
Java 8 introduced an optimization for redistribution.
Because capacity doubles, entries from an existing bucket either:
- Remain at the same index.
- Move to the index obtained by adding the old capacity.
This avoids recalculating the complete hash for every entry.
8. How put() Works Internally
Let's understand the simplified flow of the put() operation.
Map<Integer, String> employees = new HashMap<>(); employees.put(101, "John"); Internally, the process is approximately:
put(key, value) | v Calculate hash | v Calculate bucket index | v Is bucket empty? / \ Yes No | | Insert Check existing nodes | | | Same key? | / \ | Yes No | | | | Replace Continue | value searching | | | Add new node | | +---------------+ | v Check resize threshold | v Return This is a simplified conceptual flow. The actual implementation also handles tree bins, null keys, and other special cases.
9. How get() Works Internally
Retrieving a value follows a similar process.
String employee = employees.get(101); HashMap:
- Calculates the key's hash.
- Determines the bucket index.
- Checks the first node.
- Compares hash and key equality.
- Traverses the linked list or searches the tree if necessary.
- Returns the matching value.
If the key does not exist, it returns null.
This explains why HashMap provides approximately O(1) average-time lookup.
10. Why Are equals() and hashCode() Important?
One of the most common mistakes developers make is overriding equals() without overriding hashCode().
Consider:
class Employee { private int id; Employee(int id) { this.id = id; } @Override public boolean equals(Object obj) { if (this == obj) { return true; } if (!(obj instanceof Employee)) { return false; } Employee other = (Employee) obj; return this.id == other.id; } } Now consider:
Map<Employee, String> employees = new HashMap<>(); employees.put(new Employee(101), "John"); System.out.println( employees.get(new Employee(101)) ); Without a matching hashCode() implementation, the lookup may fail.
Why?
Because two logically equal objects may produce different identity-based hash codes.
The contract is:
- If two objects are equal according to
equals(), they must have the same hashCode. - Objects with the same hashCode are not necessarily equal.
Correct implementation:
@Override public int hashCode() { return Integer.hashCode(id); } Real-world lesson: Always implement equals() and hashCode() together when defining custom key objects.
Also, avoid modifying fields that participate in equals() and hashCode() while an object is being used as a HashMap key. Doing so can make the entry difficult to retrieve.
11. Time Complexity of HashMap
Let's look at the typical performance characteristics.
| Operation | Average Case | Worst Case |
|---|---|---|
| put() | O(1) | O(n) |
| get() | O(1) | O(n) |
| remove() | O(1) | O(n) |
| containsKey() | O(1) | O(n) |
With tree bins, heavily collided buckets can provide O(log n) lookup behavior under normal balanced-tree conditions.
However, resizing can require O(n) work.
These complexities describe the general implementation behavior, not a guarantee that every individual operation always takes constant time.
12. HashMap vs ConcurrentHashMap
A common question in backend development is:
Should we use HashMap or ConcurrentHashMap?
| Feature | HashMap | ConcurrentHashMap |
|---|---|---|
| Thread-safe | No | Yes |
| Null key | One allowed | Not allowed |
| Null values | Allowed | Not allowed |
| Concurrent access | Requires external synchronization | Supports concurrent operations |
| Performance | Good for single-threaded access | Designed for concurrent access |
Example:
Map<String, Integer> map = new ConcurrentHashMap<>(); In a multithreaded application, using HashMap without proper synchronization can lead to incorrect behavior when multiple threads modify it concurrently.
ConcurrentHashMap provides thread-safe operations and is generally a better choice for shared mutable maps.
Remember: Thread-safe individual operations do not automatically make multi-step business workflows atomic.
13. Real-World Usage in Enterprise Applications
HashMap is not just an interview topic. It plays an important role in enterprise backend development.
Consider a banking application.
We may use HashMap for:
1. Transaction Processing
Map<String, Transaction> transactionCache = new HashMap<>(); Useful for temporary in-memory lookups within a controlled execution context.
2. Configuration Management
Map<String, String> applicationConfig = new HashMap<>(); 3. Grouping Transactions
Map<String, List<Transaction>> transactionsByAccount = new HashMap<>(); 4. API Response Transformation
Map<String, Object> response = new HashMap<>(); response.put("status", "SUCCESS"); response.put("transactionId", "TXN1001"); response.put("amount", 5000); In production applications, choose the appropriate concurrency model and cache technology based on data size, lifecycle, consistency, and deployment architecture.
For distributed caching across multiple microservice instances, an in-memory HashMap is not a replacement for Redis or another distributed cache.
14. Best Practices for Using HashMap
A few practical recommendations:
- Initialize HashMap with a suitable capacity when the approximate number of entries is known.
- Use immutable objects as keys wherever possible.
- Always implement equals() and hashCode() consistently for custom keys.
- Avoid using HashMap for shared mutable state without synchronization.
- Use ConcurrentHashMap for appropriate concurrent access scenarios.
- Do not depend on HashMap iteration order.
- Use LinkedHashMap when insertion order matters.
- Use TreeMap when sorted key ordering is required.
- Avoid unnecessarily large initial capacities because they increase memory consumption.
- Consider distributed caching solutions for cross-instance application caching.
15. Key Takeaways
Let's summarize what happens internally:
- HashMap stores entries in an internal array of buckets.
- It uses hashCode() and hash spreading to calculate the hash.
- Bucket indexes are calculated using
(n - 1) & hash. - Collisions are handled using linked lists.
- Java 8 introduced Red-Black Tree bins for heavily populated buckets.
- Default initial capacity is 16.
- Default load factor is 0.75.
- Resizing generally doubles the capacity.
- Correct equals() and hashCode() implementations are essential.
- HashMap is not thread-safe.
Understanding these internals helps us write better Java applications, troubleshoot performance issues, and make informed architectural decisions.
A good Java developer knows how to use HashMap. An experienced Java engineer understands what happens behind the scenes.
Interview Questions to Test Your Understanding
- Why is HashMap capacity always a power of two?
- Why does HashMap use
h ^ (h >>> 16)? - What happens when two different keys have the same hashCode?
- What is the difference between collision handling in Java 7 and Java 8?
- Why does HashMap convert a linked list into a Red-Black Tree?
- What are TREEIFY_THRESHOLD and MIN_TREEIFY_CAPACITY?
- What happens when the load factor threshold is exceeded?
- Can two different objects have the same hashCode?
- Why is HashMap not thread-safe?
- What happens if we modify a key after inserting it into a HashMap?
If you can explain these questions with internal implementation details and practical examples, you have a strong understanding of HashMap.
What's Next?
In the next article, we'll explore another important Java Collections topic:
HashMap vs LinkedHashMap vs TreeMap: Internal Differences, Performance and Real-World Use Cases.
Follow me for more practical Java, Spring Boot, Microservices, Kafka, System Design and Enterprise Architecture insights.
Ram The Architect (RTA)




![Physical AI Engineering — Ch.13: Computing Platforms for Physical AI [EN]](https://media2.dev.to/dynamic/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.us-east-2.amazonaws.com%2Fuploads%2Farticles%2Fg3ou3b2eumf1epqj4bk4.png)

![Physical AI Engineering — Ch.04: Localization Mapping and World Understanding [EN]](https://media2.dev.to/dynamic/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.us-east-2.amazonaws.com%2Fuploads%2Farticles%2Fuscy0mautxl2mb4834vd.png)