HashMap Internals in Java

22 min readApr 3, 2026

Recently, I interviewed with a few product-based companies and was asked about the internal workings of a HashMap. It’s one of those questions you see everywhere and something we all use daily, so it’s easy to assume a surface-level explanation is enough. It isn’t. That interview made it clear that understanding HashMap internals requires more than vague familiarity. Over the past week, I went back to basics by reading official documentation, digging into source code, exploring blogs, and cross-checking my understanding with tools like Claude . This article is a distilled summary of that effort, aimed at anyone who wants to explain HashMap internals with clarity and confidence, not just at a high level but with real depth.
A comprehensive technical deep dive for HashMaps from bucket arrays to Red-Black trees, hash spreading to rehashing. Everything you need to answer any interview question with confidence.

Why HashMap ? one of the most favourite Question

Walk into any backend, systems, or data engineering interview at a serious company and there’s a high chance the conversation will land on HashMap. Not because it’s complex, but because it’s fundamental. It’s one of the most heavily used data structures in Java, powering caches, frequency maps, adjacency lists, configuration storage, and more. Interviewers focus on it because most engineers rely on it daily without fully understanding what happens beneath a simple put() call.

HashMap internals are one of those areas where low-level understanding directly improves production intuition. Knowing how load factor works helps you size data structures correctly. Understanding treeification explains why performance can shift from O(1) to O(log n). Being clear on the contract between equals() and hashCode() saves you from subtle, hard-to-debug issues.

This article aims to remove that ambiguity. We’ll start from the conceptual model and work our way down to the bit-level operations in the JDK implementation.

A. What is HashMap ??

HashMap<K, V> is Java’s general-purpose hash table implementation of the Map<K, V> interface, part of java.util. It stores key-value pairs, where each key is unique within the map.

A simple way to think about it: imagine a set of numbered mailboxes. A key is passed through a hash function to determine which mailbox it belongs to, and the value is stored there. For lookups, the same computation takes you directly to the right spot, without scanning everything.

Key characteristics

O(1) average for put, get, remove =>The hash function maps keys to buckets, enabling constant-time operations in typical cases.
Unordered => Iteration order is not guaranteed and can change, especially after resizing.
Allows one null key =>null is treated as a special case and mapped to bucket 0.
Allows null values => Values can be null without restriction.
Not thread-safe => Concurrent modifications without external synchronization can lead to inconsistent state.
Fail-fast iterators => Iteration throws ConcurrentModificationException if the structure is modified during traversal.
No ordering guarantees =>If ordering matters, use LinkedHashMap (insertion order) or TreeMap (sorted order).

Under the hood

HashMap is not synchronized by design. For basic thread safety, you can wrap it using Collections.synchronizedMap(). For true concurrent access with better scalability, ConcurrentHashMap is the appropriate choice.

B. Internal Data Structure

A HashMap is backed by an array of buckets, implemented as an array of Node<K, V> (called Entry<K, V> prior to Java 8). Each slot in this array can be empty, hold a single node, form a linked list due to collisions, or, starting from Java 8, be converted into a Red-Black tree when certain thresholds are met.

The `Node` class

Each key-value pair is stored inside a Node:

static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;   // cached hash of the key
    final K key;
    V value;
    Node<K, V> next;  // next node in the bucket chain
}

It’s a minimal structure with four fields. The hash is cached to avoid recomputing it during operations like resizing, where every element needs to be reprocessed. The next pointer links nodes within the same bucket when collisions occur.

Structural layout

At the top level, the map maintains an array called table:

table[] (Node array, default capacity = 16)

index:  [0]   [1]   [2]   [3]   [4]   ...  [15]
         |     |     |     |     |
        null  Node  null  Node  null
               |           |
              Node        Node   ← collision: linked list
               |
              null
Each Node: { hash | key | value | next → }

Each index represents a bucket. When multiple keys map to the same index, they are chained together, initially as a linked list.

One important detail: the array size is always a power of two. This isn’t arbitrary; it’s a deliberate design choice that enables efficient index calculation using bit operations, which we’ll explore next.

C. How Hashing Works Internally

Step 1: `hashCode()`

Every Java object inherits a hashCode() method from Object. For a given key k, HashMap starts by calling k.hashCode() to produce an integer hash.

The implementation depends on the type. For example, String computes a polynomial hash based on its characters, while Integer.hashCode() simply returns the integer value itself. This raw hash is the foundation, but it’s not used directly.

