Java HashMap Internal Working

Java HashMap Internal Working

Every HashMap operation — put(), get(), remove() — works by computing a hash from the key, converting that hash to a bucket index in an array, and either storing or reading from that bucket. Understanding this one mechanism explains every HashMap characteristic that comes up in interviews and production debugging: why null is allowed as a key, what happens when two keys hash to the same bucket, why HashMap slows down when equals() and hashCode() are broken, and what treeification means in Java 8+.

What Is Inside a HashMap?

HashMap<K, V> is backed by an array of Node<K, V> objects called table. Each position in the array is a bucket. A bucket holds zero, one, or many entries — multiple entries appear when two different keys hash to the same bucket index (a collision). The HashMap class holds a handful of fields that govern its sizing and growth.

HASHMAP INTERNAL FIELDS (simplified from JDK source):

  transient Node<K,V>[]  table;         ← the bucket array
  transient int          size;           ← number of key-value pairs stored
  int                    threshold;      ← resize when size > threshold
  final float            loadFactor;     ← default 0.75
  transient int          modCount;       ← fail-fast iterator support

  static final int DEFAULT_INITIAL_CAPACITY = 16; ← always a power of 2
  static final float DEFAULT_LOAD_FACTOR    = 0.75f;
  static final int TREEIFY_THRESHOLD        = 8;  ← chain → Red-Black tree
  static final int UNTREEIFY_THRESHOLD      = 6;  ← tree → chain on shrink
  static final int MIN_TREEIFY_CAPACITY     = 64; ← min table size to treeify

  Node<K,V> structure:
    final int   hash;    ← cached hash of the key
    final K     key;
    V           value;
    Node<K,V>   next;    ← next node in the same bucket (null = end of chain)

  TreeNode<K,V> structure (Java 8+, used after treeification):
    Extends LinkedHashMap.Entry which extends Node.
    Adds: parent, left, right, prev, red fields.
    A Red-Black tree node — O(log n) lookup instead of O(n) chain scan.

INITIAL STATE (new HashMap<>()):
  table     = null   ← lazy: allocated on first put()
  size      = 0
  threshold = 12     ← 16 * 0.75
  loadFactor = 0.75

Basic Overview — How Each Core Method Works

OPERATION       WHAT HAPPENS INTERNALLY                           COMPLEXITY
──────────────────────────────────────────────────────────────────────────────
put(k, v)       1. hash(k): compute spread hash                   O(1) avg
                2. index = hash & (n-1): bucket position           O(n) worst
                3. if bucket empty: insert new Node
                4. if bucket non-empty: walk chain for key match
                   — found:  update value
                   — absent: append Node to chain (or tree insert)
                5. if ++size > threshold: resize()

get(k)          1. hash(k): compute spread hash                   O(1) avg
                2. index = hash & (n-1): bucket position           O(n) worst
                3. walk chain/tree at bucket for key match
                4. return matching value or null

remove(k)       1. hash(k), compute index                         O(1) avg
                2. walk chain, rewire prev.next to skip target node

containsKey(k)  hash + index + chain walk                         O(1) avg

containsValue(v) full scan all buckets + all chains               O(n) always

size()          return size field                                   O(1)

resize()        create new table[2 × oldCapacity]                  O(n)
                rehash all existing entries into new positions

KEY RULE:
  Average O(1) assumes good hash distribution — one or few entries per bucket.
  Worst case O(n) occurs when all keys hash to the same bucket (degenerate).
  Java 8 treeification caps the worst case at O(log n) per bucket.

When to Use HashMap

USE HashMap WHEN:
  1. Key-value lookup with O(1) average get/put performance
     — product catalog by SKU, session store by token
     — any scenario where "find by key" is the primary operation

  2. Key order does not matter
     — HashMap does NOT preserve insertion order or sort keys
     — use LinkedHashMap for insertion-order iteration
     — use TreeMap for sorted-key iteration

  3. Single-threaded or externally synchronised access
     — HashMap is NOT thread-safe
     — use ConcurrentHashMap for concurrent access

  4. Null key or null values are needed
     — HashMap allows exactly one null key and unlimited null values
     — Hashtable, ConcurrentHashMap, and TreeMap reject null keys

CHOOSE ALTERNATIVES WHEN:
  LinkedHashMap → insertion or access order iteration matters
  TreeMap       → keys must stay sorted for range queries
  ConcurrentHashMap → multiple threads read/write concurrently
  Hashtable     → never — it is legacy; use ConcurrentHashMap instead
  EnumMap       → keys are all from one enum — faster, zero hashing

