HashMap Resize and Load Factor — Java Interview Guide

Load factor is the fraction of capacity that can fill up before HashMap grows — default 0.75. The threshold is capacity × loadFactor; once size exceeds it, HashMap doubles capacity and rehashes every existing entry into the new, larger table.

Resizing isn't a cheap copy — every entry's bucket index depends on hash(key) & (capacity - 1), so a bigger capacity means most entries land in a different bucket. HashMap has to walk every existing entry and re-insert it into the new table, which is why a resize is O(n) even though put() is normally amortized O(1).

A resize can also change the order entries come out in during iteration. HashMap never guaranteed iteration order, but because bucket index depends on capacity, the exact same entries can walk out in a different order before and after a resize. Code that happens to "work" because of an incidental order will break the moment the map crosses a resize threshold — if order matters, use LinkedHashMap (insertion order) or a TreeMap (sorted), don't rely on HashMap's.

Load factor interacts with a second Java 8+ mechanism: treeification. If a single bucket collects 8 or more colliding entries and the table capacity is at least 64, that bucket's linked list converts to a red-black tree, turning worst-case lookup in that bucket from O(n) to O(log n). A resize can also untreeify a bucket back to a list once it drops to 6 entries after keys redistribute. This only kicks in under pathological hashing (poor hashCode() or an adversarial key set) — with a well-distributed hash, buckets rarely get anywhere near 8 entries, so most HashMaps never treeify at all.

ConcurrentHashMap resizes differently. A plain HashMap resize is a single-threaded stop-the-world rehash of every entry. ConcurrentHashMap instead marks the table as transferring and lets any thread that calls put()/get() during the resize help migrate a chunk of buckets (transferIndex, ForwardingNode) — readers never block, and multiple writer threads share the rehash cost instead of one thread paying for all of it. The trade-off is more bookkeeping per resize, which is why ConcurrentHashMap benefits from pre-sizing even more than HashMap does in write-heavy concurrent code.

Capacity is always a power of two, even if you don't ask for one. new HashMap<>(1000) doesn't create a table of exactly 1000 buckets — the constructor's tableSizeFor() rounds any requested capacity up to the next power of two (1000 → 1024), because the fast bucket-index calculation hash(key) & (capacity - 1) only behaves correctly (as a substitute for the slower % modulo) when capacity - 1 is all 1-bits, which is only true for powers of two. Pre-sizing math should account for this: new HashMap<>(1366) for ~1000 entries at 0.75 load factor actually allocates a 2048-bucket table, not a 1366-bucket one — still correct, just worth knowing so a "precisely sized" map isn't a surprise in a memory profiler.

HashSet is a HashMap under the hood — every HashSet field is backed by an internal HashMap<E, Object>, with each added element stored as a key mapped to a single shared dummy value (PRESENT). Every rule covered here — load factor, threshold, resize cost, treeification, iteration-order instability — applies identically to HashSet, because add(), contains(), and size() are just thin wrappers around the underlying map's put(), containsKey(), and size(). A new HashSet<>(expected * 4 / 3 + 1) pre-sizing call is solving the exact same resize problem as pre-sizing a HashMap.

Keywords they're listening for: