Zum Hauptinhalt springen

Week 6 Day 3 — HashMap Internals

Goal​

Today I want the whiteboard picture of HashMap: hash, bucket, collision, resize, and why a mutable key vanishes.

Main questions:

  1. What happens on put and get?
  2. How do collisions work after Java 8?
  3. When does the table resize?
  4. Why must equals and hashCode stay stable?
  5. Why is “O(1)” not a promise?

1. Hash, then equals​


key.hashCode()  →  mix bits  →  index = hash & (capacity - 1)
                                    │
                                    ▼
                              bucket[i]
                          empty | node | list | tree
                                    │
                         same hash? then key.equals

Capacity is a power of two so & (n - 1) is a cheap modulo.

get uses the same index, then walks the bin. Matching is hash first, equals second. Two keys with the same hash and equals are the same map key. The old value is replaced on put.

One null key is allowed (HashMap only). It lives at index 0. ConcurrentHashMap and Hashtable reject nulls.

Memory sentence:

Hash picks the bucket. equals confirms the key. Collisions list, then tree.

2. Collisions: list, then tree​

If two different keys land in the same bucket, they form a linked list of nodes.

Since Java 8, if a bin grows past 8 nodes and the table is large enough (capacity ≥ 64), the bin treeifies into a red-black tree. Lookup in that bin becomes O(log n) instead of O(n). If the table is still small, HashMap resizes instead of treeifying.

A bad hashCode (constant return 1) turns the map into one long bin. Expected O(1) becomes O(n) or O(log n). That is why “HashMap is O(1)” is expected constant time with a decent hash, not a guarantee.

3. Resize and load factor​

Default load factor is 0.75. When size > capacity * loadFactor, the table doubles and entries are redistributed.

Resize is O(n). A map I fill to millions of entries without an expected size will resize repeatedly. new HashMap<>(expected) helps when I know the size.

I do not set the load factor in application code without a reason. 0.75 is the usual trade-off between space and collisions.

4. Mutable keys disappear​

The bucket is chosen from hashCode at insert time. If I later mutate a field that hashCode/equals use, the key still sits in the old bucket. get hashes the new value, looks in a different bucket, and returns null. The entry is a ghost: it iterates, but lookup misses.


record Bad(int[] data) {
    @Override public boolean equals(Object o) { /* uses data[0] */ }
    @Override public int hashCode() { return data[0]; }
}

int[] n = {1};
Map<Bad, String> map = new HashMap<>();
Bad key = new Bad(n);
map.put(key, "x");
n[0] = 99;
map.get(key); // typically null

Rules:

  • Map keys and set elements must be immutable in the fields that equals/hashCode use.
  • Records with mutable components are not safe keys unless I copy (Week 1).
  • JPA entities with id-based equality: do not put them in a HashSet before the id is assigned; do not change that id later.

Memory sentence:

Equal objects must share a hash. A mutated key stays in the old bucket.

5. Spring connection​

  • Caching with a HashMap on a singleton: not thread-safe (Day 4 / Week 8). Also needs immutable keys (String, Long, records of values).
  • Request DTO as a map key: if Jackson or a setter mutates it after put, the cache is wrong.
  • equals/hashCode on @Entity: Lombok @Data includes collections and lazy fields — a HashSet of entities can trigger extra SQL or break after load (Week 2 Day 5).

6. Common traps​

Trap 1: “HashMap is always O(1).”

Trap 2: Using a mutable bean as a key.

Trap 3: Overriding equals without hashCode (Week 2). The key never finds its bucket.

Trap 4: Iterating keySet and putting new keys — fail-fast (Day 4).

Trap 5: Assuming treeification always happens at 8. The table must also be big enough; otherwise HashMap resizes.

Practice Questions and Answers​

Question 1​

How does HashMap work internally?

Answer:

put hashes the key, mixes bits, and indexes a power-of-two table. An empty bucket stores the node. Collisions form a list; a long bin in a large table becomes a red-black tree. Lookup uses hash, then equals. When size exceeds capacity times 0.75, the table doubles.

Question 2​

Why does changing a key after insert break the map?

Answer:

The entry sits in the bucket chosen from the old hash. After mutation, get computes a new hash and looks elsewhere. equals never runs on the old bucket. The mapping is lost for lookup.

Question 3​

Why mix the hash (XOR with shifted bits)?

Answer:

Many hashCode implementations put entropy in the high bits. Indexing uses the low bits (& (n - 1)). Mixing spreads high bits downward so keys do not all pile into a few buckets.

Question 4​

Is HashMap thread-safe?

Answer:

No. Concurrent put can lose entries, resize incorrectly, or (historically) form a loop in a bin. I use ConcurrentHashMap or confine the map to one thread. Hashtable is not the answer.

Question 5​

Can I use a JPA entity as a HashMap key?

Answer:

Only with a stable equals/hashCode that does not change after insert (typically a UUID assigned at construction, not a generated id that appears after flush). Lazy collections must not participate. Prefer a value key (orderId) over the entity.

Memory sentences​

Hash picks the bucket; equals confirms the key; collisions list, then tree.

Expected O(1), not guaranteed O(1).

A mutated key stays in the old bucket.

Next: Week 6 Day 4 — Fail-fast Iterators