CRITICAL REQUIREMENT:
  Keys used in a HashMap MUST correctly implement equals() and hashCode().
  Objects that are equal by equals() MUST return the same hashCode().
  Breaking this contract causes silent data loss — puts succeed but
  gets return null for keys that appear to exist.

How HashMap Works Internally

The Hash Function

Before any key touches the bucket array, its hashCode() passes through a spreading function that mixes the high bits into the low bits.

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

WHY SPREAD THE HASH?

  HashMap capacity is always a power of 2 (16, 32, 64 ...).
  Bucket index = hash & (capacity - 1)
  For capacity 16: index = hash & 15 = hash & 0b00001111
  Only the LOWEST 4 bits of hash determine the bucket.

  If hashCode() returns values that only vary in high bits:
    "abc"  → hashCode = 0xAB000001 → low 4 bits = 0001 → bucket 1
    "xyz"  → hashCode = 0xCD000001 → low 4 bits = 0001 → bucket 1
    "pqr"  → hashCode = 0xEF000001 → low 4 bits = 0001 → bucket 1
    All three keys land in the same bucket despite very different hashCodes.

  XOR with upper 16 bits:
    h ^ (h >>> 16) mixes high bits into low bits
    Now high-bit differences produce different low bits
    Better distribution across buckets — fewer collisions

put() — Step by Step

put("order-101", Order) on a HashMap with capacity=16, size=3:

  Step 1: hash("order-101")
    h = "order-101".hashCode()  — say h = 0x9E3779B9
    spread = h ^ (h >>> 16) = 0x9E3779B9 ^ 0x00009E37 = 0x9E36E78E

  Step 2: bucket index = spread & (16 - 1)
    = 0x9E36E78E & 0x0000000F = 0xE = 14
    This key lands in bucket 14.

  Step 3: examine table[14]
    CASE A — table[14] is null (empty bucket):
      Create new Node: {hash=spread, key="order-101", value=Order, next=null}
      table[14] = new node
      size++ → 4

    CASE B — table[14] is not null (collision):
      Walk the chain at table[14]:
        For each node n in the chain:
          if (n.hash == spread && (n.key == key || key.equals(n.key)))
            → key exists: update n.value with new value, return old value
        If no match found after walking full chain:
          → Append new Node to end of chain (or insert into tree)
          size++

  Step 4: if (size > threshold = 16 * 0.75 = 12):
    resize() — doubles the table to capacity 32

  NULL KEY:
    hash(null) = 0  → always stored in bucket 0
    put(null, value) → table[0] chain, key compared with == null check

get() — Hash, Index, Walk

get("order-101"):

  Step 1: hash("order-101") → same spread hash as during put
  Step 2: index = spread & (n-1) → same bucket index (14)
  Step 3: examine table[14]:
    if (table[14] == null) return null  ← key never stored here

    Walk chain from table[14]:
      for each node n:
        if (n.hash == spread && (n.key == "order-101" || "order-101".equals(n.key)))
          return n.value   ← FOUND

    return null  ← key not found

WHY HASH IS CHECKED BEFORE equals():
  hash comparison is a cheap int == int check.
  equals() may be expensive (String comparison, custom object).
  Checking hash first eliminates most non-matching nodes before equals().
  Only nodes with the same hash (and same index) call equals().

WHY BOTH == AND equals() ARE CHECKED:
  n.key == key  checks reference equality (fast for interned Strings,
                same-instance keys, enum constants)
  key.equals(n.key) checks logical equality for non-identical objects
  == first short-circuits to avoid equals() for the common same-reference case

Collision Handling — Chain to Tree

COLLISION HANDLING EVOLUTION:

  BEFORE Java 8: each bucket is a singly-linked list
    Collisions grow the chain linearly.
    Worst case: all n keys in one bucket → get() is O(n).
    Hash flooding attack: deliberately craft keys with same hash
    to degrade a HashMap to O(n) — a known DoS vector.

  JAVA 8+: bucket converts to a Red-Black tree when chain is too long.

  TREEIFICATION RULE:
    if (chain length >= TREEIFY_THRESHOLD = 8
        AND table.length >= MIN_TREEIFY_CAPACITY = 64):
      convert bucket's linked chain → TreeNode Red-Black tree
      get/put in that bucket: O(log n) instead of O(n)

    if (table.length < 64):
      resize() instead of treeifying — small table means better to
      rehash entries to spread across more buckets first

  UNTREEIFY RULE:
    if (tree node count <= UNTREEIFY_THRESHOLD = 6 after removes):
      convert tree back to linked list