Step 2: Hash spreading

Raw hashCode() values often have weak distribution in their lower bits. This matters because bucket selection depends on those lower bits, especially when the table size is small. Poor distribution here leads to unnecessary collisions.

To address this, Java 8 introduces a lightweight mixing step:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

The unsigned right shift (>>>) moves the higher 16 bits down, and the XOR folds them into the lower 16 bits. This effectively spreads entropy from the high bits into the low bits, improving distribution without adding real overhead.

The intuition is simple: if most of the randomness sits in the upper half of the integer, this step ensures the lower half benefits from it, which directly impacts bucket selection.

Step 3: Index calculation

Once the hash is mixed, the bucket index is computed as:

index = (n - 1) & hash

Here, n is the table length, always a power of two. Instead of using a modulo operation, HashMap uses a bitwise AND. For example, if n = 16, then n - 1 = 15 (0b00001111). ANDing any number with this mask extracts just the last 4 bits.

This is equivalent to hash % 16, but significantly faster since it avoids division. This design is the reason the table size must always be a power of two.

A quick example:

hash("Alice") = 0x7B92A341
spread hash   = 0x7B92A341 ^ 0x00007B92 = 0x7B92D8D3

n = 16
n - 1 = 15 = 0b00001111
index = 0x7B92D8D3 & 0x0000000F
      = 0b...1101_0011
        & 0b00001111
      = 0b00000011 = 3

This direct mapping from hash to index is what makes average-case operations constant time, as long as the hash distribution holds up.

D. put() Operation — Step by Step

The put(K key, V value) method is where most of the real work in a HashMap happens. Let’s walk through it step by step.

1. Compute the hash

The key is passed through the hash spreading function. For null, the hash is defined as 0.

2. Initialize the table

If the internal table is still null (which is the case for a new map), resize() is triggered to allocate the array with the default capacity of 16.

3. Calculate the bucket index

The index is computed using:

i = (n - 1) & hash

where n is the current table length.

4. Check if the bucket is empty

If table[i] is null, a new node is created and placed there. This is the simplest and fastest path.

5. Handle duplicate keys

If the bucket is not empty, the first node is checked. If both the hash and key match:

existing.hash == hash &&
(existing.key == key || key.equals(existing.key))

it’s an update, not an insertion. The value is simply overwritten.

6. Handle tree nodes

If the bucket has already been converted into a Red-Black tree, insertion is delegated to putTreeVal(), which operates in O(log n) time.

7. Traverse the linked list

If the bucket is still a linked list:

Walk through each node
Check for a matching key (update if found)
If no match is found and the end is reached, append a new node

After insertion, if the chain length reaches 8 or more, treeifyBin() is triggered to convert the list into a Red-Black tree. However, this only happens if the table size is at least 64; otherwise, the map resizes instead.

8. Update size and check threshold

If a new node was added (not an update), increment size.
If size exceeds the threshold (capacity × loadFactor), trigger a resize.

Example


map.put("Alice", 42) — hash("Alice") spreads to, say, index 3. 
Bucket 3 is empty. A new Node{hash, "Alice", 42, null} is created at table[3].
size becomes 1. Threshold is 12 (16 × 0.75). No resize needed.

At a glance, put() looks simple. Under the hood, it carefully balances fast insertion, collision handling, and dynamic resizing to keep operations close to constant time.

E. get() Operation — Step by Step

The get(K key) path is straightforward on the surface, but carefully optimized under the hood.

1. Null check and hash

If the key is null, the lookup is done in bucket 0. Otherwise, the key is passed through the hash spreading function.

2. Table check

If the internal table is null or has zero length, there’s nothing to look up. Return null.

3. Compute index and fetch first node

The bucket index is calculated:

i = (n - 1) & hash

Fetch the first node at table[i]. If it’s null, the key doesn’t exist.

4. Check the first node

The first node is checked directly:

first.hash == hash &&
(first.key == key || key.equals(first.key))

If it matches, return the value immediately. The hash comparison acts as a fast filter, avoiding the more expensive equals() call in most cases.

5. Traverse chain or tree

If there are more nodes in the bucket:

If it’s a tree, delegate to getTreeNode() for O(log n) lookup
Otherwise, walk the linked list and apply the same hash + equals check at each node

