Illustrated diagram of Java HashMap internals — hashing, bucket array, collision handling with linked list and TreeNode.
| Concept | Value / Behaviour | Notes |
|---|---|---|
| Default initial capacity | 16 buckets | Always a power of 2 |
| Default load factor | 0.75 | Resize when 75% full |
| Resize threshold | capacity × load factor | 16 × 0.75 = 12 entries triggers resize |
| Resize multiplier | 2× | New capacity = old × 2 |
| Bucket structure (< 8 entries) | Singly linked list | O(n) worst-case lookup |
| Bucket structure (≥ 8 entries) | Red-Black Tree (TreeNode) | O(log n) worst-case lookup |
| Tree → list conversion threshold | < 6 entries after removal | Untreeify back to linked list |
| Null key | Allowed — stored in bucket 0 | Only one null key permitted |
| Null values | Allowed — multiple | Use containsKey() to distinguish null vs absent |
| Step | Operation | Code / Detail |
|---|---|---|
| 1. hashCode() | Called on the key | User-defined or Object default |
| 2. Spread hash | hash ^ (hash >>> 16) | XORs upper 16 bits into lower to reduce collisions |
| 3. Bucket index | hash & (capacity - 1) | Fast modulo — works because capacity is power of 2 |
| 4. Key equality | equals() on existing keys | Must override both hashCode() and equals() together |
| 5. Insert / update | Replace value if key exists | Returns old value on put(), null if new key |
| Operation | Average Case | Worst Case (all keys in one bucket) |
|---|---|---|
| get(key) | O(1) | O(n) list / O(log n) tree |
| put(key, value) | O(1) | O(n) list / O(log n) tree |
| remove(key) | O(1) | O(n) list / O(log n) tree |
| containsKey(key) | O(1) | O(n) list / O(log n) tree |
| containsValue(value) | O(n) | O(n) — full scan always |
| resize() | O(n) | Rehashes all entries into new array |
| Gotcha | Problem | Fix |
|---|---|---|
| Mutable key | hashCode() changes after insert — key lost in wrong bucket | Only use immutable objects as keys (String, Integer, enums) |
| Missing hashCode() | All instances hash to same bucket → O(n) every lookup | Always override hashCode() when overriding equals() |
| ConcurrentModificationException | Structural change during iteration | Use ConcurrentHashMap or iterate with Iterator.remove() |
| Not thread-safe | Race conditions on concurrent put() | Use ConcurrentHashMap — HashMap is NOT synchronized |
| Initial capacity too small | Frequent resizes degrade performance | Set capacity = expectedSize / loadFactor + 1 |
| LinkedHashMap vs HashMap | HashMap has no iteration order guarantee | Use LinkedHashMap for insertion-order iteration |
| Class | Ordered? | Thread-Safe? | Null Keys | Use When |
|---|---|---|---|---|
| HashMap | No | No | Yes (1) | Default — single-threaded, unordered |
| LinkedHashMap | Insertion order | No | Yes (1) | Need predictable iteration order |
| TreeMap | Sorted by key | No | No | Need sorted keys — uses Red-Black Tree |
| ConcurrentHashMap | No | Yes | No | Multi-threaded access without external locking |
| Hashtable | No | Yes (synchronized) | No | Legacy — prefer ConcurrentHashMap instead |
| EnumMap | Enum order | No | No | Keys are enum constants — extremely fast |
| Concept | Java 8+ Behaviour | Notes |
|---|---|---|
| Locking strategy | Synchronized on individual bucket head (not whole map) | Java 7 used segment locks (16 segments); Java 8 uses per-bin CAS + synchronized |
| Read operations | Lock-free using volatile reads | get() never locks — reads are always concurrent |
| Write operations | CAS for empty bins; synchronized for non-empty | Only the affected bin is locked — high concurrency |
| Null keys/values | Not allowed — throws NullPointerException | Null would be ambiguous with 'key not present' |
| size() accuracy | Approximate — uses distributed LongAdder cells | Use mappingCount() for large maps — returns long not int |
| putIfAbsent / compute | Atomic — safe for counter/accumulator patterns | computeIfAbsent(key, k -> new ArrayList<>()).add(val) |
| Treeification | Same as HashMap — 8 entries → Red-Black Tree | Applies per-bin independently |
| Goal | Formula | Example |
|---|---|---|
| Avoid resize for n entries | initialCapacity = (int)(n / loadFactor) + 1 | 100 entries, LF=0.75 → capacity = 134 |
| Default resize trigger | size > capacity × loadFactor | Default: 16 × 0.75 = 12 entries → resize to 32 |
| Memory per entry (approx) | ~48 bytes (key obj + value obj + Entry node) | 1M entries ≈ 48MB overhead (excluding key/value sizes) |
| Custom load factor trade-off | Lower LF → fewer collisions, more memory | LF=0.5 for read-heavy; LF=0.9 for memory-constrained |
| Power-of-2 capacity | HashMap always rounds up to next power of 2 | new HashMap<>(100) → internal capacity = 128 |