How do initial capacity and load factor affect a HashSet's performance, and how would you size one for a known number of elements?
answer
- Capacity = bucket count (power of two); load factor default 0.75
- Resize doubles the array + rehashes all => O(n)
- Pre-size to ceil(n / 0.75) to avoid resizes
- A Java 19 factory on HashSet itself
- Passing n as capacity may still resize
basics
~10 sA HashSet doubles its bucket array and re-buckets every element once its size exceeds capacity times load factor. For a known count, use HashSet.newHashSet(n) (Java 19+) to avoid that work; oversizing slows iteration.
solid answer
~50 sHashSet is backed by a HashMap with an internal bucket array. Capacity is the number of buckets; load factor (default 0.75) is the fullness ratio that triggers a resize. When size exceeds capacity times load factor, the array doubles and every element is rehashed into the new buckets — an O(n) operation. If you keep inserting into a default-sized set you may trigger several such resizes. When you know the target size n, use HashSet.newHashSet(n) (Java 19+), which computes the capacity as ceil(n / 0.75); the older idiom is new HashSet<>((int)(n / 0.75f) + 1). The int constructor takes a capacity, not an element count. A lower load factor reduces collisions at the cost of memory; a higher one saves memory but increases collision chains. Don't oversize either: iteration takes time proportional to size plus capacity.
code
java · 13 linesint n = 1_000;
// Naive: starts at 16 buckets, resizes 7 times while filling.
Set<String> naive = new HashSet<>();
// Pre-19 idiom: enough buckets so no resize occurs.
Set<String> sized = new HashSet<>((int) (n / 0.75f) + 1);
// Java 19+: clearest intent, sized for n elements.
Set<String> modern = HashSet.newHashSet(n);
// Common BUG: 1,000 rounds to 1,024 buckets, threshold 768, so the 769th add resizes:
Set<String> wrong = new HashSet<>(n);go deeper
Aware that a HashSet can grow and that giving an initial capacity can help for large sets.
Explains load factor, the resize-and-rehash cost, and pre-sizing with n / 0.75.
Knows the power-of-two index trick, the threshold formula, the n-vs-capacity pitfall, and the Java 19 HashSet.newHashSet factory; can reason about the time/space trade-off.
Decides when sizing matters (hot paths, large known counts), profiles resize churn and transient memory, and sets idioms/utilities for the team to avoid the capacity pitfall.
## The internal array A HashSet stores elements in its backing HashMap's **bucket array** — a plain array where each slot (bucket) can hold one or more elements that hashed to that index. Two numbers govern it: - **Capacity**: the number of buckets (the array length). It is always a **power of two** internally (so `HashMap` can map a hash to an index with a fast bitwise `hash & (capacity - 1)` instead of a modulo). - **Load factor**: a ratio, **default 0.75**, that decides how full the array may get before it grows. The **threshold** = `capacity * loadFactor`. ## Resizing (rehashing) When the number of elements **exceeds the threshold**, the set **resizes**: it allocates a new array of **double** the capacity and redistributes ("rehashes") every existing element into the new buckets. Rehashing touches all n elements, so a single resize is **O(n)**, though it reuses the hash stored in each entry rather than calling `hashCode()` again. One other trigger exists: in a table under 64 buckets, adding to a bin that already holds 8 nodes forces a resize instead of making a tree. If you start with the default capacity (16, threshold 12) and add 1,000 elements without pre-sizing, you'll trigger seven resizes — at the 13th, 25th, 49th, … element. Each one re-buckets everything. The amortised cost of inserts is still O(1), but you pay avoidable bursts of work, and the old and new bucket arrays coexist during each grow. ## Load factor trade-off - **Lower load factor** (e.g. 0.5): the array stays sparser, so fewer collisions, faster lookups — but more wasted memory and earlier resizes. - **Higher load factor** (e.g. 0.9): denser array, less memory — but longer collision chains, slower lookups. - **0.75 is the tuned default** balancing time and space; you rarely need to change it. ## Oversizing costs iteration Iterating a HashSet takes time proportional to **size plus capacity**, because empty buckets are walked too. Its Javadoc calls it "very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important". A `LinkedHashSet` is less exposed, since its iteration time does not depend on capacity. ## Sizing for a known count If you know you'll store **n** elements and want to avoid any resize, you need capacity such that `capacity * loadFactor >= n`, i.e. `capacity >= n / loadFactor`. With the default 0.75: ``` initialCapacity = ceil(n / 0.75) ``` Before Java 19 the common idiom was `new HashSet<>((int)(n / 0.75f) + 1)`. The constructor rounds the value up to the next power of two for you. Since Java 19, so on 25 LTS and 27 alike, `HashSet.newHashSet(n)` computes that capacity directly, and `LinkedHashSet.newLinkedHashSet(n)` does the same; the constructors' Javadoc points to them. The capacity is "generally large enough" for `n` elements without resizing. | Created for 1,000 elements | Buckets when full | Resizes | |---|---|---| | `new HashSet<>()` | 2,048 | 7 | | `new HashSet<>(1000)` | 2,048 | 1, at the 769th add | | `new HashSet<>(1334)` | 2,048 | 0 | | `HashSet.newHashSet(1000)` | 2,048 | 0 | > Pitfall: `new HashSet<>(n)` takes a capacity, not an element count. Whether it resizes depends on where `n` falls against a power of two: `new HashSet<>(1000)` gets 1,024 buckets and a threshold of 768, while `new HashSet<>(300)` gets 512 buckets and a threshold of 384, so it never resizes for 300. Divide by the load factor, or use the factory, rather than relying on the rounding. ## When it matters For small sets it's noise. It matters for **large, known-size** sets built in hot paths or loops, where eliminating several O(n) rehashes and the transient memory spikes gives a measurable, predictable win.
- Why is the bucket array always a power of two?Because the index is computed as hash & (capacity - 1), a bitwise AND that reaches every bucket only when capacity is a power of two, and it replaces a modulo. The cost is that the mask sees only the low bits, so HashMap first XORs the hash code's high 16 bits into the low 16 to reduce collisions.
- Does a higher load factor ever help?Yes, when memory is tight and lookups are infrequent: a higher load factor packs more elements per bucket, saving array memory at the cost of longer collision chains and slower gets/contains. The 0.75 default is the general-purpose sweet spot.
It's like a parking lot. Load factor 0.75 means once it's three-quarters full, management builds a bigger lot and re-parks every car. If you know 1,000 cars are coming, you build the big lot once instead of expanding again and again.
- Passing the target size directly as initial capacity, forgetting to divide by load factor
- Believing resizing is O(1) or free
- Thinking changing load factor changes correctness rather than just time/space trade-off
- Assuming capacity stays exactly what you pass (it's rounded to a power of two)
- Assuming a huge initial capacity is free, when iteration time grows with capacity
- HashSet.newHashSet and LinkedHashSet.newLinkedHashSet
- Java 19
Assumes JDK 27. HashSet.newHashSet and LinkedHashSet.newLinkedHashSet arrived in JDK 19, so they are on 25 LTS too; on older JDKs use the manual capacity formula.
context
- HashSet (Java SE 27 & JDK 27)docs.oracle.com