ByteScrollGet the app
☰ Topics
hashmap-put13 / 200‹›
JAVA / COLLECTIONS3 minute read

What happens inside HashMap.put()?

Medium

put() hashes the key, folds the high bits into the low bits, and uses (n - 1) & hash to pick a bucket. Empty bucket: store it. Otherwise match by hash + equals() and replace, or append. Crowded buckets turn into trees; past 75% full the table doubles.

How it works

  1. Hash. put calls key.hashCode() and XORs the top 16 bits into the bottom 16 (h ^ (h >>> 16)). Keys whose hashes differ only in high bits still spread across a small table.
  2. Pick a bucket. Table length is always a power of two, so (length - 1) & hash is a cheap modulo.
  3. Empty bucket: the new node goes straight in.
  4. Occupied bucket: walk its nodes. A node with the same hash and an equals() key gets its value replaced, and put returns the old value. Otherwise the new node is appended.
  5. Treeify. A bucket with 8 or more nodes becomes a red-black tree, but only when the table has at least 64 slots. Smaller tables resize instead.
  6. Resize. Once the entry count passes capacity × loadFactor (16 × 0.75 = 12 by default), the table doubles. Each node either keeps its index or moves to index + oldCapacity.
yesnoyesnoyesnoyesput(key,value)h ^ (h 16)index = (n -1) & hashBucket empty?Insert nodeSame key?Replace valueAppend tochain8+ nodes andtable ≥ 64?Bucket becomesa treeOverthreshold?Double thetable
yesnoyesnoyesnoyesput(key,value)h ^ (h 16)index = (n -1) & hashBucket empty?Insert nodeSame key?Replace valueAppend tochain8+ nodes andtable ≥ 64?Bucket becomesa treeOverthreshold?Double thetable

Example

Example.javaJava
Map<String, Integer> stock = new HashMap<>();
stock.put("apple", 10);               // null: new key
Integer before = stock.put("apple", 7); // 10: value replaced
stock.put(null, 0);                   // allowed, lives in bucket 0

A key class without equals/hashCode breaks lookups:

Example.javaJava
class Sku { final String code; Sku(String code) { this.code = code; } }

Map<Sku, Integer> qty = new HashMap<>();
qty.put(new Sku("A1"), 5);
qty.get(new Sku("A1")); // null: identity hash puts it in another bucket

record SkuKey(String code) {} // records generate equals/hashCode, so lookups work

Edge cases

  • One null key is allowed; its hash is treated as 0.
  • Changing a field used by hashCode() after inserting the key strands the entry: it sits in the old bucket and lookups miss it.
  • Inside a tree bucket, nodes are ordered by hash, then by compareTo when keys are Comparable.
  • Presize when you know the count: HashMap.newHashMap(1_000) (Java 19+) avoids repeated resizing.

Common mistakes

  • Saying the map treeifies at 8 entries total. It's 8 in one bucket, and only once the table is 64+ slots.
  • Overriding equals() but not hashCode().
  • Expecting insertion order. Use LinkedHashMap for that.

Likely follow-up

"How is ConcurrentHashMap.put() different?" Empty bins are filled with a CAS, busy bins lock only their first node, there's no map-wide lock, and null keys or values are rejected.

Get every deep dive in the app

Coming soon to the App StoreComing soon to Google Play