VISUAL — what bucket 5 looks like with 9 colliding keys:

  BEFORE treeification (chain, length = 8):
  table[5] → [K1]→[K2]→[K3]→[K4]→[K5]→[K6]→[K7]→[K8] → null
              O(n) worst-case lookup

  AFTER treeification (Red-Black tree):
  table[5] → TreeNode(K4)
               /         \
          TreeNode(K2)   TreeNode(K6)
           /      \        /      \
         K1       K3     K5       K7
                                    \
                                    K8
  O(log n) lookup in the tree

resize() and Rehashing

RESIZE TRIGGER AND PROCESS:

  TRIGGER: size > threshold  (threshold = capacity × loadFactor)
    Default: size > 16 × 0.75 = 12 → resize to capacity 32
    After resize: threshold = 32 × 0.75 = 24

  RESIZE PROCESS:
    1. newCapacity = oldCapacity << 1   ← double (always power of 2)
    2. newTable = new Node[newCapacity]
    3. For each bucket in oldTable:
         For each Node in the bucket:
           Recompute bucket index for newCapacity:
             new index = node.hash & (newCapacity - 1)
           Place in newTable at new index

  JAVA 8 OPTIMISATION — rehash without recomputing hash:
    When capacity doubles from 16 to 32, new bit mask gains one higher bit.
    For a node with hash h:
      Old index = h & 01111  (4 bits)
      New index = h & 11111  (5 bits)
    The new bit position is (h & oldCapacity):
      if 0 → new index = old index (node stays in same bucket position)
      if 1 → new index = old index + oldCapacity (node moves to upper half)

    No need to rerun the hash function — just test one bit of the stored hash.
    Nodes in each old bucket split into two new buckets in O(1) per node.

GROWTH SEQUENCE (default load factor 0.75):
  capacity=16  threshold=12  → resize at 13th entry → capacity=32
  capacity=32  threshold=24  → resize at 25th entry → capacity=64
  capacity=64  threshold=48  → resize at 49th entry → capacity=128

Core Operations with Examples

put(), get(), and Collision Behaviour

Output:
=== Normal HashMap: put and get ===
get(LAPTOP-15)   : 42
get(null)        : -1
get(MISSING-KEY) : null
size             : 5
Updated LAPTOP-15, old value was: 42
New stock: 50

=== putIfAbsent vs put ===
Initial: user-priya
After put: user-rohan
putIfAbsent result: user-priya
After putIfAbsent: user-priya

=== Collision keys (same hashCode) ===
get(k1): value-alpha
get(k2): value-beta
get(k3): value-gamma
All three keys hash to same bucket — get walks chain

The Broken equals/hashCode Trap

Output:
=== BROKEN — equals without hashCode ===
Inserted with insertKey
get(insertKey)  : Delivered
get(lookupKey)  : null!
insertKey.equals(lookupKey): true
But get returns null because hashCodes differ — silent data loss

=== CORRECT — both equals and hashCode implemented ===
get(insertKey2) : Delivered
get(lookupKey2) : Delivered

Resize and Load Factor Effects

Output:
=== Default HashMap resize sequence ===
  size=1   → capacity grew to 16   (threshold was 0)
  size=13  → capacity grew to 32   (threshold was 12)
  size=25  → capacity grew to 64   (threshold was 24)
  size=49  → capacity grew to 128  (threshold was 48)
  size=97  → capacity grew to 256  (threshold was 96)

=== Pre-sized HashMap — no resize events ===
Pre-sized capacity: 256 (for 100 expected entries)
After 100 puts, capacity still: 256 (no resize occurred)

=== Useful Java 8 HashMap operations ===
Word counts: {redis=1, kafka=1, java=3, spring=2}
getOrDefault(kafka, 0)  : 1
getOrDefault(docker, 0) : 0
Grouped: {backend=[Spring, Hibernate], frontend=[React]}

Basic Example

Output:
Lookup result: Start
Map size: 1

Because Point overrides both equals() and hashCode() using the same fields (x and y), HashMap computes the same bucket index for both Point instances, and equals() then confirms the match inside that bucket. That is why get(new Point(1, 2)) finds the value even though it is a completely different object from the one passed to put() — this hashCode-then-equals two-step lookup is exactly how every HashMap operation works internally.

Performance Considerations

Iteration cost includes empty buckets. entrySet() traversal visits every slot in the table array, including empty ones. A HashMap with capacity 256 and only 10 entries still visits all 256 slots during full iteration. For small maps with many entries, this is negligible. For maps where iterating all entries is frequent and the fill ratio is low, this overhead adds up.

