Hash Collision in HashMap.

Hash collisions are where a simple map starts behaving like a real-world filing cabinet under pressure.

Question: Hash Collision in HashMap.

Answer: A hash collision happens when two different keys land in the same bucket of a HashMap. Java does not lose either entry; it keeps both in that bucket and uses equals() to find the exact one. So the main effect of a collision is usually slower lookup, not incorrect storage.

Interview-Ready Answer: I would say a hash collision in HashMap means two different keys map to the same bucket index. HashMap handles that by storing both entries in the same bucket and then checking equals() to pick the right key. In Java 8 and later, if one bucket gets too crowded, HashMap can switch that bucket from a linked list to a red-black tree, which keeps lookups from getting too slow.

Detailed Explanation: A HashMap uses an array of buckets. A bucket is just a slot that can hold one or more entries. A collision happens when two keys compute to the same bucket index, even if the keys are different. That is normal and expected; the map is designed to handle it.

How HashMap resolves a key

1. It calls hashCode() on the key, then mixes the bits with h ^ (h >>> 16) so weak low bits do less damage.
2. It finds the bucket with (n - 1) & hash, where n is the table size. This works because HashMap keeps the capacity as a power of two.
3. If the bucket is empty, the entry is stored right there.
4. If the bucket already has entries, HashMap compares hashes first, then uses equals() to find the exact key. If the key matches, the value is replaced; if not, the new node is appended to that bucket.
5. If too many entries pile up in one bucket, Java 8+ can turn that bucket into a red-black tree, which is a self-balancing binary tree. That gives faster searches when collisions are heavy.
6. On get(), HashMap repeats the same path: hash, index, bucket scan, then equals(). That is why a bad hashCode() hurts every read and write.
7. When the map grows beyond its threshold, it resizes. With default settings, the first allocated table is 16 buckets, and the resize threshold is 12 because 16 × 0.75 = 12. Resize doubles the table and redistributes entries, but it does not magically fix a poor hash function.

List bucket vs tree bucket

Shape	When used	Lookup	Trade-off
Linked list	Small collision chain	O(k)	Simple and small
Red-black tree	8+ entries and table size 64+	O(log k)	More memory, better worst case

Why collisions matter

In the average case, get() and put() are O(1). With many collisions, a list bucket can degrade toward O(n) for that bucket, while a tree bucket keeps it closer to O(log n). Space is still O(n) overall because every entry must be stored somewhere.

Edge cases interviewers love

• Different objects can share a hash. That is allowed. The contract is that equal objects must have the same hash, not that different objects must have different hashes.
• Mutable keys are dangerous. If you change a field that affects hashCode() after insertion, the key may become hard to find because it now points to a different bucket.
• null key is allowed. HashMap stores it in bucket 0.
• Treeification is not instant for tiny maps. If the table is still small, HashMap often resizes first instead of treeifying, because a bigger table may solve the crowding cheaper than a tree.

Memory model: collisions are like many names assigned to the same mailbox; equals() is the clerk who opens the mailbox and hands you the right letter.

Real-World Story: In an e-commerce checkout service, the team used a HashMap to cache pricing data by PromotionKey. A refactor accidentally made hashCode() depend on only campaignId, while equals() still used both campaignId and customerId. During a flash sale, thousands of customers collided into the same few buckets, and checkout latency jumped from a few milliseconds to hundreds.

The symptoms were classic: CPU went up, profiler samples showed time inside HashMap.getNode(), and users saw spinner delays and occasional timeouts when applying coupons. The fix was to make the hash spread across the full key, add tests that compare equals() and hashCode() behavior, and avoid mutable fields in map keys.

Follow-up & Tricky Questions:

• What happens when two keys have the same hashCode but are not equal? They can both live in the same bucket. HashMap uses equals() to decide whether to replace an existing value or keep a separate entry.
• Why does HashMap use power-of-two capacity? It makes bucket selection fast with (n - 1) & hash instead of a slower modulo operation, and it helps resize redistribute entries efficiently.
• When does HashMap turn a bucket into a tree? In Java 8+, a bucket is treeified after the chain gets long enough, typically around 8 entries, but only if the table is already at least 64 slots wide. Otherwise it prefers resizing first.
• How do bad hashCode implementations affect performance? They cluster entries into a few buckets, so each lookup has to scan more nodes. That can turn expected O(1) operations into much slower work on hot paths.
• How does collision handling differ in ConcurrentHashMap? The idea is similar: bins still hold multiple entries and can treeify, but the class is built for concurrency, so it adds thread-safety mechanics that HashMap does not have.
• Does resizing remove collisions? Not completely. Resizing spreads entries across more buckets, but if the hash function is poor or keys are naturally similar, collisions can still happen after the resize.
• Tricky: If two keys have the same hashCode, will one overwrite the other? No. Only equals() decides whether it is the same logical key. Same hash alone just means they share a bucket.
• Tricky: Does HashMap check equals first or hashCode first? It checks hashCode() first to find the bucket, then equals() only among candidates in that bucket. That is the whole reason hash lookups are fast on average.
• Tricky: Is a collision always a bug? No. Collisions are normal and unavoidable in real hash tables. A bug is usually a poor hash function, a mutable key, or forgetting that equal objects must share the same hash.

Common Mistakes:

• Mistake: Thinking a collision means data is lost. Correction: The entries still exist; HashMap just stores them in the same bucket and separates them with equals().
• Mistake: Saying different objects must have different hash codes. Correction: That is impossible to guarantee. The real contract is: equal objects must have the same hash code.
• Mistake: Ignoring key immutability. Correction: Never mutate fields that participate in hashCode() or equals() after putting the key into the map.
• Mistake: Forgetting the 8 and 64 treeify rule. Correction: Long collision chains may become trees in Java 8+, but only after the bucket is crowded and the table is large enough.

Memory Hook: Think of HashMap as a hotel: the hash is the room number, collisions mean two guests got the same room, and equals() is the front desk checking who really belongs there. Remember the 8-64 rule: at about 8 guests in one room and 64 rooms total, the hotel upgrades from a line to a tree.

Cheat Sheet:

• Collision = different keys land in the same bucket.
• HashMap uses hashCode() first, then equals().
• Default load factor is 0.75; default logical capacity starts at 16.
• Java 8+ can treeify a crowded bucket to keep lookups fast.
• Bad or mutable keys are the most common real-world cause of pain.
• Average lookup is O(1); worst case is worse, but trees help.

Practice Tasks:

• Create a key class with a constant hashCode() and confirm that three different keys still work in one HashMap.
• Write a key class with a mutable field, insert it into a map, mutate the field, and observe why retrieval fails.
• Implement equals() and hashCode() correctly for a custom EmployeeId class, then write a small test that proves equal objects map to one entry.