[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":96,"_73":97,"_35":98},"articles",{"_11":12,"_13":14,"_15":16,"_17":16,"_18":19,"_20":21,"_22":23,"_24":23,"_25":16,"_26":27},"content",[30],"pageable",{"_28":21,"_29":19},"totalElements",1,"totalPages","size",10,"number",0,"first",true,"last","numberOfElements","empty",false,"page_number","page_size",{"_31":32,"_33":34,"_35":36,"_37":38,"_11":39,"_40":-5,"_41":23,"_42":27,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":52,"_54":55,"_56":57,"_58":59,"_60":52,"_61":62,"_63":64,"_65":66,"_67":68,"_69":70,"_71":72},"id",108,"title","HashMap: Buckets and Collisions","slug","java-collections-part-12-hashmap-buckets-collisions","excerpt","Journey inside HashMap's O(1) average performance: bucket arrays, hash code transformation, collision handling via chaining, and why power-of-2 capacity matters.","# Java Collections Compendium: Part 12 - HashMap Internals: Buckets & Collisions\n\nHashMap is the workhorse of Java collections—the go-to data structure for key-value storage that powers everything from caching layers to configuration systems. Yet many developers treat it as a black box, unaware of the elegant engineering that enables its O(1) average-case performance.\n\nThis article takes you inside HashMap's implementation: how it transforms hash codes into bucket indices, handles collisions through chaining, and manages capacity through dynamic resizing. Understanding these internals isn't just academic—it's the difference between a HashMap that performs flawlessly and one that degrades to O(n) in production.\n\nWhether you're optimizing a hot code path, debugging mysterious performance issues, or preparing for senior-level interviews, mastering HashMap internals is essential knowledge for any serious Java developer.\n\n## 🎯 At a Glance\n\n**What it is:** HashMap is Java's primary key-value data structure, using hash-based bucket storage for O(1) average-case lookups.\n\n**Key insights:**\n- Keys are converted to bucket indices via `hashCode()` and bitwise operations\n- Collisions are handled by chaining (linked list, tree after threshold)\n- Load factor (0.75) triggers resize at 75% capacity\n- Capacity must be power of 2 for efficient index calculation\n- Never use mutable objects as keys\n\n**Complexity:**\n| Operation | Average | Worst Case |\n|-----------|---------|------------|\n| get(key) | O(1) | O(n)* |\n| put(key, value) | O(1) | O(n)* |\n| remove(key) | O(1) | O(n)* |\n| containsKey | O(1) | O(n)* |\n\n*Worst case with poor hash distribution; O(log n) after treeification (Java 8+)\n\n**One-liner:** HashMap trades memory for speed by using hash codes to directly locate entries in an array of buckets.\n\n### Interactive Visualizer\n\nSee HashMap operations in action - watch how keys are hashed to bucket indices and how collisions are handled through chaining:\n\n```visualizer-hashmap\ncontrols: true\n```\n\n---\n\n## 📋 Prerequisites\n\nBefore reading this article, you should understand:\n- **Part 3: equals() & hashCode() Contract** - Critical for understanding how HashMap finds entries\n- **Basic Java generics** - HashMap uses generic types\n- **Big O notation** - To understand performance characteristics\n\n---\n\n## 📘 Introduction\n\n### 🔥 The Black Friday Incident\n\n**\"Black Friday, 2019. Our e-commerce search service ground to a halt. Response times jumped from 5ms to 45 seconds. The culprit? A HashMap with 2 million product entries—all landing in the same bucket.\"**\n\nOur product catalog used a custom `ProductKey` class as HashMap keys. The developer had overridden `equals()` but forgot `hashCode()`. Every single key returned the default identity hash from `Object.hashCode()`, which happened to collide spectacularly due to our JVM configuration.\n\nTwo million entries. One bucket. A linked list 2 million nodes long.\n\nThat day, I learned that HashMap's O(1) promise is a contract—and like any contract, it requires both parties to uphold their end. HashMap provides the infrastructure; you provide proper hash codes.\n\n### 🌍 Why HashMap Internals Matter\n\nHashMap is everywhere in Java applications:\n- **Caching layers** - In-memory caches, session stores\n- **Configuration** - Properties, feature flags\n- **Data processing** - Grouping, deduplication, lookups\n- **Framework internals** - Spring beans, Hibernate caches\n\nUnderstanding its internals helps you:\n- **Avoid performance pitfalls** - Proper capacity planning, key design\n- **Debug production issues** - Recognize symptoms of hash collision problems\n- **Make informed decisions** - When to use HashMap vs TreeMap vs LinkedHashMap\n- **Ace interviews** - HashMap internals is a top-10 Java interview topic\n\n## 🎯 What You'll Learn\n\n1. **Bucket array structure** - How entries are stored and located\n2. **Hash function internals** - How hashCode() becomes a bucket index\n3. **Collision handling** - Chaining strategy and its implications\n4. **Load factor & resizing** - When and how HashMap grows\n5. **Capacity planning** - Choosing the right initial capacity\n6. **Key design principles** - Creating hash-friendly keys\n\n---\n\n## 🧠 Mental Model\n\n### Think of HashMap as a Library with Numbered Shelves\n\nImagine a library where books are stored on numbered shelves (buckets):\n\n```text\n┌─────────────────────────────────────────────────────────────────────────┐\n│ HASHMAP LIBRARY │\n├─────────────────────────────────────────────────────────────────────────┤\n│ Shelf 0 │ [empty] │\n│ Shelf 1 │ [Book: ISBN-1001 → \"Java Basics\"] │\n│ Shelf 2 │ [empty] │\n│ Shelf 3 │ [Book: ISBN-3045 → \"Spring\"] → [ISBN-3189 → \"JPA\"] ←collision│\n│ Shelf 4 │ [empty] │\n│ Shelf 5 │ [Book: ISBN-5002 → \"Kotlin Guide\"] │\n│ ... │ │\n│ Shelf 15 │ [Book: ISBN-1523 → \"Clean Code\"] │\n└─────────────────────────────────────────────────────────────────────────┘\n\nTo find a book:\n1. Take ISBN (key) → compute shelf number (hash → index)\n2. Go to that shelf\n3. If multiple books on shelf → scan through them (collision chain)\n```\n\n### The Core Algorithm\n\n```text\nPUT operation:\n1. hash = key.hashCode()\n2. index = hash & (capacity - 1) // Fast modulo for power-of-2\n3. Go to table[index]\n4. If empty → create new entry\n5. If occupied → walk the chain, check equals()\n - If key exists → update value\n - If key not found → add to chain\n\nGET operation:\n1. hash = key.hashCode()\n2. index = hash & (capacity - 1)\n3. Go to table[index]\n4. Walk the chain, check equals() for each entry\n5. Return value if found, null if not\n```\n\n### Visual: HashMap Memory Layout\n\n```text\nHashMap object\n┌──────────────────────────────────┐\n│ table: Node[] │──→ Bucket Array\n│ size: 5 │ ┌───┬───┬───┬───┬───┬───┐\n│ threshold: 12 │ │ 0 │ 1 │ 2 │ 3 │...│15 │\n│ loadFactor: 0.75 │ └─┬─┴─┬─┴───┴─┬─┴───┴───┘\n└──────────────────────────────────┘ │ │ │\n ↓ ↓ ↓\n null ┌───┐ ┌───┐\n │ A │ │ C │\n └─┬─┘ └─┬─┘\n ↓ ↓\n ┌───┐ ┌───┐\n │ B │ │ D │\n └───┘ └─┬─┘\n ↓\n ┌───┐\n │ E │ (collision chain)\n └───┘\n\nNode structure:\n┌─────────────────────────┐\n│ hash: int (cached) │\n│ key: K │\n│ value: V │\n│ next: Node │──→ next node in chain (or null)\n└─────────────────────────┘\n```\n\n**Key insight:** Good hash distribution = entries spread evenly = short chains = fast lookups.\n\n---\n\n## 🔬 Deep Dive\n\n### 1. The Bucket Array\n\nAt the heart of HashMap lies a simple array:\n\n```java\n// ✅ Internal structure (simplified from JDK source)\ntransient Node[] table;\n\nstatic class Node implements Map.Entry {\n final int hash; // ✅ Cached hash - avoid recomputation\n final K key; // ✅ Final - keys should be immutable\n V value;\n Node next; // ✅ Link to next node (collision chain)\n\n Node(int hash, K key, V value, Node next) {\n this.hash = hash;\n this.key = key;\n this.value = value;\n this.next = next;\n }\n}\n```\n\n**Why cache the hash?**\n- Hash is computed once during `put()`\n- Reused during `get()`, `remove()`, and resize operations\n- Comparing hashes is faster than comparing keys (especially for Strings)\n\n### 2. The Hash Function\n\nHashMap doesn't use `hashCode()` directly. It applies additional mixing:\n\n```java\n// ✅ JDK hash function\nstatic final int hash(Object key) {\n int h;\n return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);\n}\n```\n\n**Why XOR with upper bits?**\n\n```text\nOriginal hashCode: 1010 1100 0011 0101 | 0000 0000 0000 1111\n ─────────────────────────────────────────\n upper 16 bits | lower 16 bits\n\nShift right 16: 0000 0000 0000 0000 | 1010 1100 0011 0101\n\nXOR result: 1010 1100 0011 0101 | 1010 1100 0011 1010\n ↑ lower bits now contain\n information from upper bits\n```\n\n**Problem solved:** When capacity is small (e.g., 16), only lower bits determine the bucket index. If many keys differ only in upper bits, they'd all collide. XOR spreads that entropy.\n\n### 3. Index Calculation\n\n```java\n// ✅ How bucket index is calculated\nint index = hash & (capacity - 1); // Equivalent to: hash % capacity\n```\n\n**Why bitwise AND instead of modulo?**\n\n```text\ncapacity = 16 (binary: 10000)\ncapacity - 1 = 15 (binary: 01111)\n\nhash = 12345678\nhash & 15 = 12345678 & 00001111 = 00001110 = 14\n\n// Bitwise AND is 1 CPU cycle\n// Modulo (%) requires division - many cycles\n```\n\n**Why capacity must be power of 2:**\n\n```text\ncapacity = 16: capacity - 1 = 15 = 01111 ✅ All lower bits set\ncapacity = 17: capacity - 1 = 16 = 10000 ❌ Only one bit set - bad distribution!\n\nWith capacity=17, only entries with hash ending in 10000 go to bucket 16.\nEverything else goes to buckets 0-15 unevenly.\n```\n\n### 4. Collision Resolution: Chaining\n\nWhen two keys map to the same bucket, HashMap chains them:\n\n```java\n// ✅ Simplified put() logic\nfinal V putVal(int hash, K key, V value) {\n Node[] tab = table;\n int n = tab.length;\n int i = (n - 1) & hash; // Calculate bucket index\n\n Node p = tab[i];\n\n if (p == null) {\n // ✅ Bucket empty - create first node\n tab[i] = new Node<>(hash, key, value, null);\n } else {\n // ❌ Bucket occupied - must handle collision\n Node e;\n\n if (p.hash == hash &&\n (p.key == key || (key != null && key.equals(p.key)))) {\n // ✅ Key already exists at head - will update\n e = p;\n } else {\n // Walk the chain looking for key\n for (int binCount = 0; ; ++binCount) {\n if ((e = p.next) == null) {\n // ✅ Key not found - add to end of chain\n p.next = new Node<>(hash, key, value, null);\n break;\n }\n if (e.hash == hash &&\n (e.key == key || (key != null && key.equals(e.key)))) {\n // ✅ Found key in chain - will update\n break;\n }\n p = e;\n }\n }\n\n if (e != null) {\n // ✅ Update existing value\n V oldValue = e.value;\n e.value = value;\n return oldValue;\n }\n }\n\n size++;\n if (size > threshold) {\n resize(); // ❌ Expensive operation!\n }\n return null;\n}\n```\n\n**Performance implication:**\n- **Empty bucket:** O(1) - direct array access\n- **Chain of length n:** O(n) - must traverse the chain\n- **This is why hash distribution matters!**\n\n### 5. Load Factor and Threshold\n\n```java\n// ✅ Key fields\nfloat loadFactor = 0.75f; // Default load factor\nint threshold = capacity * loadFactor; // Resize when size > threshold\n\n// With default capacity 16:\n// threshold = 16 * 0.75 = 12\n// Resize triggers when adding 13th element\n```\n\n**Why 0.75?**\n\n| Load Factor | Trade-off |\n|-------------|-----------|\n| 0.5 | More memory, fewer collisions, faster |\n| 0.75 | Balanced (default) |\n| 1.0 | Less memory, more collisions, slower |\n\nThe value 0.75 is based on statistical analysis - it provides a good balance between space efficiency and collision probability.\n\n### 6. Resize Operation\n\nWhen size exceeds threshold, HashMap doubles its capacity:\n\n```java\n// ✅ Simplified resize() logic\nfinal Node[] resize() {\n Node[] oldTab = table;\n int oldCap = oldTab.length; // e.g., 16\n int newCap = oldCap << 1; // Double: 32\n int newThr = newCap * loadFactor; // New threshold: 24\n\n Node[] newTab = new Node[newCap];\n\n // ❌ Must rehash ALL entries - O(n) operation!\n for (int j = 0; j < oldCap; ++j) {\n Node e = oldTab[j];\n if (e != null) {\n // Rehash: recalculate index for new capacity\n // Some entries stay, some move to (old_index + oldCap)\n // ... (clever bit manipulation in actual JDK)\n }\n }\n\n table = newTab;\n threshold = newThr;\n return newTab;\n}\n```\n\n**Resize is expensive:**\n- Allocates new array (2x size)\n- Rehashes every single entry\n- Causes GC pressure\n- Can cause latency spikes in production\n\n**Visual: How entries are redistributed**\n\n```text\nOld capacity: 8 (mask: 0111)\nNew capacity: 16 (mask: 1111)\n\nEntry with hash = 13 (binary: 1101)\n- Old index: 1101 & 0111 = 0101 = 5\n- New index: 1101 & 1111 = 1101 = 13 ← moved to index 5 + 8\n\nEntry with hash = 5 (binary: 0101)\n- Old index: 0101 & 0111 = 0101 = 5\n- New index: 0101 & 1111 = 0101 = 5 ← stays at index 5\n\nRule: If bit at position oldCap is 0 → stays, if 1 → moves to old_index + oldCap\n```\n\n### 7. Initial Capacity Planning\n\n```java\n// ❌ BAD: Default capacity for large dataset\nMap users = new HashMap<>(); // capacity 16\nfor (int i = 0; i < 1_000_000; i++) {\n users.put(userId, user); // 💥 ~20 resizes!\n}\n\n// ✅ GOOD: Pre-sized capacity\n// Formula: expected_size / load_factor + 1\nint expectedSize = 1_000_000;\nint capacity = (int) (expectedSize / 0.75) + 1; // ~1,333,334\nMap users = new HashMap<>(capacity);\n```\n\n**Resize cascade with default capacity:**\n\n```text\nSize → Capacity → Resizes needed\n16 → 16 → 0\n17 → 32 → 1 (at 13 elements)\n33 → 64 → 2 (at 25 elements)\n...\n1M → 2^21 → ~20 resizes\n```\n\nEach resize:\n- Allocates new array\n- Copies all entries\n- Causes GC pressure\n- Increases latency\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: Mutable Keys\n\n❌ **Problem:**\n```java\nList key = new ArrayList<>();\nkey.add(\"hello\");\n\nMap, String> map = new HashMap<>();\nmap.put(key, \"world\");\n\nkey.add(\"modified\"); // 💥 hashCode changed!\n\nmap.get(key); // Returns null - entry is \"lost\"!\nmap.containsKey(key); // Returns false!\n\n// The entry still exists, but we can never find it again\n// because it's in the wrong bucket now\n```\n\n✅ **Solution:**\n```java\n// Use immutable keys\nrecord PersonKey(String name, int id) {} // ✅ Immutable by default\n\nMap map = new HashMap<>();\nmap.put(new PersonKey(\"John\", 1), person);\n\n// Or use immutable collections\nMap, String> map = new HashMap<>();\nmap.put(List.of(\"hello\"), \"world\"); // ✅ Immutable list\n```\n\n**Why:** HashMap stores entries based on `hashCode()`. If key mutates, its hash changes, but the entry stays in the old bucket. It becomes invisible to lookups.\n\n---\n\n### Mistake 2: Missing hashCode() Override\n\n❌ **Problem:**\n```java\nclass Product {\n private String sku;\n private String name;\n\n @Override\n public boolean equals(Object o) {\n if (this == o) return true;\n if (!(o instanceof Product)) return false;\n Product product = (Product) o;\n return Objects.equals(sku, product.sku);\n }\n\n // ❌ Forgot to override hashCode()!\n}\n\nMap inventory = new HashMap<>();\ninventory.put(new Product(\"SKU-001\", \"Widget\"), 100);\n\n// Later...\nProduct lookup = new Product(\"SKU-001\", \"Widget\");\ninventory.get(lookup); // 💥 Returns null!\n\n// Both products are equals(), but have different hashCodes\n// so they're in different buckets\n```\n\n✅ **Solution:**\n```java\nclass Product {\n private String sku;\n private String name;\n\n @Override\n public boolean equals(Object o) {\n if (this == o) return true;\n if (!(o instanceof Product)) return false;\n Product product = (Product) o;\n return Objects.equals(sku, product.sku);\n }\n\n @Override\n public int hashCode() {\n return Objects.hash(sku); // ✅ Consistent with equals\n }\n}\n```\n\n**Rule:** If two objects are `equals()`, they MUST have the same `hashCode()`.\n\n---\n\n### Mistake 3: Ignoring Initial Capacity\n\n❌ **Problem:**\n```java\n// Processing 1 million users\nMap cache = new HashMap<>(); // Default: 16\n\nfor (User user : users) { // 1,000,000 users\n cache.put(user.getId(), userData);\n // 💥 Triggers ~20 resizes\n // Each resize: allocate new array, rehash everything\n // Total: ~40 million entry moves!\n}\n```\n\n✅ **Solution:**\n```java\n// Pre-calculate capacity\nint expectedSize = 1_000_000;\nint initialCapacity = (int) (expectedSize / 0.75f) + 1;\n\nMap cache = new HashMap<>(initialCapacity);\n\n// Or use Guava's helper\nMap cache = Maps.newHashMapWithExpectedSize(1_000_000);\n```\n\n**Impact:**\n- Avoids resize overhead\n- Reduces GC pressure\n- Prevents latency spikes\n- Memory is allocated upfront (predictable)\n\n---\n\n### Mistake 4: Modifying Map During Iteration\n\n❌ **Problem:**\n```java\nMap scores = new HashMap<>();\nscores.put(\"Alice\", 100);\nscores.put(\"Bob\", 50);\nscores.put(\"Charlie\", 75);\n\nfor (String name : scores.keySet()) {\n if (scores.get(name) < 60) {\n scores.remove(name); // 💥 ConcurrentModificationException!\n }\n}\n```\n\n✅ **Solution 1: Use Iterator.remove()**\n```java\nIterator> it = scores.entrySet().iterator();\nwhile (it.hasNext()) {\n Map.Entry entry = it.next();\n if (entry.getValue() < 60) {\n it.remove(); // ✅ Safe removal\n }\n}\n```\n\n✅ **Solution 2: Use removeIf() (Java 8+)**\n```java\nscores.entrySet().removeIf(entry -> entry.getValue() < 60); // ✅ Clean\n```\n\n✅ **Solution 3: Collect and remove**\n```java\nList toRemove = scores.entrySet().stream()\n .filter(e -> e.getValue() < 60)\n .map(Map.Entry::getKey)\n .collect(Collectors.toList());\n\ntoRemove.forEach(scores::remove); // ✅ Safe, but extra memory\n```\n\n---\n\n### Mistake 5: Using HashMap in Multi-threaded Code\n\n❌ **Problem:**\n```java\n// Shared HashMap without synchronization\nMap sessions = new HashMap<>();\n\n// Thread 1\nsessions.put(sessionId1, session1);\n\n// Thread 2 (concurrent)\nsessions.put(sessionId2, session2);\n\n// 💥 Possible outcomes:\n// - Infinite loop during resize (threads see inconsistent state)\n// - Lost updates (one put overwrites another)\n// - Corrupted internal structure\n// - Random NullPointerException later\n```\n\n✅ **Solution:**\n```java\n// Option 1: ConcurrentHashMap (recommended)\nMap sessions = new ConcurrentHashMap<>();\n\n// Option 2: Synchronized wrapper (less performant)\nMap sessions = Collections.synchronizedMap(new HashMap<>());\n\n// Option 3: Lock manually (not recommended, error-prone)\nprivate final Map sessions = new HashMap<>();\nprivate final ReadWriteLock lock = new ReentrantReadWriteLock();\n\npublic void addSession(String id, Session session) {\n lock.writeLock().lock();\n try {\n sessions.put(id, session);\n } finally {\n lock.writeLock().unlock();\n }\n}\n```\n\n---\n\n## 🐛 Debug This\n\nFind the bug in this code:\n\n```java\npublic class UserCache {\n private final Map cache = new HashMap<>();\n\n public void cacheProfile(User user, UserProfile profile) {\n cache.put(user, profile);\n }\n\n public UserProfile getProfile(User user) {\n return cache.get(user);\n }\n}\n\nclass User {\n private String id;\n private String email;\n private LocalDateTime lastLogin; // Updated on every login\n\n public void updateLastLogin() {\n this.lastLogin = LocalDateTime.now();\n }\n\n @Override\n public boolean equals(Object o) {\n if (this == o) return true;\n if (!(o instanceof User)) return false;\n User user = (User) o;\n return Objects.equals(id, user.id) &&\n Objects.equals(email, user.email) &&\n Objects.equals(lastLogin, user.lastLogin);\n }\n\n @Override\n public int hashCode() {\n return Objects.hash(id, email, lastLogin);\n }\n}\n```\n\n**🔍 Hint:** What happens to the hash code when `lastLogin` changes?\n\n**✅ Solution:**\n\n**The Bug:** `lastLogin` is mutable and included in `equals()` and `hashCode()`.\n\nWhen a user logs in and `updateLastLogin()` is called:\n1. The `User` object's `hashCode()` changes\n2. The entry is now in the wrong bucket\n3. `cache.get(user)` looks in the new bucket (based on new hash)\n4. Entry is never found - it's still in the old bucket\n\n**The Fix:**\n\n```java\nclass User {\n private String id;\n private String email;\n private LocalDateTime lastLogin; // Mutable, not part of identity\n\n @Override\n public boolean equals(Object o) {\n if (this == o) return true;\n if (!(o instanceof User)) return false;\n User user = (User) o;\n // ✅ Only use immutable identity fields\n return Objects.equals(id, user.id);\n }\n\n @Override\n public int hashCode() {\n // ✅ Only use immutable identity fields\n return Objects.hash(id);\n }\n}\n```\n\n**Rule:** Only include immutable, identity-defining fields in `equals()` and `hashCode()`.\n\n---\n\n## 💻 Practical Exercises\n\n### Exercise 1: Basic HashMap Operations\n⭐ Difficulty: Easy | ⏱️ Time: 10 minutes\n\n**Task:** Implement a word frequency counter.\n\n```java\npublic Map countWords(String text) {\n // Split text by whitespace, count occurrences of each word\n // Return map of word -> count\n // Handle case-insensitivity (convert to lowercase)\n}\n```\n\n**Test:**\n```java\nString text = \"The quick brown fox jumps over the lazy dog the\";\nMap counts = countWords(text);\nassert counts.get(\"the\") == 3;\nassert counts.get(\"quick\") == 1;\n```\n\n**✅ Solution:**\n\n```java\npublic Map countWords(String text) {\n Map counts = new HashMap<>();\n\n for (String word : text.toLowerCase().split(\"\\\\s+\")) {\n counts.merge(word, 1, Integer::sum);\n // Equivalent to:\n // counts.put(word, counts.getOrDefault(word, 0) + 1);\n }\n\n return counts;\n}\n```\n\n---\n\n### Exercise 2: Proper Initial Capacity\n⭐⭐ Difficulty: Easy-Medium | ⏱️ Time: 15 minutes\n\n**Task:** Create a HashMap that will hold exactly 10,000 entries without ever resizing.\n\n```java\npublic Map createOptimalMap() {\n // Return a HashMap with the correct initial capacity\n // to hold 10,000 entries without resizing\n}\n```\n\n**Requirements:**\n- Calculate the minimum initial capacity needed\n- Verify no resize occurs when adding 10,000 entries\n\n**✅ Solution:**\n\n```java\npublic Map createOptimalMap() {\n // Required capacity = expected_size / load_factor\n // 10000 / 0.75 = 13333.33...\n // Round up and add 1 for safety: 13334\n\n // But HashMap rounds to next power of 2: 16384 (2^14)\n // So we can just specify 13334, or directly 16384\n\n int expectedSize = 10_000;\n int capacity = (int) Math.ceil(expectedSize / 0.75) + 1;\n\n return new HashMap<>(capacity); // Will be sized to 16384\n}\n\n// Verification\npublic void verify() {\n Map map = createOptimalMap();\n\n // Use reflection to check internal capacity\n Field tableField = HashMap.class.getDeclaredField(\"table\");\n tableField.setAccessible(true);\n\n // Add 10,000 entries\n for (int i = 0; i < 10_000; i++) {\n map.put(i, \"value\" + i);\n }\n\n Object[] table = (Object[]) tableField.get(map);\n System.out.println(\"Final capacity: \" + table.length); // 16384\n // No resize occurred - capacity was sufficient from start\n}\n```\n\n---\n\n### Exercise 3: Custom Key with Proper Contract\n⭐⭐⭐ Difficulty: Medium | ⏱️ Time: 20 minutes\n\n**Task:** Implement a `CompositeKey` class that can be safely used as a HashMap key.\n\n```java\npublic class CompositeKey {\n private final String namespace;\n private final String name;\n private final int version;\n\n // Implement constructor, equals, hashCode\n // Ensure it's safe to use as a HashMap key\n}\n```\n\n**Requirements:**\n- Two keys are equal if namespace, name, AND version match\n- Must be immutable\n- Must work correctly in HashMap\n\n**✅ Solution:**\n\n```java\npublic final class CompositeKey {\n private final String namespace;\n private final String name;\n private final int version;\n\n public CompositeKey(String namespace, String name, int version) {\n this.namespace = Objects.requireNonNull(namespace, \"namespace cannot be null\");\n this.name = Objects.requireNonNull(name, \"name cannot be null\");\n this.version = version;\n }\n\n @Override\n public boolean equals(Object o) {\n if (this == o) return true;\n if (!(o instanceof CompositeKey)) return false;\n CompositeKey that = (CompositeKey) o;\n return version == that.version &&\n namespace.equals(that.namespace) &&\n name.equals(that.name);\n }\n\n @Override\n public int hashCode() {\n // Use prime multiplier for better distribution\n int result = namespace.hashCode();\n result = 31 * result + name.hashCode();\n result = 31 * result + version;\n return result;\n\n // Or simply: return Objects.hash(namespace, name, version);\n }\n\n @Override\n public String toString() {\n return namespace + \":\" + name + \"@\" + version;\n }\n\n // Getters only - no setters (immutable)\n public String getNamespace() { return namespace; }\n public String getName() { return name; }\n public int getVersion() { return version; }\n}\n\n// Better alternative in Java 16+:\npublic record CompositeKey(String namespace, String name, int version) {\n public CompositeKey {\n Objects.requireNonNull(namespace, \"namespace cannot be null\");\n Objects.requireNonNull(name, \"name cannot be null\");\n }\n}\n```\n\n---\n\n### Exercise 4: Diagnose Hash Distribution\n⭐⭐⭐⭐ Difficulty: Medium-Hard | ⏱️ Time: 25 minutes\n\n**Task:** Write a utility to analyze hash distribution in a HashMap.\n\n```java\npublic class HashMapAnalyzer {\n\n public static DistributionReport analyze(Map map) {\n // Return statistics about the bucket distribution:\n // - Number of empty buckets\n // - Number of collision buckets (>1 entry)\n // - Maximum chain length\n // - Average chain length (for non-empty buckets)\n }\n\n public record DistributionReport(\n int totalBuckets,\n int emptyBuckets,\n int collisionBuckets,\n int maxChainLength,\n double avgChainLength\n ) {}\n}\n```\n\n**✅ Solution:**\n\n```java\npublic class HashMapAnalyzer {\n\n @SuppressWarnings(\"unchecked\")\n public static DistributionReport analyze(Map map) {\n if (!(map instanceof HashMap)) {\n throw new IllegalArgumentException(\"Only HashMap supported\");\n }\n\n try {\n Field tableField = HashMap.class.getDeclaredField(\"table\");\n tableField.setAccessible(true);\n Object[] table = (Object[]) tableField.get(map);\n\n if (table == null) {\n return new DistributionReport(0, 0, 0, 0, 0.0);\n }\n\n int totalBuckets = table.length;\n int emptyBuckets = 0;\n int collisionBuckets = 0;\n int maxChainLength = 0;\n int totalChainLength = 0;\n int nonEmptyBuckets = 0;\n\n Field nextField = null;\n\n for (Object bucket : table) {\n if (bucket == null) {\n emptyBuckets++;\n } else {\n nonEmptyBuckets++;\n int chainLength = 1;\n\n // Walk the chain\n if (nextField == null) {\n nextField = bucket.getClass().getDeclaredField(\"next\");\n nextField.setAccessible(true);\n }\n\n Object node = bucket;\n while ((node = nextField.get(node)) != null) {\n chainLength++;\n }\n\n if (chainLength > 1) {\n collisionBuckets++;\n }\n\n maxChainLength = Math.max(maxChainLength, chainLength);\n totalChainLength += chainLength;\n }\n }\n\n double avgChainLength = nonEmptyBuckets > 0\n ? (double) totalChainLength / nonEmptyBuckets\n : 0.0;\n\n return new DistributionReport(\n totalBuckets,\n emptyBuckets,\n collisionBuckets,\n maxChainLength,\n avgChainLength\n );\n\n } catch (Exception e) {\n throw new RuntimeException(\"Failed to analyze HashMap\", e);\n }\n }\n\n public record DistributionReport(\n int totalBuckets,\n int emptyBuckets,\n int collisionBuckets,\n int maxChainLength,\n double avgChainLength\n ) {\n @Override\n public String toString() {\n return String.format(\n \"Buckets: %d (empty: %d, collisions: %d), \" +\n \"Max chain: %d, Avg chain: %.2f\",\n totalBuckets, emptyBuckets, collisionBuckets,\n maxChainLength, avgChainLength\n );\n }\n }\n}\n```\n\n---\n\n### Exercise 5: LRU Cache Foundation\n⭐⭐⭐⭐⭐ Difficulty: Hard | ⏱️ Time: 30 minutes\n\n**Task:** Implement a simple LRU (Least Recently Used) cache using HashMap + custom doubly-linked list.\n\n```java\npublic class LRUCache {\n private final int capacity;\n\n public LRUCache(int capacity) {\n this.capacity = capacity;\n }\n\n public V get(K key) {\n // Return value if exists, mark as recently used\n // Return null if not exists\n }\n\n public void put(K key, V value) {\n // Add or update entry\n // If at capacity, evict least recently used entry\n }\n}\n```\n\n**Requirements:**\n- Both get() and put() should be O(1)\n- Most recently used items should not be evicted\n- Least recently used items should be evicted first\n\n**✅ Solution:**\n\n```java\npublic class LRUCache {\n private final int capacity;\n private final Map> cache;\n private final Node head; // Dummy head (most recent)\n private final Node tail; // Dummy tail (least recent)\n\n private static class Node {\n K key;\n V value;\n Node prev;\n Node next;\n\n Node(K key, V value) {\n this.key = key;\n this.value = value;\n }\n }\n\n public LRUCache(int capacity) {\n this.capacity = capacity;\n this.cache = new HashMap<>(capacity);\n\n // Initialize dummy head and tail\n this.head = new Node<>(null, null);\n this.tail = new Node<>(null, null);\n head.next = tail;\n tail.prev = head;\n }\n\n public V get(K key) {\n Node node = cache.get(key);\n if (node == null) {\n return null;\n }\n\n // Move to front (most recently used)\n moveToFront(node);\n return node.value;\n }\n\n public void put(K key, V value) {\n Node existing = cache.get(key);\n\n if (existing != null) {\n // Update existing\n existing.value = value;\n moveToFront(existing);\n } else {\n // Add new\n Node newNode = new Node<>(key, value);\n cache.put(key, newNode);\n addToFront(newNode);\n\n // Evict if over capacity\n if (cache.size() > capacity) {\n Node lru = removeLast();\n cache.remove(lru.key);\n }\n }\n }\n\n private void moveToFront(Node node) {\n removeNode(node);\n addToFront(node);\n }\n\n private void addToFront(Node node) {\n node.next = head.next;\n node.prev = head;\n head.next.prev = node;\n head.next = node;\n }\n\n private void removeNode(Node node) {\n node.prev.next = node.next;\n node.next.prev = node.prev;\n }\n\n private Node removeLast() {\n Node last = tail.prev;\n removeNode(last);\n return last;\n }\n}\n\n// Note: In practice, use LinkedHashMap with accessOrder=true\n// This exercise is to understand the underlying mechanics\n```\n\n---\n\n## 📝 Summary & Key Takeaways\n\n### What We Covered\n\n1. **Bucket Array Structure** - HashMap uses a `Node[]` array where entries are stored based on their hash code\n2. **Hash Function** - Keys are hashed using `hashCode() ^ (hashCode >>> 16)` to spread entropy across all bits\n3. **Index Calculation** - Bucket index is computed as `hash & (capacity - 1)`, requiring power-of-2 capacity\n4. **Collision Handling** - Collisions are resolved by chaining entries in linked lists (trees after threshold)\n5. **Load Factor (0.75)** - HashMap resizes when size exceeds `capacity × loadFactor`\n6. **Capacity Planning** - Pre-sizing with `expectedSize / 0.75 + 1` avoids expensive resize operations\n\n### 🎯 Production Checklist\n\n- [ ] Use immutable objects as keys (String, Integer, records)\n- [ ] Always override both `equals()` and `hashCode()` together\n- [ ] Pre-size HashMap when expected size is known: `new HashMap<>(expectedSize / 0.75 + 1)`\n- [ ] Use `ConcurrentHashMap` for multi-threaded access\n- [ ] Use `computeIfAbsent()` for lazy initialization patterns\n- [ ] Use `merge()` for counting/aggregation patterns\n- [ ] Never modify keys after putting them in the map\n- [ ] Use `removeIf()` or `Iterator.remove()` for safe removal during iteration\n\n### 📊 Key Numbers to Remember\n\n| Metric | Value | Why It Matters |\n|--------|-------|----------------|\n| Default capacity | 16 | Starting bucket array size |\n| Default load factor | 0.75 | Resize threshold |\n| Treeify threshold | 8 | Chain length to convert to tree |\n| Min treeify capacity | 64 | Minimum capacity for treeification |\n\n---\n\n## 🎤 Senior-Level Interview Questions\n\n### Question 1: How does HashMap calculate the bucket index from a key?\n\n**Answer:**\n\nHashMap uses a two-step process:\n\n1. **Hash the key:** `hash = key.hashCode() ^ (key.hashCode() >>> 16)`\n - XORs upper 16 bits with lower 16 bits to spread entropy\n\n2. **Calculate index:** `index = hash & (capacity - 1)`\n - Bitwise AND with (capacity - 1) is equivalent to modulo\n - Works because capacity is always a power of 2\n\n**Why this matters:** The XOR step ensures that keys differing only in upper bits don't all collide. The bitwise AND is faster than modulo operation.\n\n---\n\n### Question 2: What happens when two different keys have the same hash code?\n\n**Answer:**\n\nThis is called a **hash collision**. HashMap handles it through **chaining**:\n\n1. Both entries go to the same bucket\n2. They form a linked list within that bucket\n3. On lookup, HashMap walks the chain, comparing each key with `equals()`\n4. In Java 8+, if chain exceeds 8 nodes and capacity ≥ 64, it converts to a red-black tree (O(log n) instead of O(n))\n\n**Performance impact:** Collisions degrade performance from O(1) to O(n) for linked lists, or O(log n) for trees.\n\n---\n\n### Question 3: Why must HashMap capacity be a power of 2?\n\n**Answer:**\n\nFor efficient index calculation using bitwise AND instead of modulo:\n\n```java\nindex = hash & (capacity - 1) // Only works for power-of-2 capacity\n```\n\nWhen capacity is a power of 2 (e.g., 16), `capacity - 1` is all 1s in binary (e.g., 15 = 1111). This makes `hash & (capacity - 1)` equivalent to `hash % capacity`, but much faster.\n\n**Additional benefit:** During resize (doubling capacity), each entry either stays in the same bucket or moves to `old_index + old_capacity`. This can be determined by checking a single bit.\n\n---\n\n### Question 4: What is the default load factor and why was 0.75 chosen?\n\n**Answer:**\n\nThe default load factor is **0.75**.\n\n**Trade-offs:**\n- **Lower (e.g., 0.5):** Fewer collisions, more memory usage, faster operations\n- **Higher (e.g., 1.0):** More collisions, less memory usage, slower operations\n- **0.75:** Balanced trade-off between time and space\n\n**Statistical basis:** With random hash distribution, 0.75 keeps the average chain length around 0.5-1.0 nodes, which provides near-O(1) performance while using memory efficiently.\n\n---\n\n### Question 5: What happens if you use a mutable object as a HashMap key and then modify it?\n\n**Answer:**\n\nThe entry becomes **unreachable** (\"lost\"):\n\n1. Entry is stored in bucket based on original `hashCode()`\n2. When object is mutated, `hashCode()` changes\n3. `get()` calculates new hash, looks in different bucket\n4. Entry is never found, even though it still exists\n\n**This causes:**\n- Memory leaks (entry never garbage collected)\n- Incorrect `containsKey()` results\n- Silently failing lookups\n\n**Prevention:**\n- Use immutable keys (String, Integer, records)\n- Only include immutable fields in `equals()` and `hashCode()`\n\n---\n\n### Question 6: How would you diagnose a HashMap performance problem in production?\n\n**Answer:**\n\n**Symptoms to look for:**\n- Slow `get()`/`put()` operations\n- High CPU usage in HashMap methods\n- Thread contention (if incorrectly shared)\n\n**Diagnostic steps:**\n\n1. **Check key distribution:**\n ```java\n // Are many entries in the same bucket?\n // Use profiler or custom analyzer to check chain lengths\n ```\n\n2. **Verify equals/hashCode contract:**\n - Are both overridden?\n - Do equal objects have same hashCode?\n - Are keys mutable?\n\n3. **Check initial capacity:**\n - Is the map resizing frequently?\n - What's the current capacity vs size?\n\n4. **Monitor for concurrency issues:**\n - Is HashMap shared between threads without synchronization?\n - Look for infinite loops, corrupted state\n\n**Quick fix checklist:**\n- Set appropriate initial capacity\n- Use ConcurrentHashMap for shared access\n- Ensure proper equals/hashCode implementation\n- Use immutable keys\n\n---\n\n## 📋 Quick Reference\n\n### When to Use HashMap\n\n✅ **Use when:**\n- Need fast O(1) key-value lookups\n- Keys have good hash distribution\n- Iteration order doesn't matter\n- Single-threaded access (or using ConcurrentHashMap)\n\n❌ **Don't use when:**\n- Need sorted keys → use `TreeMap`\n- Need insertion order → use `LinkedHashMap`\n- Need thread-safety → use `ConcurrentHashMap`\n- Keys are enums → use `EnumMap` (faster)\n\n### Complexity Table\n\n| Operation | Average | Worst Case |\n|-----------|---------|------------|\n| put(key, value) | O(1) | O(n) / O(log n)* |\n| get(key) | O(1) | O(n) / O(log n)* |\n| remove(key) | O(1) | O(n) / O(log n)* |\n| containsKey(key) | O(1) | O(n) / O(log n)* |\n| containsValue(value) | O(n) | O(n) |\n| size() | O(1) | O(1) |\n| isEmpty() | O(1) | O(1) |\n| iteration | O(n + capacity) | O(n + capacity) |\n\n*O(log n) after treeification in Java 8+\n\n### Key Configuration\n\n| Parameter | Default | Purpose |\n|-----------|---------|---------|\n| Initial capacity | 16 | Starting bucket array size |\n| Load factor | 0.75 | Resize threshold = capacity × loadFactor |\n| Treeify threshold | 8 | Chain length to convert to tree |\n| Untreeify threshold | 6 | Tree size to convert back to list |\n| Min treeify capacity | 64 | Minimum capacity before treeification |\n\n### Capacity Formula\n\n```java\n// For expected size n, to avoid all resizing:\nint capacity = (int) (expectedSize / 0.75f) + 1;\n\n// HashMap will round up to next power of 2\nMap map = new HashMap<>(capacity);\n```\n\n### Null Handling\n\n| Key | Value |\n|-----|-------|\n| ✅ One null key allowed | ✅ Multiple null values allowed |\n\n### Common Patterns\n\n```java\n// Get with default\nV value = map.getOrDefault(key, defaultValue);\n\n// Put if absent\nmap.putIfAbsent(key, value);\n\n// Compute if absent (lazy)\nmap.computeIfAbsent(key, k -> expensiveComputation(k));\n\n// Merge values\nmap.merge(key, 1, Integer::sum); // Increment counter\n\n// Safe iteration with modification\nmap.entrySet().removeIf(e -> e.getValue() == null);\n```\n\n---\n\n## 🏁 Conclusion\n\nHashMap's elegance lies in its simplicity: convert a key to a number, use that number to find a bucket, and chain collisions together. This straightforward approach delivers O(1) average-case performance for the most common operations in programming—storing and retrieving data by key.\n\nBut this simplicity comes with a contract. HashMap provides the infrastructure; you provide:\n- **Proper hash codes** that distribute evenly across buckets\n- **Immutable keys** that don't change after insertion\n- **Consistent equals/hashCode** that satisfy the Java object contract\n- **Appropriate sizing** to avoid expensive resize operations\n\nWhen you honor this contract, HashMap becomes an incredibly powerful tool. When you violate it—as we saw in the Black Friday incident—HashMap can become your biggest performance bottleneck.\n\nIn the next article, we'll explore how Java 8 strengthened HashMap against worst-case scenarios by introducing tree bins, and how this protects your application from hash collision attacks.\n\n---\n\n## 🔄 Review Schedule\n\n- [ ] **After 1 day:** Re-read \"At a Glance\" and \"Mental Model\" sections\n- [ ] **After 3 days:** Redo Exercises 1-2 without looking at solutions\n- [ ] **After 7 days:** Answer all Interview Questions out loud\n- [ ] **After 14 days:** Do the \"Debug This\" exercise again\n- [ ] **After 30 days:** Review Quick Reference, check if you remember key numbers (0.75, 16, 8)\n\n---\n\n## 🔗 Related & Next\n\n### Related Articles in This Series\n- **Part 3: equals() & hashCode()** - The contract that makes HashMap work\n- **Part 9: HashSet** - Uses HashMap internally\n- **Part 13: HashMap Tree Bins** - Deep dive into Java 8+ treeification\n- **Part 15: LinkedHashMap** - HashMap with predictable iteration order\n\n### Next Up\n- **Part 13: HashMap - Tree Bins & Java 8+ Optimizations** - Learn how HashMap defends against hash collision attacks\n\n### External Resources\n- [JDK HashMap Source Code](https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/HashMap.java)\n- [Java Collections Framework Documentation](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/HashMap.html)\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.979318Z","createdAt","2026-06-10T07:19:25.980184Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",26,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Java","readingTime","seriesId",5,"seriesOrder",12,"author",{"_31":55,"_104":57,"_105":106,"_107":108,"_109":-5,"_110":-5,"_111":-5,"_112":-5,"_113":-5},"category",{"_31":62,"_73":59,"_35":89,"_76":102,"_103":-5},"tags",[79,80,81,82,83,84],"series",{"_31":62,"_73":74,"_35":75,"_76":77,"_78":23},"name","Java Collections Compendium: From Fundamentals to Production Mastery","java-collections-compendium","description","A comprehensive 30-part series covering everything about Java Collections Framework. From foundational concepts like generics and equals/hashCode contract, through deep dives into ArrayList, LinkedList, HashMap, TreeMap, ConcurrentHashMap, to modern features like immutable collections, Java 21 sequenced collections, streams & collectors, and production patterns with JPA, Jackson & Spring. Includes real production stories, mental models, exercises, and 50+ interview questions.","isActive",{"_31":99,"_73":100,"_35":101},{"_31":96,"_73":97,"_35":98},{"_31":93,"_73":94,"_35":95},{"_31":90,"_73":91,"_35":92},{"_31":88,"_73":59,"_35":89},{"_31":85,"_73":86,"_35":87},345,"Map","map",14,"java",257,"Hashmap","hashmap",339,"Hashing","hashing",347,"Collisions","collisions",346,"Buckets","buckets","Category for Java","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]