HashMap

🔍 What Is It?

HashMap is java.util.Map backed by a hash table.

Internal Structure (Java 8+):

buckets array: [bucket0][bucket1][bucket2]...[bucket15]
                   |
              LinkedList (or TreeNode if > 8 entries)
              [key1=val1] -> [key2=val2] -> null

Key Parameters:

• →Initial capacity: 16 (number of buckets)
• →Load factor: 0.75 (resize when 75% of buckets are used)
• →Threshold: capacity * loadFactor = point at which resize happens
• →Resize: doubles capacity, rehashes all entries — O(n)

Java 8 Improvement:

When a bucket has more than 8 entries (treeify threshold), it converts from a linked list to a balanced tree. This changes worst-case from O(n) to O(log n) for buckets with many collisions (e.g., when hashCode() returns the same value for all keys).

🎯 Why Do We Need It?

HashMap provides O(1) average lookup by key — impossible with a List (O(n) search). It is the foundation of caching, indexing, and any operation where you need to find data by a key rather than iterating through everything.

🏗️ What Happens in Real Projects?

HashMap is everywhere:

// Configuration
Map<String, String> config = new HashMap<>();
config.put("db.host", "localhost");
String host = config.getOrDefault("db.host", "127.0.0.1");

// In-memory cache
Map<Long, User> userCache = new HashMap<>();
User user = userCache.computeIfAbsent(userId, id -> db.findUser(id));

// Grouping/indexing
Map<String, List<Product>> byCategory = products.stream()
    .collect(Collectors.groupingBy(Product::getCategory));

⚙️ How It Works

put(key, value) algorithm:

1. If key is null: store in bucket 0
2. Compute hash: (h = key.hashCode()) ^ (h >>> 16) (spread high bits)
3. Find bucket: hash & (capacity - 1) (fast modulo for power-of-2 capacity)
4. Traverse bucket's linked list/tree looking for existing key (using equals())
5. If found: replace value; if not found: add new entry
6. If size > threshold: resize (double capacity, rehash all)

Why capacity is always a power of 2:

Finding the bucket with hash & (capacity-1) is a single bitwise AND operation — much faster than hash % capacity.

hashCode() and equals() contract:

If a.equals(b) then a.hashCode() == b.hashCode()

(but not vice versa — different objects can have the same hash = collision)

💻 Example

HashMap Deep Dive — Understanding HashMap internals through code.

// Demonstrate why equals/hashCode matters
class BadKey {
    int value;
    BadKey(int v) { this.value = v; }
    // NO equals/hashCode override!
}

Map<BadKey, String> bad = new HashMap<>();
BadKey k1 = new BadKey(42);
bad.put(k1, "hello");
System.out.println(bad.get(k1));          // "hello" (same reference)
System.out.println(bad.get(new BadKey(42))); // null! (different object)

// Fix: proper equals/hashCode
record GoodKey(int value) {}  // Record auto-generates equals/hashCode

Map<GoodKey, String> good = new HashMap<>();
good.put(new GoodKey(42), "hello");
System.out.println(good.get(new GoodKey(42)));  // "hello" ✓

// Pre-sizing for known capacity
// To store 100 entries without resize:
// capacity = 100 / 0.75 = 134, next power of 2 = 256
Map<String, Object> preAllocated = new HashMap<>(256);

// Observe resize behavior
Map<Integer, Integer> map = new HashMap<>(4);  // capacity 4
// Resize at 4 * 0.75 = 3 entries
map.put(1, 1);  // size=1, no resize
map.put(2, 2);  // size=2, no resize
map.put(3, 3);  // size=3 = threshold, RESIZE to capacity 8!
map.put(4, 4);  // size=4, no resize (threshold now 6)

🤔 Common Confusions

🚨 Common Production Issues

✅ Best Practices

🏛️ Architect's Note

💬 Frequently Asked Questions

🎯 Key Takeaways

🔗 Related Topics

🎯 Practice this topic in interviews

↗ Where this topic fits