The two-step comparison is intentional. Integer comparison is cheap, while equals() can be relatively expensive, especially for objects like strings. Filtering by hash first reduces unnecessary work and keeps lookups efficient even in collision-heavy buckets.

F. Collision Handling in Depth

A collision occurs when two different keys map to the same bucket index. This isn’t an edge case, it’s inevitable. Any hash table smaller than the space of possible hash values will collide. The real question is how those collisions are handled.

Phase 1: Separate chaining (linked list)

When a key maps to an already occupied bucket, it’s appended to a singly linked list at that index. Lookups walk this chain, comparing hash first, then key via equals().

With a good hash function and a controlled load factor, most buckets stay small, often just one element. But if the distribution is poor or adversarial, these chains can grow, degrading performance from O(1) to O(n).

Phase 2: Treeification (Java 8+)

To guard against long chains, Java 8 introduced treeification. When a bucket’s size reaches 8, the linked list is converted into a Red-Black tree.

This changes the worst-case complexity of lookups, inserts, and deletes from O(n) to O(log n). It’s a defensive optimization, especially useful under heavy collisions or poorly distributed hashes.

Why the table size matters

Treeification doesn’t happen unconditionally. If the table size is less than 64, HashMap prefers to resize instead of converting to a tree.

The reasoning is practical: if the table is small, it’s more effective to spread entries across more buckets than to pay the overhead of maintaining a tree in a single bucket.

Why the threshold is 8

This isn’t arbitrary. The JDK uses probability analysis based on a Poisson distribution, assuming a well-behaved hash function and default load factor (0.75).

Under these conditions, the probability of a bucket having 8 or more elements is extremely low, roughly 0.00000006. In normal scenarios, treeification should almost never trigger. If it does frequently, it’s usually a sign of a poor hashCode() implementation.

Untreeify threshold: 6

If elements are removed and the bucket size drops to 6 or below, the structure converts back into a linked list.

The gap between 8 (treeify) and 6 (untreeify) is intentional. It avoids repeated conversions when the bucket size fluctuates near the threshold.

Why a Red-Black tree

Red-Black trees offer predictable O(log n) performance with relatively low rebalancing cost. They don’t enforce strict height constraints like AVL trees, which keeps insertions and deletions cheaper.

This balance makes them a good fit for HashMap, where both reads and writes are frequent. The same reasoning applies to TreeMap, which also relies on Red-Black trees.

Conceptual view

Before (linked list, O(n)):
[5] → Node(A) → Node(B) → Node(C) → ... → Node(H) → null

After (Red-Black tree, O(log n)):
            [5]
             |
          TreeNode(D)
         /           \
    TreeNode(B)   TreeNode(F)
    /       \       /       \
 Node(A)  Node(C) Node(E) Node(G)
                               \
                              Node(H)

In practice, this transition is what keeps HashMap resilient. Even in worst-case scenarios, it avoids collapsing into linear performance.

G. Resizing / Rehashing

Load factor and threshold

The load factor (default 0.75) controls the balance between space and time. A higher value packs more elements into each bucket, saving memory but increasing collisions. A lower value spreads elements out, reducing collisions at the cost of extra space.

The resize threshold is:

threshold = capacity × loadFactor
          = 16 × 0.75 = 12

When size exceeds this threshold after a put, a resize is triggered.

How resizing works

Double the capacity
The new capacity is old capacity × 2, preserving the power-of-two property.
Allocate a new table
A new Node[] array is created.
Redistribute elements
Every existing node is visited and repositioned in the new table. This is the expensive step.
Recalculate threshold
threshold = new capacity × loadFactor.

Java 8’s rehashing optimization

When capacity doubles, the index calculation (n - 1) & hash effectively adds one more bit. This means each element has only two possible positions in the new table: it either stays where it is or moves by oldCapacity.

Java 8 takes advantage of this:

If (hash & oldCapacity) == 0, the node stays at the same index
Otherwise, it moves to oldIndex + oldCapacity

This avoids recomputing the full index and allows each bucket to be split into two chains in a single pass.

Example:

Old capacity: 16   (uses 4 bits)
New capacity: 32   (uses 5 bits)

hash = ...1_0011 → old index = 0011 = 3
(hash & 16) == 0   → stays at index 3
(hash & 16) != 0   → moves to index 3 + 16 = 19

Why resizing is expensive

Resizing is an O(n) operation since every element must be processed. If a map grows through multiple resizes, the cost compounds.

