Explain map.put() internal flow.

Hook: Interviewers ask this because put() looks tiny, but in HashMap it hides hashing, collision handling, and resize logic.

Question: Explain map.put() internal flow.

Answer: The exact flow depends on the Map implementation, but the classic interview answer is HashMap.put(). It computes a hash for the key, finds a bucket, checks whether the key already exists with equals(), and either overwrites the old value or inserts a new node. If too many keys land in one bucket, Java 8+ can turn that bucket into a balanced tree for faster lookup.

Interview-Ready Answer: I would say: map.put() in HashMap first hashes the key, then uses that hash to pick a bucket, and then either updates an existing key or adds a new node if the key is not already present. Collisions are handled inside that bucket, and in Java 8+ a long collision chain can be treeified, while a growing map may resize when it crosses its load threshold. So the average insert is O(1), but bad hashing or lots of collisions can make it slower.

Big picture

In Java, Map is an interface, so the real flow depends on the implementation. In interviews, people usually mean HashMap.put(), because that is where hashing and collision handling matter most. A bucket is just one slot in the internal array; a collision means two different keys land in the same bucket.

How HashMap.put() works under the hood

1. Hash the key. Java calls the key’s hashCode() and spreads the bits so keys distribute better. This is why a good hashCode() is critical.
2. Initialize if needed. If the table is empty, HashMap allocates it on first insert. The default initial capacity is 16 and the default load factor is 0.75, so the first resize threshold is 12.
3. Find the bucket. It computes the index with (n - 1) & hash. This fast bit operation works because the capacity is kept as a power of two.
4. If the bucket is empty, insert. A new node is created and stored in that slot.
5. If the bucket is not empty, compare keys. Java first checks the first node, then walks the chain. It uses equals() to decide whether the key already exists. Same key means replace the value and return the old value.
6. Handle collisions. If the key is different but hashes into the same bucket, the new node is linked into that bucket. In Java 8+, if the bucket gets long enough, it can become a red-black tree, which is a balanced binary tree that keeps lookups faster.
7. Resize when needed. If a new mapping makes size exceed threshold = capacity * loadFactor, the table grows, usually by doubling. For the default map, that means resizing after the 13th entry.
8. Return the old value. put() returns the previous value for that key, or null if there was no previous mapping.

Quick comparison of common map types

Performance and edge cases

• Average time: O(1). Worst case: O(n) with heavy collisions, or O(log n) once a bucket is treeified.
• Resize cost: expensive in that moment because entries are redistributed, but amortized insert time stays close to O(1).
• Null key: HashMap allows one null key and many null values; the null key is treated specially and lands in bucket 0.
• Mutable key gotcha: if a key’s fields used by equals() or hashCode() change after insertion, future lookups can fail.
• Structural changes: adding a new mapping increases modCount, which helps fail-fast iterators detect unexpected changes; replacing an existing value usually does not.
• Thread safety: plain HashMap is not thread-safe; concurrent put() without coordination can lose updates or corrupt behavior.

Memory-wise, the main point is simple: put() is not just store-and-forget. It is hash, locate, compare, possibly grow, then return the old value.

Real-world story

Imagine a checkout service that keeps a HashMap of SKU to pricing rule. Every cart update does a put() to refresh promo data before calculating totals. One day, a developer uses a mutable object as the key and changes one of its fields after insertion. The map still contains the entry, but lookups start missing because the key now points to a different hash bucket. Users see wrong totals, logs show sudden cache misses, and the checkout team chases a ghost bug until they realize the key contract was broken. The lesson: put() is fast only when keys are stable and well-designed.

Follow-up & Tricky Questions:

• What does put() return? It returns the previous value for that key, or null if the key was not mapped before. Watch out: null can also mean the key existed with a null value.
• How are collisions handled? HashMap checks equals() inside the bucket. It uses a linked list first, and in Java 8+ a long bucket can become a tree.
• When does resize happen? After inserting a new mapping, if size becomes greater than capacity * loadFactor. With defaults, that means after the 12th entry is already there and the 13th goes in.
• Why is capacity a power of two? So the bucket index can be computed with a fast bit mask: (n - 1) & hash. That is faster than using modulo each time.
• Why do we need equals() if we already have hashCode()? Hashes only narrow the search to a bucket. equals() confirms whether two keys are logically the same key.
• Is HashMap thread-safe? No. If multiple threads call put() concurrently, use ConcurrentHashMap or external synchronization.
• Does Java 8 change collision handling? Yes. Java 8 introduced tree bins for long collision chains, which reduces worst-case lookup from linear to logarithmic time in those buckets.
• Does put() on the same key count as a structural change? Usually no. Replacing a value updates the mapping without changing the shape of the table, so it typically does not bump modCount the way a new entry does.
• If two keys have the same hash code, are they the same key? No. Equal hash codes only mean they share a bucket; equals() still decides whether they are actually the same mapping.

Common Mistakes:

• Thinking put() only inserts. Correction: it can also overwrite an existing value and return the old one.
• Using == mentally for key matching. Correction: HashMap uses hashCode() first and equals() to confirm key equality.
• Ignoring poor hash codes. Correction: bad distribution creates long buckets, which slows down put() and get().
• Mutating keys after insertion. Correction: keys should be stable while they live in the map, or lookups may break.

Memory Hook: Think of HashMap.put() like a mailroom: the hash finds the shelf, equals() finds the exact box, collisions stack boxes on the same shelf, and resize adds more shelves.

Cheat Sheet:

• Map is an interface; HashMap.put() is the usual interview target.
• Default capacity is 16, load factor is 0.75, default threshold is 12.
• Bucket index uses (n - 1) & hash.
• Same key means overwrite and return old value.
• Collision means same bucket, different key.
• Java 8+ can treeify long buckets.

Practice Tasks:

• Write a custom key class and prove that equal objects overwrite each other.
• Force collisions with a bad hashCode() and observe that the map still works, but more slowly.
• Mutate a key after insertion and watch lookup fail; then fix it by making the key immutable.