How does HashMap work internally?

• Internal array: Node[] table – an array of buckets, each bucket holds null or a chain of entries
• Bucket index: hash & (capacity - 1) – bitwise AND is faster than modulo; capacity is always a power of 2
• Hash spreading: (h = key.hashCode()) ^ (h >>> 16) – XORs upper 16 bits with lower 16 bits so high bits influence bucket selection even with small tables
• Load factor: default 0.75; when size > capacity * loadFactor, the table doubles and all entries are rehashed
• Treeification: chain >= 8 nodes AND table >= 64 buckets → linked list converts to Red-Black tree (O(n) → O(log n))

What is the internal structure of HashMap?

At its core, HashMap is an array of nodes called table. Each slot in the array is a "bucket" that can hold zero or more key-value pairs.

// Simplified from OpenJDK source
public class HashMap<K,V> {
    Node<K,V>[] table;      // the bucket array
    int size;               // number of entries
    int threshold;          // capacity * loadFactor – resize trigger
    float loadFactor;       // default 0.75

    static class Node<K,V> {
        final int hash;     // cached hash of key
        final K key;
        V value;
        Node<K,V> next;     // pointer to next node in chain
    }
}

Each Node stores the hash (cached to avoid recomputing), the key, the value, and a next pointer for chaining collisions.

How does put() work step by step?

When you call map.put(key, value), HashMap performs these steps:

1. Compute hash: call key.hashCode(), then spread it with h ^ (h >>> 16) to mix high bits into low bits.
2. Find bucket: compute index = hash & (table.length - 1). Since table length is a power of 2, this is equivalent to hash % length but faster.
3. Check bucket: if the bucket is empty, create a new Node and place it there.
4. Handle collision: if the bucket is occupied, walk the chain. For each node, check node.hash == hash && node.key.equals(key). If found, replace the value. If not found, append a new node at the end.
5. Check treeification: if the chain now has 8 or more nodes and the table has at least 64 buckets, convert the chain to a Red-Black tree.
6. Check resize: if size > threshold (capacity * loadFactor), double the table and redistribute all entries.

package com.bank.demo;

import java.math.BigDecimal;
import java.util.*;

public class PutInternalsDemo {
    public static void main(String[] args) {
        Map<String, BigDecimal> balances = new HashMap<>(16, 0.75f);
        // table = new Node[16], threshold = 16 * 0.75 = 12

        // Step 1-3: hash("SAV2001"), find bucket, bucket empty → new Node
        balances.put("SAV2001", new BigDecimal("150000"));

        // Step 1-4: hash("CUR3001"), find bucket
        // If same bucket → chain; if different bucket → new Node
        balances.put("CUR3001", new BigDecimal("75000"));

        // Step 6: after 12 entries, resize triggers
        for (int i = 0; i < 10; i++) {
            balances.put("ACC" + i, BigDecimal.valueOf(i * 1000));
        }
        // Now size=12, threshold=12 → next put triggers resize to 32

        balances.put("FD4001", new BigDecimal("500000")); // 13th entry → resize!
        System.out.println("Size: " + balances.size());
    }
}

Size: 13

How does get() work?

The get(key) method follows a similar path but only reads:

1. Compute hash from the key.
2. Find bucket: index = hash & (table.length - 1).
3. If the bucket is null, return null (key not present).
4. If the bucket has a single node, check hash and equals. Match → return value.
5. If the bucket is a linked list, walk the chain comparing hash and equals.
6. If the bucket is a tree, search the Red-Black tree in O(log n).

package com.bank.demo;

import java.math.BigDecimal;
import java.util.*;

public class GetInternalsDemo {
    public static void main(String[] args) {
        Map<String, BigDecimal> balances = new HashMap<>();
        balances.put("SAV2001", new BigDecimal("150000"));

        // get: hash("SAV2001") → bucket → check hash & equals → return value
        BigDecimal balance = balances.get("SAV2001");
        System.out.println("Balance: " + balance);

        // get for absent key: bucket is null or chain has no match → null
        BigDecimal absent = balances.get("UNKNOWN");
        System.out.println("Absent: " + absent);
    }
}

Balance: 150000
Absent: null

Why does the hash function XOR high and low bits?

The bucket index uses only the lower bits of the hash (because hash & (capacity - 1) with capacity 16 uses only bits 0-3). If the hashCode() of your keys differs only in the high bits, all keys would map to the same bucket – massive collisions.

The spreading function (h = key.hashCode()) ^ (h >>> 16) XORs the upper 16 bits with the lower 16 bits. This ensures that differences in high bits influence the bucket index even for small tables.

// Without spreading: hashCode 0x0000FFFF and 0x0001FFFF
// Both have lower 4 bits = 1111 → same bucket (index 15)

