[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":87,"_71":88,"_35":89},"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":52,"_62":55,"_63":64,"_65":66,"_67":68,"_69":70},"id",74,"title","HashMap / Hash Table","slug","dsa-cheatsheet-part-3-hashmap","excerpt","Visual guide to HashMap: hashing, buckets, collision handling. Watch how keys map to values with O(1) average operations.","# HashMap / Hash Table\n\n## 📋 Quick Reference\n\n| Property | Value |\n|----------|-------|\n| **Type** | Key-value mapping with hashing |\n| **Get/Put** | O(1) average, O(n) worst case |\n| **Contains** | O(1) average |\n| **Memory** | O(n) + load factor overhead |\n| **Ordering** | No guaranteed order |\n| **Best For** | Fast key-based lookup, caching, counting |\n\n**One-liner**: *Hash-based map providing O(1) average-time key lookup via hash codes and buckets.*\n\n---\n\n## 🎮 Interactive Visualizer\n\nWatch how HashMap stores and retrieves values using hash codes and bucket arrays:\n\n```visualizer-hashmap\nshowControls: true\nshowCode: true\n```\n\n**Try these operations:**\n1. Put key-value pairs - see hash calculation and bucket placement\n2. Cause a collision - watch chaining in action\n3. Get a value - observe the O(1) lookup path\n4. Remove an entry - see bucket cleanup\n\n---\n\n## 🔧 Key Operations\n\n### Creating\n\n```java\n// Empty map (default capacity 16, load factor 0.75)\nMap map = new HashMap<>();\n\n// With initial capacity (avoid rehashing)\nMap map = new HashMap<>(1000);\n\n// From existing map\nMap map = new HashMap<>(existingMap);\n\n// Java 9+ immutable\nMap map = Map.of(\"a\", 1, \"b\", 2);\n```\n\n### Adding/Updating\n\n```java\nmap.put(\"key\", 100); // O(1) - add or update\nmap.putIfAbsent(\"key\", 200); // O(1) - only if not present\nmap.putAll(otherMap); // O(n) - add all entries\n\n// Java 8+ compute methods\nmap.compute(\"key\", (k, v) -> v == null ? 1 : v + 1);\nmap.computeIfAbsent(\"key\", k -> expensiveCalculation());\nmap.merge(\"key\", 1, Integer::sum); // Increment pattern\n```\n\n### Retrieving\n\n```java\nInteger val = map.get(\"key\"); // O(1) - null if absent\nInteger val = map.getOrDefault(\"key\", 0); // O(1) - default if absent\nboolean has = map.containsKey(\"key\"); // O(1)\nboolean has = map.containsValue(100); // O(n) - scans all values!\n```\n\n### Removing\n\n```java\nmap.remove(\"key\"); // O(1) - remove by key\nmap.remove(\"key\", 100); // O(1) - remove only if value matches\nmap.clear(); // O(n) - remove all\n```\n\n### Iteration\n\n```java\n// Entry set (most efficient)\nfor (Map.Entry e : map.entrySet()) {\n String key = e.getKey();\n Integer val = e.getValue();\n}\n\n// Keys only\nfor (String key : map.keySet()) { }\n\n// Values only\nfor (Integer val : map.values()) { }\n\n// Java 8+ forEach\nmap.forEach((k, v) -> System.out.println(k + \": \" + v));\n```\n\n---\n\n## 📊 Complexity Analysis\n\n| Operation | Average | Worst Case | Notes |\n|-----------|---------|------------|-------|\n| `get(key)` | O(1) | O(n) | Worst when all hash to same bucket |\n| `put(key, val)` | O(1) | O(n) | May trigger rehash |\n| `remove(key)` | O(1) | O(n) | |\n| `containsKey` | O(1) | O(n) | |\n| `containsValue` | O(n) | O(n) | Always scans all |\n| `size()` | O(1) | O(1) | Stored as field |\n\n### Hash Table Internals\n\n```\nHash Code → Bucket Index → Search Chain\n\nbucket[0]: null\nbucket[1]: Entry(\"cat\", 5) → Entry(\"act\", 3) → null // collision chain\nbucket[2]: Entry(\"dog\", 7) → null\nbucket[3]: null\n...\n```\n\n**Load Factor** = entries / buckets (default 0.75)\n- When exceeded, table doubles and rehashes all entries\n\n---\n\n## ✅ When to Use HashMap\n\n### Good Use Cases\n\n- **Fast key lookup** - caching, memoization\n- **Counting occurrences** - word frequency, etc.\n- **Grouping data** - partition by some key\n- **De-duplication** - track seen items\n\n### Avoid When\n\n- **Need ordering** - use `LinkedHashMap` (insertion) or `TreeMap` (sorted)\n- **Need thread safety** - use `ConcurrentHashMap`\n- **Null keys matter** - HashMap allows one null key, unlike some alternatives\n- **Keys are mutable** - changing key after insertion breaks the map!\n\n---\n\n## ⚠️ Common Pitfalls\n\n### 1. Mutable Keys\n\n```java\n// ❌ DANGER - mutable key\nList key = new ArrayList<>();\nkey.add(\"hello\");\nmap.put(key, 100);\n\nkey.add(\"world\"); // Mutated! hashCode changes\nmap.get(key); // Returns null - can't find it!\n```\n\n### 2. Missing equals/hashCode\n\n```java\n// ❌ Custom class without proper equals/hashCode\nclass Person {\n String name;\n // No equals/hashCode override!\n}\n\nmap.put(new Person(\"Alice\"), 1);\nmap.get(new Person(\"Alice\")); // null! Different object\n```\n\n### 3. Null Confusion\n\n```java\nInteger val = map.get(\"key\");\n// val could be null because:\n// 1. Key doesn't exist, OR\n// 2. Key exists with null value\n\n// ✅ Use containsKey to distinguish\nif (map.containsKey(\"key\")) {\n // Key exists (value might be null)\n}\n```\n\n### 4. Iteration Order Assumption\n\n```java\n// ❌ Don't assume any order!\nfor (String key : map.keySet()) {\n // Order is NOT guaranteed, may change after rehash\n}\n\n// ✅ Use LinkedHashMap if order matters\nMap ordered = new LinkedHashMap<>();\n```\n\n---\n\n## 🎯 Interview Practice\n\nTest your hash table knowledge with 10 curated interview questions:\n\n```visualizer-hashtable-interview\nshowControls: true\nshowCode: true\n```\n\n---\n\n## 🎤 Interview Tips\n\n**Q: How does HashMap handle collisions?**\n\n> In Java 8+, it uses chaining with linked lists that convert to red-black trees when a bucket exceeds 8 entries. This improves worst-case from O(n) to O(log n).\n\n**Q: Why is load factor 0.75 the default?**\n\n> It's a balance between space and time. Lower means fewer collisions but more memory. Higher means more collisions. 0.75 provides good performance for most use cases.\n\n**Q: What makes a good hash function?**\n\n> It should distribute keys uniformly across buckets, be fast to compute, and be consistent (same input always gives same output). Poor distribution causes clustering and O(n) lookups.\n\n**Q: HashMap vs Hashtable?**\n\n> HashMap is not synchronized (faster for single-threaded), allows null key/values. Hashtable is legacy, synchronized, no nulls. Use ConcurrentHashMap for thread safety.\n\n---\n\n## 📚 Series Navigation\n\n**Previous**: [Part 2: LinkedList](dsa-cheatsheet-part-2-linkedlist)\n\n**Next**: [Part 4: TreeSet / BST](dsa-cheatsheet-part-4-treeset)\n\n---\n\n**Visualizer**: `HashMap` from `@tomaszjarosz/react-visualizers`\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.624084Z","createdAt","2026-06-10T07:19:25.624306Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",4,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId","seriesOrder","author",{"_31":55,"_97":57,"_98":99,"_100":101,"_102":-5,"_103":-5,"_104":-5,"_105":-5,"_106":-5},"category",{"_31":93,"_71":59,"_35":94,"_74":95,"_96":-5},"tags",[77,78,79,80],"series",{"_31":52,"_71":72,"_35":73,"_74":75,"_76":23},"name","Interactive Data Structures & Algorithms","dsa-visualized-cheatsheet","description","A concise, visual reference for essential data structures and algorithms. Each article features an interactive visualizer showing how the structure/algorithm works step-by-step, along with complexity analysis, use cases, and quick reference code. Perfect for interview prep, quick review, or learning by visualization.","isActive",{"_31":90,"_71":91,"_35":92},{"_31":87,"_71":88,"_35":89},{"_31":84,"_71":85,"_35":86},{"_31":81,"_71":82,"_35":83},259,"O(1) Lookup","o(1)-lookup",257,"Hashmap","hashmap",258,"Hash Table","hash-table",252,"Data Structure","data-structure",6,"algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]