Java 18: internals de HashMap
easy⏱ 5 mincoursejava
Hash, bucket, chain
bucket = hash(key) & (table.length - 1). The & (n-1) is why table.length is always a power of 2 — the mask cheaply replaces modulo. hash(key) in Java 8 XORs the high bits: h ^ (h >>> 16) to spread poor-quality hashes across buckets.
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Load factor & resize
Default load factor is 0.75 — when size > capacity * 0.75, the table doubles and every entry is rehashed. Doubling means each entry stays in its old bucket or moves to oldBucket + oldCap — cheap. Too-low load factor wastes memory; too-high load factor means long chains.
Treeification (Java 8+)
If a bucket's chain reaches 8 nodes and the table has at least 64 buckets, the chain converts to a red-black tree — lookups drop from O(n) to O(log n). On removal below 6, it degrades back to a list. This mitigates worst-case hash attacks and poor hashCode impls.
Build a mini HashMap
Implement MiniMap with: put(k, v), get(k), size, and a buckets() view. Bucket count = 16 initially, double on load > 0.75. Use a chain (array) per bucket. Insert 30 entries and log the bucket distribution + whether any bucket hit the treeify threshold.
hashCode quality matters
A bad hashCode that returns 1 for all keys turns a HashMap into a linked list — every operation O(n). Objects.hash(field1, field2) is the lazy-correct choice; for perf-critical keys, hand-roll using primes (17 * 31 + field.hashCode()).
Quiz: Why table is power-of-2
Why is HashMap's table length always a power of 2? So bucket = hash & (n-1) works — a bitmask is 10-50x faster than modulo on most CPUs. If you chose a prime capacity you'd need hash % n which is slower.