For example, inserting 1,000,000 entries with repeated resizes can lead to tens of millions of node visits purely due to rehashing. This is avoidable by initializing the map with a reasonable capacity:

new HashMap<>(expectedSize / 0.75 + 1)

H. Time Complexity Analysis

| Operation       | Average         | Worst (Java 7) | Worst (Java 8+) |
| --------------- | --------------- | -------------- | --------------- |
| `put()`         | O(1)            | O(n)           | O(log n)        |
| `get()`         | O(1)            | O(n)           | O(log n)        |
| `remove()`      | O(1)            | O(n)           | O(log n)        |
| `containsKey()` | O(1)            | O(n)           | O(log n)        |
| `resize()`      | O(n)            | O(n)           | O(n)            |
| Iteration       | O(capacity + n) | same           | same            |

One subtle point: iteration depends on capacity, not just size. The iterator scans every bucket, including empty ones. A map with 10 elements but capacity 10,000 will still traverse all 10,000 slots. Over-allocating hurts iteration performance.

Average vs amortized cost

The O(1) guarantee assumes a good hash distribution. More precisely, operations are amortized O(1). Individual calls can be expensive, such as during resize or tree operations, but over a sequence of operations, the average cost remains constant.

I. Important internal constants

Initial capacity — 16
DEFAULT_INITIAL_CAPACITY = 1 << 4
Always a power of two to support efficient index calculation.
Maximum capacity — ²³⁰
MAXIMUM_CAPACITY = 1 << 30
This is the upper bound on table size to avoid excessive memory allocation.
Load factor — 0.75
DEFAULT_LOAD_FACTOR
A practical balance between memory usage and collision rate.
Treeify threshold — 8
TREEIFY_THRESHOLD
When a bucket reaches this size, it converts from a linked list to a Red-Black tree.
Untreeify threshold — 6
UNTREEIFY_THRESHOLD
When a tree shrinks below this size, it converts back to a linked list.
Minimum capacity for treeification — 64
MIN_TREEIFY_CAPACITY
Treeification only happens if the table has reached this size; otherwise, resizing is preferred.

J. Differences Across Java Versions

Java 7 vs Java 8+

| Aspect                  | Java 7                             | Java 8+                                           |
| ----------------------- | ---------------------------------- | ------------------------------------------------- |
| Collision handling      | Linked list only                   | Linked list → Red-Black tree (threshold = 8)      |
| Node structure          | `Entry<K,V>`                       | `Node<K,V>` + `TreeNode<K,V>`                     |
| Hash function           | Multiple shifts and XORs           | Single spread: `h ^ (h >>> 16)`                   |
| Worst-case lookup       | O(n)                               | O(log n)                                          |
| Resize behavior         | Head insertion (can reverse order) | Preserves relative order (splits into two chains) |
| Concurrent resize issue | Possible infinite loop             | Fixed (still not thread-safe)                     |

Why Java 8 changed the design

The Java 7 approach relied entirely on linked lists for collision handling. This exposed a serious weakness. If an attacker could control input keys, they could force many keys into the same bucket, turning all operations into O(n). In real systems, this showed up in places like HTTP parameter parsing, where inputs were directly mapped into a HashMap.

Get Janak Avhad’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

This wasn’t theoretical. It was reported as CVE-2011–4858, where crafted inputs could degrade performance enough to cause denial-of-service scenarios across multiple JVM-based systems.

Java 8 addressed this by introducing treeification. Even under heavy collisions, performance now degrades to O(log n), which is far more manageable and makes such attacks impractical.

The concurrent resize issue in Java 7

There was another subtle but serious problem in Java 7. During resize, nodes were reinserted using head insertion. If two threads resized the map at the same time, this could corrupt the linked list and create a cycle.

Once that happened, a simple get() could enter an infinite loop, effectively pegging a CPU core at 100%.

Java 8 fixed this by switching to a more stable approach that preserves insertion order within buckets during resize. This eliminates the possibility of cycles forming during rehashing.

That said, HashMap is still not thread-safe. These fixes make it more robust, not safe for concurrent use.

K. Edge Cases & Gotchas

1. Null key handling

HashMap explicitly supports a single null key. Internally, hash(null) returns 0, so it always maps to bucket 0.

HashMap<String, Integer> map = new HashMap<>();
map.put(null, 42);   // stored at bucket 0
map.get(null);       // returns 42
map.put(null, 99);   // updates existing entry, returns 42

This is a deliberate design choice. In contrast, Hashtable and ConcurrentHashMap do not allow null keys.

2. Mutable keys — a silent failure

Using mutable objects as keys is a common and dangerous mistake. If the key’s state changes after insertion, its hashCode() may change as well. The entry remains in the original bucket, but future lookups compute a different index.

No exception is thrown. You just get null.

List<String> key = new ArrayList<>();
key.add("a");
map.put(key, 1);
key.add("b");        // mutation changes hashCode
map.get(key);        // returns null

Rule: Only use immutable keys.
Strings, boxed primitives, enums, and well-designed value objects are safe. Lists, arrays, and mutable custom objects are not.

3. Hash collision DoS

If many keys are forced into the same bucket, operations degrade. In Java 7, this meant O(n) performance across the board, which could be exploited in scenarios like HTTP parameter parsing.

Java 8 mitigates this with treeification, capping worst-case complexity at O(log n). However, this relies on keys being Comparable. If they aren’t, the fallback comparison is less robust.

In security-sensitive paths, prefer ConcurrentHashMap and ensure a well-distributed hashCode() implementation.

4. `equals()` and `hashCode()` contract

This contract is foundational and must be respected:

If a.equals(b) is true, then a.hashCode() == b.hashCode() must also be true
The reverse is not required; collisions are allowed
If you override one, you must override the other

Breaking this contract leads to subtle, hard-to-diagnose bugs. Objects that are logically equal may end up in different buckets, and lookups fail unexpectedly.

// BROKEN: overrides equals but not hashCode
class BadKey {
    int id;
    public boolean equals(Object o) {
        return ((BadKey) o).id == this.id;
    }
    // missing hashCode()
    // falls back to Object's identity-based implementation
}

Two BadKey(5) instances are equal by equals(), but produce different hash codes, so they land in different buckets. From the map’s perspective, they are unrelated keys.

L. Comparison with Other Maps

Comparison

| Feature      | HashMap                | Hashtable          | ConcurrentHashMap  | LinkedHashMap                | TreeMap                     |
| ------------ | ---------------------- | ------------------ | ------------------ | ---------------------------- | --------------------------- |
| Thread-safe? | No                     | Yes (full sync)    | Yes (fine-grained) | No                           | No                          |
| Null keys    | 1 allowed              | Not allowed        | Not allowed        | 1 allowed                    | Not allowed                 |
| Null values  | Allowed                | Not allowed        | Not allowed        | Allowed                      | Allowed                     |
| Order        | None                   | None               | None               | Insertion / access order     | Sorted (natural/comparator) |
| Performance  | Best (single-threaded) | Poor (global lock) | Best (concurrent)  | Slightly slower than HashMap | O(log n)                    |
| Structure    | Array + list/tree      | Array + list       | Array + list/tree  | HashMap + doubly linked list | Red-Black tree              |
| Introduced   | Java 2                 | Java 1             | Java 5             | Java 2                       | Java 2                      |

When to use what

HashMap
Default choice for general-purpose use in single-threaded or externally synchronized contexts.
ConcurrentHashMap
Go-to option for concurrent access. Designed for high throughput with minimal contention, and far more scalable than synchronizedMap.
LinkedHashMap
Use when iteration order matters. Supports both insertion order and access order, making it a solid base for LRU caches (accessOrder = true).
TreeMap
Use when you need sorted keys or range-based operations like floorKey(), ceilingKey(), or headMap().
Hashtable
Legacy class. Avoid in new code. It synchronizes every method on a single lock, which severely limits concurrency and scalability.

M. Real Interview Questions & Answers

Why is `HashMap` not thread-safe?

HashMap operations are not atomic. A single put() involves multiple steps: computing the index, traversing the bucket, inserting or updating, and possibly resizing. Without synchronization, two threads can interleave these steps and corrupt the structure.

In Java 7, concurrent resize could even create cycles in the linked list, leading to infinite loops. Java 8 fixed that specific issue, but data races, lost updates, and visibility problems still exist. Structural changes without proper synchronization break the happens-before guarantees and can leave the map in an inconsistent state.

Why must capacity be a power of 2?

Index calculation uses:

(n - 1) & hash

