← Lab

HashMap internals · OpenJDK 21

A deterministic semantic trace of hashCode, spread, mask, bucket lookup, equals, mutation, resize split, and verified tree-bin gates. This is a teaching model of Java 21 behavior, not a JVM profiler.

MODELED, NOT MEASURED
no JVM addresses · no object-byte claim
no CPU/cache counters · no runtime benchmark
OpenJDK 21 GA HashMap.java ↗Java 21 HashMap API ↗Java 21 Map key/order contract ↗semantic fragment IDs · never source line numbers

Constructor input is rounded to a power-of-two allocation target. The table remains null until the first put.

Configure the constructor, then run a put/get/remove operation.

deterministic scenario fixtures
No replay yet. The initial table is intentionally unallocated.
current semantic source fragment
hashmap.hash

hashCode → spread

raw = (key == null) ? 0 : key.hashCode()
hash = raw ^ (raw >>> 16)

Boundary: JDK 21 behavior, rendered as a semantic fragment rather than source line numbers.

narration

Run an operation to create semantic micro-steps.

replay ledger

No steps.

logical view

key → bucket → chain / tree

cap nullsize 0threshold 4
table = null

threshold=4 currently means allocation target, not resize threshold.

machine model · not observed JVM layout

reference array + separately allocated entries

semantic IDs, no addresses

The table is modeled as contiguous reference slots. Entry cards expose hash/key/value/next fields but make no claim about object headers, compressed references, padding, physical placement, registers, or cache outcomes.

table reference slots · contiguous model
table reference = null
entry objects · relative placement unknown
no entry objects
Locality trade-off: scanning adjacent table slots is different from following references between entry objects. Pointer chasing may have poorer locality, but this replay records only slot scans and reference reads/writes. It does not observe cache misses.

Invariant receipt

Run an operation to attach an invariant receipt to every step.

Modeled work counters · cumulative

Counts semantic work only. These are not nanoseconds, CPU cycles, allocations in bytes, or cache misses.

No operation work yet.

⌨️ code console — every line uses the same engine; replay opens on the final operation · saved to your browser

Five implementation shapes

Illustrative review snippets. This lab does not compile or execute them.

final class AccountKey {
  String accountId;
  String email;

  public boolean equals(Object other) {
    return other instanceof AccountKey k
        && accountId.equals(k.accountId);
  }

  public int hashCode() {
    return email.hashCode(); // different field: broken
  }
}
broken

Broken equals / hashCode

equals uses accountId, but hashCode uses email. Equal objects can enter different buckets.

Trade-off: This violates the Object contract; it is not a performance tuning choice.

What the trace must teach

Complexity and memory statements below are analytical or modeled, never measured runtime.

Expected O(1), not a guarantee

Java 21 documents constant-time get/put only when hashes disperse entries across buckets. The counters here are modeled operations, not runtime.

Capacity × load factor

Capacity is the reference-array length. First allocation computes a Java-float product; from capacity 16 onward OpenJDK doubles the previous threshold when doubling the table. Before allocation the field holds the rounded target.

Mask instead of inferred modulo

A power-of-two capacity makes capacity−1 a low-bit mask. The spread step folds high hash bits down before the AND.

Resize spike and amortization

One resize scans the old table and relinks existing entries, so that put is expensive. Across geometric growth, the occasional work is amortized over many inserts.

Mutable keys break the route back

HashMap stores the spread hash computed at insertion. If the same key object later reports a different hashCode, lookup can start in another bucket.

Collision and security degradation

Many colliding keys increase comparisons and pointer traversal. Tree bins are conditional mitigation, not cryptographic hashing or a universal worst-case guarantee.

Memory overhead and locality

The model separates one reference array from entry objects with key/value/next fields. Pointer chasing can reduce locality, but this lab does not observe cache misses or object byte size.

List / tree-bin trade-off

TreeNodes add links and balancing work. OpenJDK reserves them for sufficiently large bins and tables; exact removal untreeification depends on tree shape.

Iteration order is not a contract

A replay is deterministic for teaching, but Java 21 HashMap explicitly makes no guarantee that encounter order stays constant.

Data Structure Internals roadmap · not completion status

This change implements HashMap only. Every other item below remains a roadmap entry, not a shipped claim.

contiguous
array · dynamic array · string/buffer
linked
singly/doubly linked list
restricted access
stack · queue · deque · ring buffer
hashing
HashMap current · collision strategy · resize
ordered trees
BST · AVL · Red-Black · B-tree/B+tree
priority
binary heap · indexed heap
string
trie · radix tree · suffix structures
connectivity
disjoint set / union-find
graph representations
adjacency list · matrix · CSR
later
Bloom filter · skip list · concurrent map