Stage 4: HashMap internals, lesson 3 of 13

HashMap internals 3: How put() works

Intermediate3 min readall versions
Explain it forThe essentials plus production detail and pitfalls.

What put(key, value) does in Java 8 and later:

  1. Hash the key: hash = spread(key.hashCode()). A null key gets hash 0.
  2. Create the table if this is the first put (16 buckets).
  3. Find the bucket: index = hash & (n − 1). If it's empty, a new node goes there, and put is nearly done.
  4. Otherwise walk the bucket. For each node: if node.hash == hash and the keys are equal (== or equals()), it's the same key: replace the value and return the old one.
  5. No match: append a new node at the tail of the bucket. If the bucket already held 8 nodes, it's turned into a tree (part 11).
  6. Increase size. If size is now greater than the threshold (capacity × load factor, 12 at first), resize (part 9).
  7. Return the previous value, or null if the key was new.
HashMap lab

Example

Java
Map<String, Integer> stock = new HashMap<>();

System.out.println(stock.put("pen", 10));   // null   new key
System.out.println(stock.put("pen", 12));   // 10     same key: value replaced, old value returned
System.out.println(stock.get("pen"));       // 12
System.out.println(stock.size());           // 1      still one entry

stock.put(null, 0);                         // one null key is allowed; it lives in bucket 0
stock.putIfAbsent("pen", 99);               // does nothing: "pen" is already there

Common mistake

Thinking put() with an existing key adds a second entry. It replaces the value and returns the old one.

Under the hood

Comparing the stored int hash first is cheap and rules out most non-matches before the (possibly expensive) equals() call; that's another reason equal objects must have equal hash codes. putIfAbsent, computeIfAbsent and merge do "check, then put" in a single bucket walk instead of two separate calls. Every structural change also increments modCount, which is how iterators detect changes (see "Fail-fast vs fail-safe").

Check yourself

After put("pen", 10), what does put("pen", 12) return?

How this connects

Part of HashMap internals, part by part.

Was this lesson helpful?

Finished reading? Mark it complete to track your progress.