Explain capacity, load factor, and resizing in HashMap. What is the default load factor and why?
answer
- Capacity=buckets (pow2, default 16); load factor=0.75
- threshold = capacity x loadFactor = 12 by default
- Exceed threshold -> resize doubles capacity
- 0.75 = space/time balance (Poisson: long chains rare)
- Pre-size with N/0.75; Java 8 low/high split, no rehash
basics
~20 sCapacity is the number of buckets (default 16). Load factor (default 0.75) is how full the map gets before it grows. When entries exceed capacity x load factor (the threshold), the map doubles its capacity and re-spreads entries so buckets stay short and lookups stay fast.
solid answer
~50 sCapacity is the size of the bucket array, always a power of two, defaulting to 16. The load factor (default 0.75) controls the space/time trade-off: the threshold = capacity x loadFactor (12 by default). When the number of entries exceeds the threshold, resize() doubles the capacity and redistributes entries. 0.75 is a deliberate balance: lower values waste memory but reduce collisions; higher values save memory but lengthen chains. Resizing is expensive (it allocates a new array and moves entries), so if you know the final size you should pre-size the map. To avoid any resize for N entries, pass an initial capacity of about N / 0.75, e.g. new HashMap<>((int)(N / 0.75f) + 1). Java 8 made resize cheaper with a clever split: because capacity is a power of two, each entry either keeps its index or moves to index + oldCapacity, decided by one bit, so hashes are not recomputed.
code
java · 9 lines// Pre-size to hold ~1000 entries without any resize:
int expected = 1000;
Map<String, User> users = new HashMap<>((int) (expected / 0.75f) + 1); // capacity rounded up to next power of two
// JDK 19+ convenience that does the math for you:
// Map<String, User> users = HashMap.newHashMap(1000);
// Default knobs:
// initial capacity = 16, load factor = 0.75 -> first resize after 12 entriesgo deeper
Knows default capacity 16 and that the map grows when it gets too full; aware of load factor 0.75 by name.
Computes the threshold, explains the space/time trade-off behind 0.75, and pre-sizes a map to avoid resizes.
Explains the power-of-two invariant, the (n-1)&hash indexing, and the Java 8 low/high resize split without rehashing.
Reasons about resize cost at scale, sizing strategy for hot paths, and trade-offs of tuning load factor for memory- vs latency-sensitive systems.
## Definitions first - **Capacity**: the number of buckets in the internal array (the *table*). HashMap keeps capacity a **power of two** (16, 32, 64, ...). Default initial capacity is **16**. - **Size**: the number of key-value entries actually stored (returned by `size()`). Do not confuse size (entries) with capacity (buckets). - **Load factor**: a `float` measuring how full the map is allowed to get before growing. Default **0.75**. - **Threshold**: the entry count that triggers growth, computed as `capacity x loadFactor`. With defaults that is `16 x 0.75 = 12`. ## What happens as you add entries Each `put` of a new key increments size. When size **exceeds** the threshold, the map calls `resize()`. Resizing: 1. Allocates a new table of **double** the capacity (16 -> 32 -> 64 ...). 2. Recomputes the new threshold (`newCapacity x loadFactor`). 3. Moves every existing entry into the new table. This keeps the average number of entries per bucket low, which is what preserves near-O(1) lookups. ## Why 0.75? The load factor is a **space-time trade-off**: - A **low** load factor (e.g. 0.5) means the map grows sooner, so buckets stay very short (fewer collisions, faster lookups) but you waste memory on empty buckets and resize more often. - A **high** load factor (e.g. 0.95) means fewer/later resizes and less memory, but buckets get crowded, collisions rise, and lookups slow down. 0.75 is the documented sweet spot: under a roughly uniform hash, the chance of long collision chains stays small while memory overhead is acceptable. (The JDK notes the Poisson distribution of bucket occupancy makes long chains rare at 0.75.) ## The Java 8 low/high split (why resize got cheaper) Because capacity is a power of two, the bucket index is computed as `(capacity - 1) & hash` (a bitmask). When capacity doubles, exactly **one new bit** of the hash becomes significant. So for each old entry, you only test that one bit: - bit is 0 -> the entry stays at its **same index** in the new table; - bit is 1 -> it moves to index `oldIndex + oldCapacity`. Thus each old bucket splits into at most two destination buckets (a *low* list and a *high* list) **without recomputing hashCode** for any key. This also preserves relative order within the split lists. ## Pre-sizing to avoid resizes Resizing copies all entries, so repeated growth while building a large map is wasteful. If you know you will store N entries and want **zero** resizes, set the initial capacity to at least `N / loadFactor`. A common idiom: `new HashMap<>((int)(N / 0.75f) + 1)`. The constructor rounds the requested capacity up to the next power of two (via `tableSizeFor`). (Guava's `Maps.newHashMapWithExpectedSize` and, since JDK 19, `HashMap.newHashMap(N)` do this for you.) ## Key numbers to remember Default capacity 16; default load factor 0.75; default threshold 12; growth = double; index = `(capacity-1) & hash`.
- If you create new HashMap<>(20), what is the actual initial capacity?32. The requested capacity is rounded up to the next power of two by tableSizeFor, so 20 becomes 32.
- You will insert 1000 entries. What initial capacity avoids resizing?At least 1000 / 0.75 ~= 1334, rounded up to the next power of two = 2048. Passing new HashMap<>(2048) (or 1334, which rounds to 2048) avoids resizes.
saying these in an interview costs you the question
- Saying default capacity is 10 (that is ArrayList, not HashMap)
- Confusing size (entries) with capacity (buckets)
- Thinking resize recomputes every hash in Java 8 (the bit-split avoids it)
- Claiming capacity can be any number (it is rounded to a power of two)
- Believing load factor 0.75 means it resizes at 75 entries regardless of capacity