This is a fast bitmask operation, equivalent to hash % n only when n is a power of 2. In binary, powers of 2 look like 1000..., so n - 1 becomes 0111..., which cleanly extracts the lower bits.

If you pass a non-power-of-2 capacity, HashMap internally rounds it up to the nearest power of 2.

What happens when two keys have the same `hashCode()`?

They land in the same bucket. This is a collision.

The bucket stores multiple entries as a linked list or tree. On put(), the structure is traversed to check if the key already exists (update) or needs to be added. On get(), each node is checked using hash and then equals() until a match is found.

Can two different keys have the same `hashCode()`?

Yes. hashCode() returns a 32-bit integer, while the key space is effectively unbounded. Collisions are guaranteed.

The only requirement is: if two objects are equal (equals() returns true), they must have the same hash code. The reverse is not required.

If hashes match, why do we still need `equals()`?

A matching hash only narrows down the bucket. Multiple distinct keys can share the same hash.

equals() is the final check to confirm identity. You can think of hash as a coarse filter and equals() as the exact match.

What if you override `equals()` but not `hashCode()`?

The map breaks silently.

Two logically equal objects may produce different hash codes (default identity-based implementation), so they end up in different buckets. A lookup using an equivalent key won’t find the existing entry and will return null.

Why is the load factor 0.75?

0.75 is a practical balance between memory usage and performance.

At this level, bucket occupancy stays low enough to keep operations near O(1), while utilizing most of the allocated space. Lower values reduce collisions but waste memory. Higher values save memory but increase collision rates and degrade performance.

This choice is backed by probability analysis (Poisson distribution) under uniform hashing assumptions.

Worst-case time complexity in Java 8+

In the worst case, operations are O(log n).

This happens when many keys collide into the same bucket and the structure is treeified into a Red-Black tree. Before Java 8, the worst case was O(n) due to linked list traversal.

Tree-based performance depends on keys being comparable. If they aren’t, fallback mechanisms ensure correctness, but not always optimal ordering efficiency.

N. Practical Code Snippets

Simplified Node Class

static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    public K getKey()   { return key; }
    public V getValue() { return value; }
    public V setValue(V v) {
        V old = value; value = v; return old;
    }
}

put() — Pseudocode (Core Logic)

final V putVal(int hash, K key, V value) {
    Node<K,V>[] tab;
    int n, i;
    // 1. Lazy init: allocate table on first put
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 2. Empty bucket: direct insert
    if (tab[i = (n - 1) & hash] == null) {
        tab[i] = newNode(hash, key, value, null);
    } else {
        Node<K,V> e; K k;
        Node<K,V> p = tab[i];
        // 3. Key match at head
        if (p.hash == hash && ((k = p.key) == key || key.equals(k)))
            e = p;
        // 4. Tree bucket
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>) p).putTreeVal(this, tab, hash, key, value);
        // 5. Linked list traversal
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash); // convert to tree
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                    break; // found existing key
                p = e;
            }
        }
        // 6. Update value if key exists
        if (e != null) {
            V oldValue = e.value;
            e.value = value;
            return oldValue;
        }
    }
    // 7. New entry: check resize threshold
    if (++size > threshold)
        resize();
    return null;
}