Resize is a production concern at scale. A HashMap receiving 1 million entries without pre-sizing triggers approximately 17 resize operations — each copying all entries into a new table. Pre-sizing with new HashMap<>(expectedSize / 0.75 + 1) eliminates all resize work. At high request rates, mid-traffic resizes create latency spikes that are difficult to reproduce in testing.

A broken hashCode causes O(n) degradation silently. If hashCode() returns a constant (or a narrow range of values), all entries land in one or a few buckets. get() becomes O(n) chain scan — or O(log n) after treeification — instead of O(1). The code compiles and runs correctly; the only symptom is latency increase under load.

Best Practices

Always override both equals() and hashCode() together when using a custom class as a HashMap key. They must use the same fields. Objects.hash(field1, field2) is the clean way to implement hashCode(). Using @Override on both is not optional — it is the contract that HashMap depends on for correctness.

Pre-size the HashMap when the expected number of entries is known. new HashMap<>((int)(expectedEntries / 0.75) + 1) allocates a table large enough to hold all entries before the load factor threshold. This eliminates resize events. In services that build large maps during request handling or startup loading, pre-sizing is a measurable latency improvement.

Use getOrDefault(), computeIfAbsent(), and merge() instead of manual null checks. The pattern if (map.get(key) == null) map.put(key, new ArrayList<>()) is not atomic and is verbose. map.computeIfAbsent(key, k -> new ArrayList<>()) is both cleaner and correct. merge(key, 1, Integer::sum) replaces the common count = map.getOrDefault(key, 0); map.put(key, count + 1) pattern.

Make keys immutable. Mutable objects used as keys are a silent correctness trap: if the key's fields change after insertion, hashCode() returns a different value, the key lands in a different bucket, and get() returns null for a key that is visually in the map. String, Integer, Long, UUID, record classes, and any class with all-final fields are safe keys.

Common Mistakes

Mistake 1 — Overriding equals() Without hashCode()

Mistake 2 — Iterating and Modifying Simultaneously

Output:
{Laptop=10, Mouse=5}

Mistake 3 — Using Mutable Objects as Keys

Mistake 4 — Not Pre-Sizing for Bulk Load

Interview Questions

Q1. Explain how put() works internally in HashMap.

put(key, value) computes a spread hash by XOR-ing the key's hashCode() with its upper 16 bits — hash(key) = h ^ (h >>> 16). The bucket index is then hash & (capacity - 1), which is a fast bitwise AND because capacity is always a power of 2. If the bucket is empty, a new Node is inserted directly. If occupied, the existing chain is walked comparing hash first (cheap int equality), then equals(). A matching key updates the value and returns the old one. No matching key appends a new Node to the chain. Finally, if ++size > threshold, resize() doubles the table capacity.

Q2. What is treeification in Java 8 HashMap and when does it trigger?

When a single bucket's chain grows to TREEIFY_THRESHOLD = 8 nodes and the table length is at least MIN_TREEIFY_CAPACITY = 64, the chain converts to a Red-Black tree (TreeNode). Lookups in that bucket change from O(n) chain scan to O(log n) tree traversal. If the table length is below 64, the HashMap resizes instead of treeifying — better distribution across more buckets is preferred. When entries are removed and a tree bucket shrinks to UNTREEIFY_THRESHOLD = 6 nodes, it converts back to a linked list.

Q3. Why does HashMap capacity always stay as a power of 2?

Bucket index is computed as hash & (capacity - 1). When capacity is a power of 2, capacity - 1 is a bitmask of all 1s in the lower bits — for example, capacity 16 gives mask 0b00001111. The bitwise AND with this mask extracts exactly the lower bits of the hash, which is a single machine instruction. If capacity were arbitrary (say, 15), the index computation would require a modulo division — slower and not aligned to the hash distribution. Power-of-2 sizing also enables the O(1) resize optimisation where each existing entry's new bucket is determined by testing a single bit of its stored hash.

Q4. What happens when two keys have the same hashCode but different equals?

They hash to the same bucket (collision). The bucket holds both entries as a chain (or tree if the chain is long enough). put() for the second key walks the chain, finds that equals() returns false for the existing key, and appends a new Node. Both entries exist independently in the same bucket. get() for either key computes the same bucket index, then walks the chain comparing both hash and equals() until the correct node is found.

Q5. Why must keys be immutable in a HashMap?

