Hash Maps

A HashMap stores key-value pairs using hashing. It computes a hash of the key to determine the bucket index, giving O(1) average time for get and put operations. Keys must correctly implement hashCode() and equals(). It is not thread-safe — use ConcurrentHashMap for concurrent access.

Key Concepts

Property	Value
Average get/put	O(1)
Worst-case get/put	O(n) — all keys hash to same bucket
Null keys	1 allowed (stored in bucket 0)
Thread-safe	No (ConcurrentHashMap is)
Default capacity	16
Default load factor	0.75

Deep Dive: How Hashing Works Internally

When you call put(key, value):

1. Compute key.hashCode()
2. Apply a spread function to reduce collisions
3. Map to bucket index: (n - 1) & hash

// Java's internal hash spread function
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

The XOR with the upper 16 bits ensures that differences in higher bits also affect the bucket index.

Deep Dive: Collision Handling

When two keys map to the same bucket:

• Java 7: Linked list chaining (O(n) worst case)
• Java 8+: Linked list → Red-Black Tree when bucket size > 8 (treeify threshold)
  • Degrades gracefully: O(n) → O(log n) worst case
  • Untreeifies when bucket size drops below 6

Bucket 5: [K1,V1] → [K2,V2] → [K3,V3]  // Linked list
Bucket 5: RedBlackTree({K1,V1}, {K2,V2}, ... {K9,V9})  // Treeified

Deep Dive: Resizing (Rehashing)

When size > capacity × loadFactor, the map doubles its capacity and rehashes all entries.

• Default: resize at 16 × 0.75 = 12 entries
• Rehashing is O(n) — this is why initial capacity matters for large maps
• After resize, entries either stay in the same bucket or move to oldIndex + oldCapacity

Tip: If you know the size upfront, set initial capacity to avoid rehashing:

Map<String, Integer> map = new HashMap<>(expectedSize * 4 / 3 + 1);

Deep Dive: hashCode() and equals() Contract

Critical contract:

• If a.equals(b) is true, then a.hashCode() == b.hashCode() must be true
• If a.hashCode() == b.hashCode(), a.equals(b) may or may not be true

Breaking this contract causes silent bugs — keys become "lost" in the map.

@Override
public int hashCode() {
    return Objects.hash(field1, field2);
}

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (!(o instanceof MyClass)) return false;
    MyClass that = (MyClass) o;
    return Objects.equals(field1, that.field1)
        && Objects.equals(field2, that.field2);
}

Common Interview Questions

• How does HashMap work internally?
• What happens when two keys have the same hashCode?
• Why did Java 8 introduce treeification?
• What's the difference between HashMap, TreeMap, and LinkedHashMap?
• How does ConcurrentHashMap achieve thread safety?
• Why is the default load factor 0.75?