// With spreading:
// 0x0000FFFF ^ (0x0000FFFF >>> 16) = 0x0000FFFF ^ 0x00000000 = 0x0000FFFF
// 0x0001FFFF ^ (0x0001FFFF >>> 16) = 0x0001FFFF ^ 0x00000001 = 0x0001FFFE
// Lower 4 bits: 1111 vs 1110 → different buckets!

How does resize work?

When size > capacity * loadFactor, HashMap doubles the table and redistributes every entry.

Java 8 optimized redistribution: instead of recomputing hash % newCapacity for every entry, it checks one bit. When capacity doubles from n to 2n, the new mask has one more bit. If that bit in the hash is 0, the entry stays at its current index. If 1, it moves to oldIndex + oldCapacity.

package com.bank.demo;

import java.util.*;

public class ResizeDemo {
    public static void main(String[] args) {
        // Start with capacity 4 for easy visualization
        Map<String, String> map = new HashMap<>(4, 0.75f);
        // threshold = 4 * 0.75 = 3 → resize after 3rd entry

        map.put("A", "1"); // size=1
        map.put("B", "2"); // size=2
        map.put("C", "3"); // size=3, threshold=3 → resize!
        // Table doubles: 4 → 8. All entries redistributed.
        map.put("D", "4"); // now in 8-capacity table

        System.out.println("Map: " + map);
        System.out.println("Size: " + map.size());
    }
}

Map: {A=1, B=2, C=3, D=4}
Size: 4

How do you pre-size HashMap correctly?

When you know the expected number of entries, pre-size the HashMap to avoid resizing.

The formula: initialCapacity = expectedSize / loadFactor + 1. For the default load factor of 0.75: expectedSize * 4 / 3 + 1. HashMap will round up to the next power of 2.

package com.bank.service;

import java.math.BigDecimal;
import java.util.*;

public class PreSizingDemo {
    public static void main(String[] args) {
        int expectedAccounts = 10_000;

        // WRONG: default constructor, resizes ~13 times to reach 10K
        Map<String, BigDecimal> bad = new HashMap<>();

        // CORRECT: pre-sized, zero resizes
        int initialCapacity = expectedAccounts * 4 / 3 + 1; // 13334
        Map<String, BigDecimal> good = new HashMap<>(initialCapacity);
        // HashMap rounds up to next power of 2: 16384
        // threshold = 16384 * 0.75 = 12288 > 10000 → no resize!

        // ALSO CORRECT: Java 19+ has a factory method
        // Map<String, BigDecimal> best = HashMap.newHashMap(expectedAccounts);

        for (int i = 0; i < expectedAccounts; i++) {
            good.put("ACC" + i, BigDecimal.valueOf(i * 100));
        }
        System.out.println("Size: " + good.size());
    }
}

Size: 10000

What are common mistakes?

Mistake 1: Not pre-sizing HashMap for known data

// WRONG: starts at 16, resizes ~13 times for 10K entries
Map<String, String> map = new HashMap<>();

// CORRECT: pre-sized
Map<String, String> map = new HashMap<>(14000); // 10000 / 0.75 + 1

Mistake 2: Setting load factor too low or too high

// Load factor 0.5: wastes 50% memory, fewer collisions
// Load factor 0.9: saves memory, but more collisions and slower
// 0.75 is the best balance for most applications

Mistake 3: Not implementing hashCode() for custom keys

// WRONG: relies on Object.hashCode() (memory address based)
class Account {
    String id;
    // No hashCode override!
}
// Two Account objects with same id are treated as DIFFERENT keys

// CORRECT:
class Account {
    String id;
    @Override public int hashCode() { return id.hashCode(); }
    @Override public boolean equals(Object o) {
        return o instanceof Account a && a.id.equals(this.id);
    }
}

What should a senior engineer know?

- Capacity is always a power of 2. This enables hash & (capacity - 1) instead of hash % capacity. Bitwise AND is one CPU instruction; modulo requires division (~10x slower). HashMap internally rounds any initial capacity to the next power of 2.

- The null key goes to bucket 0. HashMap special-cases null keys: hash(null) = 0, so the null key always goes to bucket 0.

- Lazy initialization. The table is not allocated until the first put(). The constructor only sets the load factor and threshold. This saves memory for maps that are created but never populated.

- Java 19 HashMap.newHashMap(int numMappings). This factory method calculates the correct initial capacity for the given number of mappings, avoiding the expectedSize * 4/3 + 1 formula.

- resize() is O(n). Every entry is visited and potentially moved. For a map with 10 million entries, resize copies 10 million entries. Pre-sizing eliminates this cost.

What are common interview follow-up questions?

• "Why is the initial capacity 16?" – Power of 2, reasonable default for small maps.
• "What is the time complexity of put and get?" – O(1) average, O(log n) worst case (treeified bucket).
• "What happens if two keys have the same hashCode?" – Collision; they go to the same bucket and are compared with equals().
• "Why is load factor 0.75?" – Balance between space (lower = more waste) and time (higher = more collisions).
• "What is the maximum capacity?" – 2^30 (1,073,741,824).