get() — Pseudocode

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab;
    Node<K,V> first, e;
    int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0
        && (first = tab[(n - 1) & hash]) != null) {
        // Check first node (most common case: chain length 1)
        if (first.hash == hash && ((k = first.key) == key || key.equals(k)))
            return first;
        if ((e = first.next) != null) {
            // Tree lookup
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>) first).getTreeNode(hash, key);
            // Linear chain scan
            do {
                if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

O. Performance optimization tips

1. Set initial capacity to avoid rehashing

If you know the expected size, pre-size the map to avoid repeated resizes:

int expectedSize = 1000;
HashMap<String, Integer> map =
    new HashMap<>((int) (expectedSize / 0.75f) + 1);

This ensures the threshold comfortably accommodates your data without triggering a resize. Resizing is expensive, so avoiding it upfront pays off.

2. Design a good `hashCode()`

A well-distributed hash function is critical for performance.

Use all significant fields
Avoid relying on a single field for composite keys
Prefer prime multipliers (31 is commonly used and efficient)
Use Objects.hash(...) for clarity or rely on IDE/Lombok generation

// Good
@Override
public int hashCode() {
    return Objects.hash(userId, email, department);
}
// Bad
@Override
public int hashCode() {
    return department.hashCode();
}

Poor hashing leads to clustering, which directly impacts performance.

3. Avoid over-allocating capacity

Allocating far more capacity than needed wastes memory and slows down iteration. Iteration scans all buckets, not just populated ones.

A map with 100 elements and capacity 65,536 will still iterate over all 65,536 slots. Size your map realistically.

4. Prefer `computeIfAbsent()` and `getOrDefault()`

Avoid patterns that perform multiple lookups:

// Inefficient: double lookup
if (!map.containsKey(key)) {
    map.put(key, new ArrayList<>());
}
map.get(key).add(value);
// Better: single lookup
map.computeIfAbsent(key, k -> new ArrayList<>()).add(value);

This reduces redundant work and keeps the code cleaner.

5. Use `ConcurrentHashMap` for concurrency

Wrapping a HashMap with Collections.synchronizedMap() introduces a single global lock, which doesn’t scale.

ConcurrentHashMap uses finer-grained locking (and lock-free reads), allowing multiple threads to operate on different buckets simultaneously. This significantly improves throughput under concurrent workloads.

Summary

HashMap isn’t just a convenience API. It’s a carefully engineered data structure that balances speed, memory usage, hash distribution, collision handling, and concurrency trade-offs. Once you understand how it works internally, it stops being a black box and becomes something you can reason about and tune.

There are four core ideas you should have clear:

Hash spreading
The XOR-with-shift step improves distribution by mixing high bits into low bits, which directly affects bucket selection.
Power-of-two capacity
Enables fast index calculation using bitwise operations instead of modulo.
Load factor and threshold
Controls when resizing happens and how densely the table is filled before paying the O(n) rehash cost.
List to tree transition
The Java 8 optimization that converts long collision chains into Red-Black trees, capping worst-case performance at O(log n).

Get these right, and you’re not just using HashMap — you understand it well enough to predict its behavior under real-world load.

Quick Revision Cheat Sheet — By Claude

HashMap Internals — Interview Cheat Sheet

Structure

Backed by an array of Node<K, V> called table (default capacity = 16)
Each node holds: hash, key, value, next
Table size is always a power of 2
A bucket can be: null, single node, linked list, or Red-Black tree

Hashing

Raw hash: key.hashCode()
Spread: h ^ (h >>> 16) to improve lower-bit distribution
Index: (n - 1) & hash (bitwise, faster than modulo)
null key → hash = 0 → always maps to bucket 0

Collisions

Same index → handled via separate chaining (linked list)
Chain length ≥ 8 and table size ≥ 64 → convert to Red-Black tree
Tree shrinks to ≤ 6 → convert back to linked list
Tree ensures O(log n) worst-case vs O(n) for lists

Resize

Threshold = capacity × 0.75 (default: 12 at capacity 16)
Resize doubles capacity and rehashes all entries → O(n)
Java 8 optimization: node either stays or moves to index + oldCapacity
Pre-size to avoid rehashing:
new HashMap<>(expectedSize / 0.75f + 1)

Complexity

put / get / remove: O(1) average, O(log n) worst (Java 8+)
resize: O(n)
Iteration: O(capacity + n), depends on table size, not just entries

Key constants

DEFAULT_INITIAL_CAPACITY = 16
DEFAULT_LOAD_FACTOR = 0.75f
TREEIFY_THRESHOLD = 8, UNTREEIFY_THRESHOLD = 6
MIN_TREEIFY_CAPACITY = 64
MAXIMUM_CAPACITY = 1 << 30

Java 7 vs Java 8

Java 7: linked list only → O(n) worst case
Java 8: tree-based bins → O(log n) worst case
Java 7: head insertion during resize → risk of infinite loops in concurrency
Java 8: maintains order during resize → fixes that issue and simplifies hashing

Critical rules

Override equals() → must override hashCode()
If a.equals(b) is true → a.hashCode() == b.hashCode() must be true
Avoid mutable keys → leads to silent lookup failures
Not thread-safe → use ConcurrentHashMap for concurrency
Allows one null key; ConcurrentHashMap and Hashtable do not

Interview gotchas

Different keys can share the same hash (collisions are expected)
Matching hash ≠ equal keys → equals() confirms identity
Iteration order is undefined and can change after resize
Over-allocating capacity slows iteration (empty buckets are scanned)
Load factor 0.75 is a practical balance based on distribution behavior