HashMap internal working.

A HashMap is like a row of mailboxes: the hash chooses the street, and equals() chooses the exact apartment. Interviewers love this question because it reveals whether you understand both the public API and the hidden rules that keep lookups fast.

Question: HashMap internal working.

Answer: HashMap stores key-value pairs in an array of buckets. It uses hashCode() to pick a bucket and equals() to find the exact key inside that bucket. In modern Java, collisions start as a short linked list and may become a red-black tree when a bucket gets too crowded, which keeps performance much better than a long linear scan.

Interview-Ready Answer: "I would explain that HashMap first turns a key into a hash, then maps that hash to an array bucket using a very fast bit operation. If two keys land in the same bucket, Java uses equals() to find or replace the right entry. In Java 8 and later, a heavily collided bucket can turn into a red-black tree, so average operations stay near O(1), and the worst case inside that bucket improves to about O(log n)."

What HashMap really is

HashMap is a key-value container backed by an array of buckets. A bucket is just a slot that can hold one or more entries. In Java 8+, each entry is a Node with a stored hash, key, value, and a link to the next node. HashMap does not keep keys sorted or in insertion order; its only goal is fast lookup by key.

How put and get work under the hood

1. Java takes the key’s hashCode(). This can be any 32-bit integer, including a negative one.
2. It mixes the high bits into the low bits with a small spread function (h ^ (h >>> 16)). This matters because bucket selection mostly uses the lower bits.
3. It computes the bucket index with (n - 1) & hash, where n is the table size. This works because the table size is always a power of two.
4. If the bucket is empty, the new node is stored there directly.
5. If the bucket already has entries, HashMap checks the stored hash first, then calls equals(). If the key matches, the value is replaced; otherwise, the new node is added to that bucket.
6. If the bucket gets too long, Java 8+ can convert that bucket from a linked list into a red-black tree, which is a balanced binary search tree that keeps height small.
7. After insertion, if size crosses the threshold, HashMap resizes: the backing array grows, usually by doubling.

Why the capacity is a power of two

Using a power-of-two length lets HashMap replace slow modulo with a fast bit mask. That is why (n - 1) & hash is used instead of hash % n. It is also why resize is efficient: when capacity doubles, each entry either stays in the same bucket or moves by exactly the old capacity.

Collision handling and the Java 8 behavior

Collisions are normal. Two different keys can produce the same bucket index, so HashMap must compare keys inside the bucket. In Java 8+, small collisions stay as a linked list because that is cheap and simple. When a bucket gets very crowded, treeification can happen, but only if the table is already large enough; otherwise HashMap prefers resizing first.

Resize, load factor, and real numbers

Default initial capacity is 16, and default load factor is 0.75. That means the resize threshold is 12 entries at the default size, 24 at capacity 32, 48 at capacity 64, and so on. Resize is one of the most expensive operations because every entry must be examined and moved, so if you already know roughly how many items you will store, pre-sizing a HashMap can save time.

Performance and edge cases

• Average get, put, and remove: O(1).
• Worst case for one bucket: O(n) with a long list, or about O(log n) in a treeified bucket.
• Space: O(n), plus array overhead and node objects.
• HashMap allows exactly one null key and many null values.
• get(key) returning null can mean either "missing key" or "present with null value", so use containsKey() when you need to distinguish the two.
• If equals() and hashCode() do not follow the contract, lookups become unreliable.

Use HashMap when you want fast lookup by key and do not need ordering or built-in thread safety. If multiple threads write to it, use external synchronization or ConcurrentHashMap.

Real-world story

Imagine a checkout service in an e-commerce system keeping orderId -> OrderState in a HashMap so it can answer requests quickly. Most of the time it is perfect: one lookup, one update, done. But one day an engineer uses a mutable object as the key and changes one of its fields after the object is put into the map.

What goes wrong is painful: the entry is still in the map, but it is now effectively unreachable because the key’s hash and equality result no longer match the original bucket. The symptoms are confusing: get() returns null, containsKey() fails, the service starts creating duplicate orders, and logs show increasing cache misses even though the map size keeps growing. If the issue is also combined with a poor hashCode(), one bucket becomes hot, CPU rises, and p99 latency spikes during peak traffic.

The lesson is simple: keys should be effectively immutable, and a good hashCode() matters because it spreads traffic across buckets instead of turning one bucket into a traffic jam.

Follow-up & Tricky Questions:

• Why does HashMap use a power-of-two capacity? Because it can compute the bucket index with a fast bit mask instead of a slower modulo. It also makes resize cheaper because each entry usually stays put or moves by exactly the old capacity.
• What is the default load factor? It is 0.75. That is the balance Java chose between memory usage and collision rate; lower values waste space, and higher values increase collisions.
• Why do collisions still work correctly? Because HashMap does not rely on hash alone. It first checks the hash to find the bucket, then uses equals() to find the exact key inside that bucket.
• What changed in Java 8? Java 8 added tree bins for heavily collided buckets. Before that, collisions stayed as linked lists, which made bad hash patterns much slower.
• Why is HashMap not thread-safe? Because multiple threads can race while resizing or updating buckets, which can lose updates or corrupt structure. For concurrent writes, use ConcurrentHashMap or external locking.
• Can I rely on iteration order? No. If you need insertion order, use LinkedHashMap; if you need sorted keys, use TreeMap.
• Can two keys with the same hashCode() coexist? Yes. Same hash does not mean same key. If equals() says they are different, HashMap stores both entries in the same bucket.
• Does a negative hashCode() break HashMap? No. Java mixes and masks the hash, so negative values are fine.
• Does get() returning null always mean the key is absent? No. The key may be present with a null value, so containsKey() is the safe check.

Tricky / gotcha questions:

• Can HashMap store multiple null keys? No. It allows exactly one null key, because there is only one logical slot for the null key.
• If two objects are equal, can they have different hash codes? They should not. That breaks the contract and makes lookups unreliable.
• Is HashMap always O(1)? No. Average lookup is O(1), but resizing and heavy collisions make some operations slower.

Common Mistakes:

• Assuming hashCode() alone is enough. Correction: HashMap uses hashCode() to choose a bucket, then equals() to identify the exact key.
• Using mutable objects as keys. Correction: make keys effectively immutable, or the map may never find them again after a field changes.
• Expecting insertion order. Correction: HashMap does not promise order; use LinkedHashMap if order matters.
• Treating get() returning null as proof that the key is absent. Correction: a key can exist with a null value, so use containsKey() when needed.

Memory Hook: Think of HashMap as a postal system: hashCode() picks the street, equals() picks the house, resize adds more streets, and treeification is what happens when one street gets too crowded.

Cheat Sheet:

• Backed by an array of buckets.
• Default capacity is 16; default load factor is 0.75.
• Average get/put is O(1).
• Collisions are handled by bucket chaining; Java 8+ can treeify crowded buckets.
• Exactly one null key is allowed; many null values are allowed.
• Keys should have stable hashCode() and equals().

Practice Tasks:

• Write a custom key class with a bad hashCode() and observe how many collisions you create.
• Compare the iteration order of HashMap and LinkedHashMap with the same inserts.
• Pre-size a HashMap for 10,000 entries and compare it to the default constructor in a small benchmark.