[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":84,"_73":85,"_35":86},"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",109,"title","HashMap: Tree Bins and Performance","slug","java-collections-part-13-hashmap-tree-bins","excerpt","Explore Java 8's tree bins enhancement: Red-Black trees in collided buckets, treeify thresholds, the HashDoS security fix, and hybrid linked list/tree approach.","# Java Collections Part 13: HashMap Tree Bins & Java 8+ Optimizations\n\nJava 8 fundamentally changed how HashMap handles collisions. Before Java 8, a bucket with many collisions degraded to O(n) lookup time. After Java 8, heavily collided buckets automatically convert to balanced trees, maintaining O(log n) performance. This change wasn't just an optimization - it was a critical security fix against HashDoS attacks.\n\nIn this article, we'll explore how tree bins work, when they activate, and why this matters for your production systems.\n\n## 📋 At a Glance\n\n| Aspect | Details |\n|--------|---------|\n| Feature | Tree bins (Red-Black Trees) in HashMap buckets |\n| Introduced | Java 8 |\n| Treeify Threshold | 8 nodes in bucket |\n| Untreeify Threshold | 6 nodes (after resize) |\n| Min Capacity for Tree | 64 buckets |\n| Key Benefit | O(log n) worst case instead of O(n) |\n\n---\n\n## 🎯 What You'll Learn\n\nAfter reading this article, you will be able to:\n\n- **Explain tree bins**: What they are and why they were introduced\n- **Understand the thresholds**: Why 8, 6, and 64 are the magic numbers\n- **Describe HashDoS attacks**: How they worked and how Java 8 mitigates them\n- **Debug tree bin behavior**: Identify when buckets treeify\n- **Optimize for tree bins**: Use Comparable keys effectively\n- **Make informed decisions**: HashMap vs TreeMap trade-offs\n\n---\n\n## 🔥 Production Story: The HashDoS Incident\n\nIn 2011, a devastating attack vector was publicly disclosed: HashDoS (Hash Denial of Service). By carefully crafting HTTP request parameters with colliding hash codes, attackers could degrade Java web applications from O(1) to O(n²) performance, causing complete service denial.\n\n**The attack scenario:**\n\n```java\n// ❌ Before Java 8: All colliding keys in one bucket\nMap params = new HashMap<>();\n\n// Attacker sends request with thousands of parameters like:\n// \"Aa\", \"BB\", \"CC\", \"DD\"... all with same hashCode!\n// \"Aa\".hashCode() == \"BB\".hashCode() == 2112\n\nfor (String key : attackerControlledKeys) { // 10,000 keys with same hash\n params.put(key, \"value\"); // Each put() traverses entire chain: O(n)\n}\n// Total time: O(n²) for n insertions!\n```\n\n**Real-world impact:**\n- Apache Tomcat, JBoss, Jetty all vulnerable\n- Simple HTTP request could consume 100% CPU for minutes\n- A few malicious requests could take down entire server\n\n**How Java 8 fixed it:**\n\n```java\n// ✅ Java 8+: Long chains convert to trees\nMap params = new HashMap<>();\n\nfor (String key : attackerControlledKeys) {\n params.put(key, \"value\");\n // After 8 collisions, bucket converts to Red-Black Tree\n // Each put() is now O(log n), not O(n)\n}\n// Total time: O(n log n) instead of O(n²)\n// Attack effectiveness reduced by orders of magnitude\n```\n\n**The numbers:**\n- Before Java 8: 10,000 colliding keys → ~50 million comparisons\n- After Java 8: 10,000 colliding keys → ~130,000 comparisons\n- **385x improvement** in worst case\n\nThis is why understanding tree bins matters - it's not just performance, it's security.\n\n---\n\n## 🧠 Mental Model: The Bucket Evolution\n\nThink of each HashMap bucket as a storage system that adapts to load:\n\n```text\n┌─────────────────────────────────────────────────────────────────┐\n│ BUCKET EVOLUTION │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ STAGE 1: Empty Bucket │\n│ ┌─────┐ │\n│ │ null│ No entries yet │\n│ └─────┘ │\n│ │\n│ STAGE 2: Single Node (1-7 entries) │\n│ ┌─────┐ │\n│ │ A │→ B → C → D → ... (Linked list, max 7 before tree) │\n│ └─────┘ │\n│ Lookup: O(n) - walk the chain │\n│ │\n│ STAGE 3: Tree Bin (8+ entries) │\n│ ┌─────┐ │\n│ │ │ ┌───┐ │\n│ │ Tree│ → │ D │ (root) │\n│ │ │ ┌─┴───┴─┐ │\n│ └─────┘ │ B │ │ F │ │\n│ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ │\n│ │A│ │C│ │E│ │G│ (Red-Black Tree) │\n│ └─┘ └─┘ └─┘ └─┘ │\n│ Lookup: O(log n) - binary search in tree │\n│ │\n│ STAGE 4: Back to List (after resize, ≤6 entries) │\n│ If resize spreads entries and bucket has ≤6, converts back │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n**Key insight:** The bucket intelligently adapts - simple list for typical use (fast), tree for pathological cases (safe).\n\n---\n\n## 🔬 Deep Dive\n\n### 1. The Magic Constants\n\n```java\n// ✅ From HashMap source code (Java 8+)\nstatic final int TREEIFY_THRESHOLD = 8; // Convert list to tree\nstatic final int UNTREEIFY_THRESHOLD = 6; // Convert tree back to list\nstatic final int MIN_TREEIFY_CAPACITY = 64; // Min capacity before treeifying\n```\n\n**Why 8 for treeify?**\n\nBased on Poisson distribution analysis. With a good hash function and load factor 0.75:\n\n```text\nProbability of k entries in one bucket (Poisson λ=0.5):\nk=0: 60.65%\nk=1: 30.33%\nk=2: 7.58%\nk=3: 1.26%\nk=4: 0.16%\nk=5: 0.016%\nk=6: 0.0013%\nk=7: 0.00009%\nk=8: 0.000006% ← Extremely rare with good hash!\n\nIf bucket has 8+ entries, it's almost certainly:\n1. Poor hash function, OR\n2. Deliberate attack\nEither way, tree helps.\n```\n\n**Why 6 for untreeify (hysteresis)?**\n\nIf we used 8 for both, a bucket oscillating around 8 entries would constantly convert back and forth. The gap (8 to treeify, 6 to untreeify) prevents this thrashing.\n\n```text\nEntries: 7 → 8 → 9 → 8 → 7 → 6 → 5\n ↑ ↑ ↑\n Treeify Still tree Untreeify (stays list until 8 again)\n```\n\n**Why 64 for min capacity?**\n\nWith small maps, it's cheaper to resize than to treeify:\n\n```java\n// If capacity < 64, resize instead of treeify\nif (tab == null || tab.length < MIN_TREEIFY_CAPACITY)\n resize(); // Spreading entries is cheaper than tree overhead\nelse if (... binCount >= TREEIFY_THRESHOLD - 1)\n treeifyBin(tab, hash); // Large map: treeify the bucket\n```\n\n### 2. TreeNode Structure\n\nWhen a bucket treeifies, nodes are converted from `Node` to `TreeNode`:\n\n```java\n// ✅ Regular node (linked list)\nstatic class Node implements Map.Entry {\n final int hash;\n final K key;\n V value;\n Node next; // 1 reference: next in chain\n}\n\n// ✅ Tree node (Red-Black tree)\nstatic final class TreeNode extends LinkedHashMap.Entry {\n TreeNode parent; // Red-Black tree parent\n TreeNode left; // Left child\n TreeNode right; // Right child\n TreeNode prev; // For unlinking on removal\n boolean red; // Color (for balancing)\n\n // Inherits: hash, key, value, next from Node\n}\n```\n\n**Memory overhead:**\n- Node: ~32 bytes (header + 4 fields)\n- TreeNode: ~56 bytes (header + 9 fields)\n- ~75% more memory per entry when treeified\n\nThis is why treeification is only for pathological cases - the memory cost is significant.\n\n### 3. The Treeify Process\n\n```java\n// ✅ Simplified treeifyBin logic\nfinal void treeifyBin(Node[] tab, int hash) {\n int n = tab.length;\n int index = (n - 1) & hash;\n\n // Step 1: Check if we should resize instead\n if (n < MIN_TREEIFY_CAPACITY) {\n resize(); // Small table - resize is better\n return;\n }\n\n // Step 2: Convert all nodes to TreeNodes\n TreeNode hd = null, tl = null; // head, tail\n for (Node e = tab[index]; e != null; e = e.next) {\n TreeNode p = replacementTreeNode(e, null);\n if (tl == null)\n hd = p;\n else {\n p.prev = tl;\n tl.next = p;\n }\n tl = p;\n }\n\n // Step 3: Replace bucket with tree root\n tab[index] = hd;\n\n // Step 4: Build the Red-Black tree\n if (hd != null)\n hd.treeify(tab);\n}\n```\n\n### 4. Ordering in Trees: Comparable and tieBreakOrder\n\nRed-Black trees need a total ordering. What if keys don't implement `Comparable`?\n\n```java\n// ✅ How HashMap orders keys in trees\n// Priority 1: Compare by Comparable (if implemented)\n// Priority 2: Compare by class name\n// Priority 3: Compare by System.identityHashCode()\n\nstatic int tieBreakOrder(Object a, Object b) {\n int d;\n if (a == null || b == null ||\n (d = a.getClass().getName().compareTo(b.getClass().getName())) == 0)\n d = (System.identityHashCode(a) <= System.identityHashCode(b) ? -1 : 1);\n return d;\n}\n```\n\n**Performance implication:**\n\n```java\n// ✅ Keys implementing Comparable: optimal tree performance\nclass GoodKey implements Comparable {\n String id;\n\n @Override\n public int compareTo(GoodKey other) {\n return this.id.compareTo(other.id);\n }\n}\n// Tree operations use compareTo() - fast, stable ordering\n\n// ⚠️ Keys NOT implementing Comparable: tieBreakOrder fallback\nclass BadKey {\n String id;\n // No Comparable implementation\n}\n// Tree uses class name + identityHashCode - still O(log n) but less cache-friendly\n```\n\n**Best practice:** If you expect high collision rates, make your key class implement `Comparable`.\n\n### 5. The Untreeify Process\n\nWhen does a tree convert back to a list?\n\n```java\n// ✅ During resize, if bucket has ≤ UNTREEIFY_THRESHOLD entries\nfinal void split(HashMap map, Node[] tab, int index, int bit) {\n // ... split tree into two buckets based on hash bit ...\n\n // If either new bucket is small enough, convert back to list\n if (loHead != null) {\n if (lc <= UNTREEIFY_THRESHOLD)\n tab[index] = loHead.untreeify(map); // Back to list!\n else {\n tab[index] = loHead;\n if (hiHead != null) // Tree still needed\n loHead.treeify(tab);\n }\n }\n // ... similar for hiHead ...\n}\n```\n\n**When untreeify happens:**\n1. HashMap resizes (doubles capacity)\n2. Entries in treeified bucket get split between two new buckets\n3. If either new bucket has ≤6 entries, it becomes a list again\n\n### 6. Visualizing Tree Bin Behavior\n\n```text\n┌────────────────────────────────────────────────────────────────────┐\n│ HashMap with Tree Bins │\n├────────────────────────────────────────────────────────────────────┤\n│ │\n│ Bucket Array (capacity = 16) │\n│ ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐ │\n│ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │10 │11 │12 │13 │14 │15 │ │\n│ └─┬─┴───┴─┬─┴───┴───┴─┬─┴───┴───┴───┴───┴───┴───┴─┬─┴───┴───┘───┘ │\n│ │ │ │ │ │\n│ ↓ ↓ ↓ ↓ │\n│ ┌───┐ ┌───┐ ┌──────┐ ┌───┐ │\n│ │ A │ │ D │ │ TREE │ ← 12 entries │ Z │ │\n│ └─┬─┘ └─┬─┘ │ BIN │ all same hash └───┘ │\n│ ↓ ↓ │ │ (single) │\n│ ┌───┐ ┌───┐ │ ┌─┐ │ │\n│ │ B │ │ E │ │ │R│ │ R = Root │\n│ └───┘ └───┘ │ ┌┴─┴┐│ │\n│ (list) (list) │ │ │ ││ Balanced │\n│ 2 items 2 items │ └───┘│ Red-Black │\n│ └──────┘ Tree │\n│ │\n│ Most buckets: 0-3 entries (list) - O(1) effective │ \n│ Rare buckets: 8+ entries (tree) - O(log n) worst case │\n│ │\n└────────────────────────────────────────────────────────────────────┘\n```\n\n### 7. Security Context: HashDoS Deep Dive\n\n**How the attack worked (pre-Java 8):**\n\n```java\n// ❌ Attacker crafts strings with identical hashCodes\n// These all have hashCode = 0:\nString[] collisions = {\n \"pollinating sandridge\",\n \"pollinating sandrill\",\n // ... thousands more crafted strings\n};\n\n// Simple web request:\n// POST /api/data\n// param1=a¶m2=b&... [10,000 params with colliding names]\n\n// Server's HashMap.put() for each parameter:\n// With all collisions in one bucket:\n// put #1: 0 comparisons (empty)\n// put #2: 1 comparison\n// put #3: 2 comparisons\n// put #n: n-1 comparisons\n// Total: 0+1+2+...+(n-1) = n(n-1)/2 = O(n²)\n\n// 10,000 parameters = ~50,000,000 comparisons\n// Can take minutes of CPU time from a single request!\n```\n\n**Why Java 8 tree bins fix it:**\n\n```java\n// ✅ With tree bins (Java 8+):\n// put #1 through #7: O(1) each (list)\n// put #8: O(7) + treeify overhead\n// put #9 through #n: O(log n) each (tree)\n\n// Total: ~7 + tree_build + (n-8) * log(n)\n// 10,000 parameters = ~7 + overhead + 9992 * 13 ≈ 130,000 comparisons\n\n// That's 385x better than O(n²)!\n```\n\n**Additional mitigations in modern Java:**\n\n```java\n// ✅ Java 8+ also randomizes hash seed\n// Each JVM instance has different hash behavior\n// Makes it harder to predict collisions\n\n// ✅ String.hashCode() is deterministic but:\n// - Attack strings must be computed per target\n// - Tree bins limit damage anyway\n```\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: Ignoring Comparable for High-Collision Keys\n\n❌ **Problem:**\n```java\n// Custom key without Comparable\npublic class SessionKey {\n private String userId;\n private String sessionType;\n\n @Override\n public int hashCode() {\n // Intentionally poor hash - many collisions\n return sessionType.hashCode(); // Only 3 types → 3 buckets\n }\n // No Comparable implementation\n}\n\n// When bucket treeifies, tree uses tieBreakOrder\n// Less efficient than proper Comparable ordering\n```\n\n✅ **Solution:**\n```java\npublic class SessionKey implements Comparable {\n private String userId;\n private String sessionType;\n\n @Override\n public int compareTo(SessionKey other) {\n int typeComp = this.sessionType.compareTo(other.sessionType);\n if (typeComp != 0) return typeComp;\n return this.userId.compareTo(other.userId);\n }\n\n @Override\n public int hashCode() {\n return Objects.hash(userId, sessionType); // Better distribution too\n }\n}\n```\n\n---\n\n### Mistake 2: Assuming All Operations Benefit from Trees\n\n❌ **Problem:**\n```java\n// Trees help lookup but iteration is different\nMap map = new HashMap<>();\n// ... populate with many collisions ...\n\n// Iteration still visits every entry: O(n)\nfor (Map.Entry entry : map.entrySet()) {\n // This is O(n) regardless of tree bins\n}\n\n// Tree bins help: get(), put(), remove(), containsKey()\n// Tree bins don't help: iteration, size(), clear()\n```\n\n✅ **Understanding:**\n```java\n// Tree bins optimize per-bucket operations:\nmap.get(key); // O(log n) in treeified bucket\nmap.put(key, value); // O(log n) in treeified bucket\nmap.remove(key); // O(log n) in treeified bucket\n\n// Global operations are unchanged:\nmap.size(); // O(1) - just returns field\nmap.clear(); // O(n) - must clear all buckets\nmap.entrySet().forEach(...); // O(n) - visits every entry\n```\n\n---\n\n### Mistake 3: Trying to Force or Prevent Treeification\n\n❌ **Problem:**\n```java\n// \"I'll prevent trees by keeping capacity high\"\nMap map = new HashMap<>(1000000); // Huge initial capacity\n\n// Trees are still created if 8+ entries collide in ONE bucket!\n// Capacity affects distribution, not collision handling\n```\n\n✅ **Solution:**\n```java\n// Focus on hash distribution, not capacity:\n// 1. Implement good hashCode() in your key class\n// 2. Use immutable, well-distributed key fields\n// 3. Let HashMap manage tree bins automatically\n\n// If you need sorted access, use TreeMap instead\nMap sorted = new TreeMap<>(); // Always O(log n), sorted\n```\n\n---\n\n### Mistake 4: Not Knowing When Trees Exist\n\n❌ **Problem:**\n```java\n// How do I know if my HashMap has tree bins?\nMap map = new HashMap<>();\n// ... operations ...\n\n// There's no public API to check!\n// boolean hasTreeBins = map.??? // Doesn't exist\n```\n\n✅ **Solution:**\n```java\n// Use reflection for debugging (not production!):\npublic static void analyzeHashMap(HashMap map) throws Exception {\n Field tableField = HashMap.class.getDeclaredField(\"table\");\n tableField.setAccessible(true);\n Object[] table = (Object[]) tableField.get(map);\n\n if (table == null) {\n System.out.println(\"Empty map\");\n return;\n }\n\n int treeBuckets = 0;\n int listBuckets = 0;\n int maxChain = 0;\n\n for (Object bucket : table) {\n if (bucket == null) continue;\n\n // Check if it's a TreeNode\n if (bucket.getClass().getName().contains(\"TreeNode\")) {\n treeBuckets++;\n } else {\n listBuckets++;\n // Count chain length\n int length = 1;\n Field nextField = bucket.getClass().getDeclaredField(\"next\");\n nextField.setAccessible(true);\n Object node = bucket;\n while ((node = nextField.get(node)) != null) {\n length++;\n }\n maxChain = Math.max(maxChain, length);\n }\n }\n\n System.out.printf(\"Tree buckets: %d, List buckets: %d, Max chain: %d%n\",\n treeBuckets, listBuckets, maxChain);\n}\n```\n\n---\n\n### Mistake 5: Confusing TreeMap and HashMap Tree Bins\n\n❌ **Problem:**\n```java\n// \"HashMap with tree bins is like TreeMap\"\n// NO! They are fundamentally different:\n```\n\n✅ **Understanding:**\n\n| Aspect | HashMap (with tree bins) | TreeMap |\n|--------|-------------------------|---------|\n| Primary structure | Hash table | Red-Black Tree |\n| Tree bins | Only for collision buckets | Entire structure |\n| Ordering | No ordering (hash-based) | Sorted by keys |\n| Normal lookup | O(1) average | O(log n) always |\n| Collision lookup | O(log n) worst case | O(log n) always |\n| NavigableMap | No | Yes |\n| Memory | Less (mostly Nodes) | More (all TreeNodes) |\n\n```java\n// HashMap: Use when order doesn't matter\nMap hash = new HashMap<>(); // Fastest average case\n\n// TreeMap: Use when you need sorted keys\nMap tree = new TreeMap<>(); // Always sorted, range queries\n```\n\n---\n\n## 🐛 Debug This: The Unexplained Slowdown\n\nA production service experiences periodic slowdowns. Profiling shows excessive time in `HashMap.get()` operations. The map contains user sessions:\n\n```java\npublic class SessionManager {\n private Map sessions = new HashMap<>(1024);\n\n public Session getSession(SessionId id) {\n return sessions.get(id); // Periodically very slow!\n }\n}\n\npublic class SessionId {\n private String visitorId; // UUID-like string\n private String channel; // \"web\", \"mobile\", \"api\" (only 3 values!)\n\n @Override\n public int hashCode() {\n return channel.hashCode(); // ❌ Only uses channel!\n }\n\n @Override\n public boolean equals(Object o) {\n if (!(o instanceof SessionId)) return false;\n SessionId other = (SessionId) o;\n return Objects.equals(visitorId, other.visitorId) &&\n Objects.equals(channel, other.channel);\n }\n}\n```\n\n**Why is `get()` slow? What would you fix?**\n\n---\n\n**✅ Solution:**\n\n**The bug:** `hashCode()` only uses `channel`, which has only 3 possible values (\"web\", \"mobile\", \"api\"). All sessions go into just 3 buckets!\n\nWith thousands of sessions:\n- Each bucket has hundreds or thousands of entries\n- Buckets are treeified (good), but still O(log n) per lookup\n- And since `SessionId` doesn't implement `Comparable`, trees use inefficient `tieBreakOrder`\n\n**The fix:**\n\n```java\npublic class SessionId implements Comparable { // ✅ Add Comparable\n private String visitorId;\n private String channel;\n\n @Override\n public int hashCode() {\n return Objects.hash(visitorId, channel); // ✅ Use ALL identifying fields\n }\n\n @Override\n public boolean equals(Object o) {\n if (!(o instanceof SessionId)) return false;\n SessionId other = (SessionId) o;\n return Objects.equals(visitorId, other.visitorId) &&\n Objects.equals(channel, other.channel);\n }\n\n @Override\n public int compareTo(SessionId other) { // ✅ For efficient tree operations\n int channelComp = this.channel.compareTo(other.channel);\n if (channelComp != 0) return channelComp;\n return this.visitorId.compareTo(other.visitorId);\n }\n}\n```\n\n**After the fix:**\n- Sessions distributed across many buckets (good hash distribution)\n- Most buckets have 0-3 entries (no trees needed)\n- If trees form, `Comparable` ensures efficient ordering\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: Force Treeification\n⭐⭐ Difficulty: Medium | ⏱️ Time: 15 minutes\n\n**Task:** Create a scenario that forces HashMap to treeify a bucket, then verify it happened.\n\n```java\npublic class TreeifyDemo {\n public static void main(String[] args) {\n // TODO: Create keys that all hash to the same bucket\n // TODO: Add enough to trigger treeification\n // TODO: Verify the bucket is now a tree\n }\n}\n\n// Hint: Create a class where you control hashCode()\n```\n\n**✅ Solution:**\n\n```java\npublic class TreeifyDemo {\n\n static class CollidingKey implements Comparable {\n private final int id;\n private final int forcedHash;\n\n CollidingKey(int id, int forcedHash) {\n this.id = id;\n this.forcedHash = forcedHash;\n }\n\n @Override\n public int hashCode() {\n return forcedHash; // All instances with same forcedHash collide\n }\n\n @Override\n public boolean equals(Object o) {\n if (!(o instanceof CollidingKey)) return false;\n return this.id == ((CollidingKey) o).id;\n }\n\n @Override\n public int compareTo(CollidingKey other) {\n return Integer.compare(this.id, other.id);\n }\n }\n\n public static void main(String[] args) throws Exception {\n Map map = new HashMap<>(64); // >= MIN_TREEIFY_CAPACITY\n\n // Add 10 keys that all collide (same hash)\n int collidingHash = 42;\n for (int i = 0; i < 10; i++) {\n map.put(new CollidingKey(i, collidingHash), \"value\" + i);\n }\n\n // Verify treeification using reflection\n Field tableField = HashMap.class.getDeclaredField(\"table\");\n tableField.setAccessible(true);\n Object[] table = (Object[]) tableField.get(map);\n\n int bucketIndex = collidingHash & (table.length - 1);\n Object bucket = table[bucketIndex];\n\n System.out.println(\"Bucket class: \" + bucket.getClass().getName());\n // Should print: java.util.HashMap$TreeNode\n\n boolean isTree = bucket.getClass().getName().contains(\"TreeNode\");\n System.out.println(\"Bucket is treeified: \" + isTree); // true\n }\n}\n```\n\n---\n\n### Exercise 2: HashDoS Simulation (Educational)\n⭐⭐⭐ Difficulty: Medium | ⏱️ Time: 20 minutes\n\n**Task:** Compare HashMap performance with good vs. bad hash distribution to understand the attack vector.\n\n```java\npublic class HashDoSSimulation {\n // TODO: Create two key types:\n // 1. GoodKey - well-distributed hashCode\n // 2. BadKey - all instances have same hashCode\n\n // TODO: Benchmark put() operations for 10,000 keys\n // TODO: Compare times for Java 7 simulation (list only) vs Java 8+ (with trees)\n}\n```\n\n**✅ Solution:**\n\n```java\npublic class HashDoSSimulation {\n\n static class GoodKey {\n private final int id;\n GoodKey(int id) { this.id = id; }\n\n @Override\n public int hashCode() { return Integer.hashCode(id); } // Good distribution\n\n @Override\n public boolean equals(Object o) {\n return o instanceof GoodKey && ((GoodKey) o).id == this.id;\n }\n }\n\n static class BadKey implements Comparable {\n private final int id;\n BadKey(int id) { this.id = id; }\n\n @Override\n public int hashCode() { return 1; } // All collide!\n\n @Override\n public boolean equals(Object o) {\n return o instanceof BadKey && ((BadKey) o).id == this.id;\n }\n\n @Override\n public int compareTo(BadKey o) { return Integer.compare(id, o.id); }\n }\n\n public static void main(String[] args) {\n int n = 10_000;\n\n // Test 1: Good hash distribution\n Map goodMap = new HashMap<>();\n long startGood = System.nanoTime();\n for (int i = 0; i < n; i++) {\n goodMap.put(new GoodKey(i), \"v\");\n }\n long goodTime = System.nanoTime() - startGood;\n System.out.printf(\"Good hash: %d keys in %.2f ms%n\", n, goodTime / 1_000_000.0);\n\n // Test 2: Bad hash (all collisions) - Java 8+ with tree bins\n Map badMap = new HashMap<>(64); // Ensure treeification\n long startBad = System.nanoTime();\n for (int i = 0; i < n; i++) {\n badMap.put(new BadKey(i), \"v\");\n }\n long badTime = System.nanoTime() - startBad;\n System.out.printf(\"Bad hash (with tree bins): %d keys in %.2f ms%n\", n, badTime / 1_000_000.0);\n\n // The ratio shows the mitigation effect\n System.out.printf(\"Slowdown factor: %.2fx%n\", (double) badTime / goodTime);\n\n // Note: Pre-Java 8 (list only) would be O(n²), ~50,000,000 comparisons\n // Java 8+ (tree bins) is O(n log n), ~130,000 comparisons\n // Expected slowdown: ~10-50x, not ~1000x\n }\n}\n```\n\n---\n\n### Exercise 3: Analyze HashMap Distribution\n⭐⭐⭐ Difficulty: Medium-Hard | ⏱️ Time: 20 minutes\n\n**Task:** Create a utility to analyze HashMap bucket distribution and detect potential issues.\n\n```java\npublic class HashMapAnalyzer {\n\n public static class Analysis {\n public int totalBuckets;\n public int usedBuckets;\n public int emptyBuckets;\n public int treeBuckets;\n public int listBuckets;\n public int maxChainLength;\n public double avgChainLength;\n public int totalEntries;\n }\n\n public static Analysis analyze(HashMap map) {\n // TODO: Use reflection to inspect internal structure\n // TODO: Return comprehensive analysis\n }\n}\n```\n\n**✅ Solution:**\n\n```java\npublic class HashMapAnalyzer {\n\n public static class Analysis {\n public int totalBuckets;\n public int usedBuckets;\n public int emptyBuckets;\n public int treeBuckets;\n public int listBuckets;\n public int maxChainLength;\n public double avgChainLength;\n public int totalEntries;\n\n @Override\n public String toString() {\n return String.format(\n \"HashMap Analysis:%n\" +\n \" Total buckets: %d (used: %d, empty: %d)%n\" +\n \" Tree buckets: %d, List buckets: %d%n\" +\n \" Max chain length: %d, Avg chain length: %.2f%n\" +\n \" Total entries: %d%n\" +\n \" Load factor: %.2f\",\n totalBuckets, usedBuckets, emptyBuckets,\n treeBuckets, listBuckets,\n maxChainLength, avgChainLength,\n totalEntries,\n (double) totalEntries / totalBuckets\n );\n }\n }\n\n public static Analysis analyze(HashMap map) throws Exception {\n Analysis result = new Analysis();\n\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 result; // Empty map\n }\n\n result.totalBuckets = table.length;\n int totalChainLength = 0;\n\n for (Object bucket : table) {\n if (bucket == null) {\n result.emptyBuckets++;\n continue;\n }\n\n result.usedBuckets++;\n String className = bucket.getClass().getName();\n\n if (className.contains(\"TreeNode\")) {\n result.treeBuckets++;\n // Count tree size (complex - simplified here)\n int size = countTreeSize(bucket);\n result.maxChainLength = Math.max(result.maxChainLength, size);\n totalChainLength += size;\n result.totalEntries += size;\n } else {\n result.listBuckets++;\n int chainLength = countListLength(bucket);\n result.maxChainLength = Math.max(result.maxChainLength, chainLength);\n totalChainLength += chainLength;\n result.totalEntries += chainLength;\n }\n }\n\n result.avgChainLength = result.usedBuckets > 0\n ? (double) totalChainLength / result.usedBuckets\n : 0;\n\n return result;\n }\n\n private static int countListLength(Object node) throws Exception {\n int length = 0;\n Field nextField = null;\n\n while (node != null) {\n length++;\n if (nextField == null) {\n nextField = node.getClass().getDeclaredField(\"next\");\n nextField.setAccessible(true);\n }\n node = nextField.get(node);\n }\n return length;\n }\n\n private static int countTreeSize(Object treeNode) throws Exception {\n // Simplified: count via linked structure (TreeNode maintains list too)\n return countListLength(treeNode);\n }\n\n // Usage example\n public static void main(String[] args) throws Exception {\n Map map = new HashMap<>();\n for (int i = 0; i < 1000; i++) {\n map.put(\"key\" + i, i);\n }\n\n Analysis analysis = analyze((HashMap) map);\n System.out.println(analysis);\n }\n}\n```\n\n---\n\n### Exercise 4: Comparable vs Non-Comparable Performance\n⭐⭐⭐ Difficulty: Medium | ⏱️ Time: 15 minutes\n\n**Task:** Benchmark tree bin performance with and without `Comparable` implementation.\n\n```java\npublic class ComparableBenchmark {\n // TODO: Create ComparableKey (implements Comparable)\n // TODO: Create NonComparableKey (no Comparable)\n // TODO: Both should have same colliding hashCode\n // TODO: Benchmark get() with 1000 entries in tree bin\n}\n```\n\n**✅ Solution:**\n\n```java\npublic class ComparableBenchmark {\n\n static class ComparableKey implements Comparable {\n final int id;\n\n ComparableKey(int id) { this.id = id; }\n\n @Override\n public int hashCode() { return 1; } // Force collisions\n\n @Override\n public boolean equals(Object o) {\n return o instanceof ComparableKey && ((ComparableKey) o).id == id;\n }\n\n @Override\n public int compareTo(ComparableKey o) {\n return Integer.compare(id, o.id); // Efficient comparison\n }\n }\n\n static class NonComparableKey {\n final int id;\n\n NonComparableKey(int id) { this.id = id; }\n\n @Override\n public int hashCode() { return 1; } // Force collisions\n\n @Override\n public boolean equals(Object o) {\n return o instanceof NonComparableKey && ((NonComparableKey) o).id == id;\n }\n // No Comparable - tree will use tieBreakOrder\n }\n\n public static void main(String[] args) {\n int n = 1000;\n int lookups = 100_000;\n\n // Setup: Comparable keys\n Map compMap = new HashMap<>(64);\n ComparableKey[] compKeys = new ComparableKey[n];\n for (int i = 0; i < n; i++) {\n compKeys[i] = new ComparableKey(i);\n compMap.put(compKeys[i], \"v\");\n }\n\n // Setup: Non-Comparable keys\n Map nonCompMap = new HashMap<>(64);\n NonComparableKey[] nonCompKeys = new NonComparableKey[n];\n for (int i = 0; i < n; i++) {\n nonCompKeys[i] = new NonComparableKey(i);\n nonCompMap.put(nonCompKeys[i], \"v\");\n }\n\n // Benchmark: Comparable\n long startComp = System.nanoTime();\n for (int i = 0; i < lookups; i++) {\n compMap.get(compKeys[i % n]);\n }\n long compTime = System.nanoTime() - startComp;\n\n // Benchmark: Non-Comparable\n long startNonComp = System.nanoTime();\n for (int i = 0; i < lookups; i++) {\n nonCompMap.get(nonCompKeys[i % n]);\n }\n long nonCompTime = System.nanoTime() - startNonComp;\n\n System.out.printf(\"Comparable keys: %d lookups in %.2f ms%n\",\n lookups, compTime / 1_000_000.0);\n System.out.printf(\"Non-Comparable keys: %d lookups in %.2f ms%n\",\n lookups, nonCompTime / 1_000_000.0);\n System.out.printf(\"Comparable is %.2fx faster%n\",\n (double) nonCompTime / compTime);\n }\n}\n```\n\n---\n\n### Exercise 5: Custom HashMap with Tree Bin Logging\n⭐⭐⭐⭐ Difficulty: Hard | ⏱️ Time: 25 minutes\n\n**Task:** Create a HashMap wrapper that logs when treeification occurs.\n\n```java\npublic class LoggingHashMap extends HashMap {\n // TODO: Override putVal or relevant methods\n // TODO: Detect when treeification happens\n // TODO: Log bucket index and entry count\n\n // Note: This is challenging because treeifyBin is private\n // You may need a creative approach!\n}\n```\n\n**✅ Solution:**\n\n```java\npublic class LoggingHashMap extends HashMap {\n private final Consumer logger;\n private final Map bucketSizes = new ConcurrentHashMap<>();\n\n public LoggingHashMap(Consumer logger) {\n super();\n this.logger = logger;\n }\n\n public LoggingHashMap(int initialCapacity, Consumer logger) {\n super(initialCapacity);\n this.logger = logger;\n }\n\n @Override\n public V put(K key, V value) {\n int hash = hash(key);\n V result = super.put(key, value);\n\n // Check bucket state after put\n checkForTreeification(hash);\n return result;\n }\n\n private static int hash(Object key) {\n int h;\n return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);\n }\n\n private void checkForTreeification(int hash) {\n try {\n Field tableField = HashMap.class.getDeclaredField(\"table\");\n tableField.setAccessible(true);\n Object[] table = (Object[]) tableField.get(this);\n\n if (table == null) return;\n\n int index = hash & (table.length - 1);\n Object bucket = table[index];\n\n if (bucket == null) return;\n\n int currentSize = countBucketSize(bucket);\n Integer previousSize = bucketSizes.get(index);\n\n // Detect treeification: size crosses threshold AND bucket is TreeNode\n boolean isTree = bucket.getClass().getName().contains(\"TreeNode\");\n\n if (isTree && (previousSize == null || previousSize < 8)) {\n logger.accept(String.format(\n \"TREEIFIED: Bucket %d converted to tree (size: %d)\",\n index, currentSize));\n }\n\n bucketSizes.put(index, currentSize);\n\n } catch (Exception e) {\n // Reflection failed - ignore in production\n }\n }\n\n private int countBucketSize(Object node) throws Exception {\n int size = 0;\n Field nextField = null;\n\n while (node != null) {\n size++;\n if (nextField == null) {\n try {\n nextField = node.getClass().getDeclaredField(\"next\");\n nextField.setAccessible(true);\n } catch (NoSuchFieldException e) {\n break; // TreeNode structure differs\n }\n }\n node = nextField.get(node);\n }\n return size;\n }\n\n // Usage\n public static void main(String[] args) {\n LoggingHashMap map = new LoggingHashMap<>(64, System.out::println);\n\n // Add entries with colliding hashes\n class CollidingInt {\n final int value;\n CollidingInt(int v) { this.value = v; }\n @Override public int hashCode() { return 1; }\n @Override public boolean equals(Object o) {\n return o instanceof CollidingInt && ((CollidingInt) o).value == value;\n }\n }\n\n // This won't work directly with Integer keys, need wrapper\n // For demo, using reflection-based detection\n for (int i = 0; i < 20; i++) {\n map.put(i, \"value\" + i);\n }\n }\n}\n```\n\n---\n\n## 📝 Summary & Key Takeaways\n\n### The Tree Bin Mechanism\n\n```text\nBucket State Transitions:\n\n ┌─────────────────────┐\n put() │ │ resize()\n (size < 8) │ LINKED LIST │ (size ≤ 6)\n ┌────────────────→│ (0-7 nodes) │←────────────────┐\n │ │ O(n) │ │\n │ └─────────┬───────────┘ │\n │ │ │\n │ put() │ (size = 8, │\n │ │ capacity ≥ 64) │\n │ ↓ │\n │ ┌─────────────────────┐ │\n │ │ │ │\n │ │ RED-BLACK TREE │─────────────────┘\n │ │ (8+ nodes) │\n │ │ O(log n) │\n │ └─────────────────────┘\n │ │\n └───────────────────────────┘\n put() (continues adding)\n```\n\n### Key Constants\n\n| Constant | Value | Purpose |\n|----------|-------|---------|\n| TREEIFY_THRESHOLD | 8 | Convert list → tree when bucket has 8+ entries |\n| UNTREEIFY_THRESHOLD | 6 | Convert tree → list when bucket has ≤6 entries (after resize) |\n| MIN_TREEIFY_CAPACITY | 64 | Don't treeify if map capacity < 64 (resize instead) |\n\n### Performance Characteristics\n\n| Operation | Normal Case | With Tree Bins |\n|-----------|-------------|----------------|\n| get() | O(1) average | O(log n) worst case |\n| put() | O(1) average | O(log n) worst case |\n| remove() | O(1) average | O(log n) worst case |\n| iteration | O(n) | O(n) |\n\n### Best Practices\n\n1. **Implement Comparable** on key classes that might collide heavily\n2. **Use good hashCode()** implementations (Objects.hash or similar)\n3. **Don't try to prevent trees** - they exist for your protection\n4. **Consider TreeMap** if you need sorted keys (always O(log n))\n5. **Monitor in production** if you suspect hash collision issues\n\n---\n\n## 🎤 Senior-Level Interview Questions\n\n### Question #1: When does a HashMap bucket convert to a tree?\n\n**What interviewers want to hear**: Understanding of the specific conditions.\n\n**Strong answer**: A bucket converts to a tree (treeifies) when THREE conditions are met:\n1. The bucket contains 8 or more entries (TREEIFY_THRESHOLD = 8)\n2. The total map capacity is at least 64 (MIN_TREEIFY_CAPACITY = 64)\n3. A new entry is being added that would increase the bucket size to 8+\n\nIf capacity is less than 64, HashMap resizes instead of treeifying - spreading entries across more buckets is more efficient for small maps.\n\n---\n\n### Question #2: Why is the treeify threshold 8 specifically?\n\n**What interviewers want to hear**: Understanding of the probabilistic reasoning.\n\n**Strong answer**: The threshold is based on Poisson distribution analysis. With a good hash function and load factor of 0.75, the probability of 8 or more entries landing in the same bucket is approximately 0.00000006 (six in a hundred million). This is so rare under normal conditions that if it happens, it almost certainly indicates either a poor hash function or a deliberate collision attack. The value 8 provides a good balance - high enough to avoid unnecessary overhead from tree creation in normal use, low enough to protect against attacks before performance degrades significantly.\n\n---\n\n### Question #3: What is HashDoS and how do tree bins mitigate it?\n\n**What interviewers want to hear**: Understanding of the security implications.\n\n**Strong answer**: HashDoS (Hash Denial of Service) is an attack where an adversary sends data with keys that all hash to the same bucket. Pre-Java 8, this degraded HashMap operations from O(1) to O(n), making total insertion time O(n²). With 10,000 colliding keys, this meant ~50 million comparisons from a single request - enough to consume 100% CPU for minutes.\n\nTree bins mitigate this by converting heavily-loaded buckets to Red-Black trees. This changes worst-case lookup from O(n) to O(log n). With 10,000 collisions, that's ~130,000 operations instead of ~50 million - a 385x improvement. The attack becomes impractical because the computational cost to the server is bounded.\n\n---\n\n### Question #4: How does HashMap order keys in tree bins when keys don't implement Comparable?\n\n**What interviewers want to hear**: Knowledge of the tieBreakOrder mechanism.\n\n**Strong answer**: When keys don't implement Comparable, HashMap uses a fallback ordering called tieBreakOrder:\n1. First, it compares the fully-qualified class names of the keys\n2. If class names are equal, it uses `System.identityHashCode()` to establish ordering\n\nThis ensures a consistent total ordering for the Red-Black tree, even with non-Comparable keys. However, it's less efficient than using proper Comparable implementations because: (a) string comparison of class names has overhead, and (b) identityHashCode-based ordering doesn't preserve any logical key ordering, potentially making tree operations less cache-friendly.\n\n---\n\n### Question #5: When does a tree bin convert back to a linked list?\n\n**What interviewers want to hear**: Understanding of the untreeify process.\n\n**Strong answer**: Tree bins convert back to linked lists (untreeify) during resize operations when the new bucket has 6 or fewer entries (UNTREEIFY_THRESHOLD = 6). This happens because resize doubles the capacity and splits each bucket's entries between two new buckets based on a hash bit. If the split results in small buckets, maintaining tree structure has more overhead than benefit. The gap between 8 (treeify) and 6 (untreeify) prevents thrashing - a bucket oscillating around 7 entries won't constantly convert back and forth.\n\n---\n\n### Question #6: Do tree bins have performance overhead?\n\n**What interviewers want to hear**: Balanced understanding of trade-offs.\n\n**Strong answer**: Yes, tree bins have several overheads:\n\n1. **Memory**: TreeNode uses ~56 bytes vs Node's ~32 bytes (75% more per entry)\n2. **Insertion**: Building and maintaining Red-Black tree requires rotations and recoloring\n3. **Constant factors**: Tree operations have higher constant factors than list traversal for small n\n\nHowever, these overheads are acceptable because:\n- Trees only form in pathological cases (collision attacks or bad hash functions)\n- The O(log n) guarantee protects against worst-case degradation\n- In normal operation, most buckets have 0-2 entries (no trees)\n\nThe design philosophy is: \"Pay small overhead in rare edge cases to guarantee bounded worst-case performance.\"\n\n---\n\n## 🏁 Conclusion\n\nTree bins represent one of the most important defensive programming decisions in the JDK. By automatically converting heavily-loaded buckets to Red-Black trees, HashMap provides:\n\n- **Security**: Protection against HashDoS attacks\n- **Predictability**: Bounded O(log n) worst-case performance\n- **Transparency**: No code changes required - it \"just works\"\n\n**Key takeaways:**\n\n1. Tree bins activate at 8+ entries per bucket (if capacity ≥ 64)\n2. They convert back to lists at ≤6 entries during resize\n3. Implementing `Comparable` on key classes optimizes tree performance\n4. Good hash distribution prevents trees from forming at all\n5. Don't try to game the system - let HashMap manage itself\n\n**Your next step:** Continue to Part 14 (TreeMap & NavigableMap) to understand when you should use a tree-based map from the start, or Part 18 (ConcurrentHashMap) to learn about thread-safe maps.\n\n---\n\n## 📅 Review Schedule for This Article\n\n| Day | Task | Time |\n|-----|------|------|\n| Day 1 | Review the thresholds (8, 6, 64) and why | 5 min |\n| Day 3 | Redo Exercise 1 (Force Treeification) | 15 min |\n| Day 7 | Answer interview questions without looking | 10 min |\n| Day 14 | Redo Exercise 2 (HashDoS Simulation) | 15 min |\n| Day 30 | Review mental model and security implications | 5 min |\n\n---\n\n*Next in series: [Part 14: TreeMap & NavigableMap - Red-Black Trees & Range Queries]*\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.996147Z","createdAt","2026-06-10T07:19:25.997718Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",26,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Java","readingTime","seriesId",5,"seriesOrder",13,"author",{"_31":55,"_100":57,"_101":102,"_103":104,"_105":-5,"_106":-5,"_107":-5,"_108":-5,"_109":-5},"category",{"_31":62,"_73":59,"_35":94,"_76":98,"_99":-5},"tags",[79,80,81,82,83],"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":95,"_73":96,"_35":97},{"_31":93,"_73":59,"_35":94},{"_31":90,"_73":91,"_35":92},{"_31":87,"_73":88,"_35":89},{"_31":84,"_73":85,"_35":86},348,"Tree Bins","tree-bins",343,"Red-black Tree","red-black-tree",118,"Performance","performance",14,"java",257,"Hashmap","hashmap","Category for Java","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]