If a mutable key's fields change after it has been inserted, its hashCode() returns a new value. The next get() call computes the new hash, derives a new bucket index, and finds no entry there — even though the key visually exists in the map. The entry is now "stranded" in the bucket corresponding to the original hash. This produces silent correctness failures — the code compiles, runs without exceptions, but returns null for keys that appear present. String, Integer, record classes, and all-final-field classes are safe keys.

Q6. What is the significance of the load factor in HashMap?

The load factor (default 0.75) determines when the HashMap resizes. threshold = capacity × loadFactor. When size > threshold, the table doubles. A higher load factor (e.g., 0.9) delays resizing — more entries before a grow event — but increases average chain length and degrades lookup performance. A lower load factor (e.g., 0.5) resizes earlier, keeping chains short and lookups fast, but wastes memory with more empty bucket slots. The default 0.75 is the empirically chosen balance between time (chain length) and space (empty buckets) for typical usage patterns.

FAQs

Why does HashMap allow null keys but ConcurrentHashMap does not?

HashMap's hash() method has a special case: hash(null) = 0, directing null keys to bucket 0. get(null) also checks bucket 0 for a node with key == null. ConcurrentHashMap is designed for concurrent access and uses null as a sentinel signal — get() returning null means the key is absent; there is no way to distinguish "key maps to null" from "key not present" in a concurrent context without additional synchronisation. Removing null support eliminates this ambiguity.

What is the difference between HashMap and LinkedHashMap internally?

LinkedHashMap extends HashMap and adds a doubly-linked list that runs through all entries in insertion order (or access order, if configured). Each entry is a LinkedHashMap.Entry that extends HashMap.Node with two extra fields: before and after pointing to the previous and next entries in insertion sequence. The hash table structure is identical. The extra linked list means LinkedHashMap iteration is O(n) over entries in insertion order, while HashMap iteration is O(n + capacity) visiting all bucket slots including empty ones.

Does HashMap maintain any ordering of keys?

No. HashMap makes no guarantee about iteration order — it depends on the hash distribution and the insertion history. Iteration order can change after a resize. For predictable iteration order, use LinkedHashMap (insertion order) or TreeMap (natural or comparator order). Assuming HashMap has consistent iteration order is a common subtle bug in test code.

How many times does a HashMap entry get copied during resize operations when inserting 1 million entries?

Each resize event copies all existing entries. Starting from capacity 16, the resize sequence reaches capacity ~1.5 million (next power of 2 above 1 million / 0.75 = 1,333,333) in about 17 resize steps. Each entry is copied once per resize after it is inserted. The total number of extra copies across all resizes is approximately equal to the final entry count — roughly 1 million extra copy operations. Pre-sizing with new HashMap<>(1_333_334) eliminates all of this.

What is the difference between HashMap.get() returning null and a key being absent?

There is no difference at the API level if null values are used. map.get(key) returns null both when the key is absent and when the key maps to a null value. To distinguish these two cases, use map.containsKey(key). If containsKey() returns true but get() returns null, the key is present with a null value. getOrDefault(key, defaultValue) is the clean way to handle the absent-key case when null values are not used.

Why is the default load factor 0.75 and not 1.0 or 0.5?

A load factor of 1.0 fills every bucket before resizing, maximising space efficiency but increasing average chain length — lookups degrade as the table fills. A load factor of 0.5 resizes at half capacity, keeping chains very short and lookups fast, but doubles the memory footprint for empty bucket slots. The default 0.75 is the empirically validated balance: at 75% fill, average chain lengths stay close to one, lookup performance remains O(1) in practice, and memory utilisation is reasonable. This value comes from Poisson distribution analysis — at load factor 0.75, the probability of any bucket having 8 or more entries (the treeification threshold) is below 0.00000006.

Summary

HashMap<K, V> is a Node<K, V>[] bucket array where every put() and get() operation starts with the same two steps: compute a spread hash using key.hashCode() ^ (h >>> 16), then derive a bucket index using hash & (capacity - 1). Collisions are handled by linked chains that treeify to Red-Black trees when a bucket grows beyond 8 nodes and the table has at least 64 slots. Capacity is always a power of 2 to enable bitwise AND indexing. When size > capacity × 0.75, the table doubles and all entries are rehashed.

Two implementation details answer most HashMap interview questions at product-based companies: the spread hash function (why it XORs with upper 16 bits and why it matters for distribution) and the treeification mechanism (when it triggers, what it prevents, and what it costs). The most common production bug is overriding equals() without hashCode() — silent data loss, no exception, extremely difficult to debug under load.

What to Read Next