skip to content

How do initial capacity and load factor affect a HashSet's performance, and how would you size one for a known number of elements?

level: seniorimportance: should knowfreq 48%

answer

  1. Capacity = bucket count (power of two); load factor default 0.75
  2. Resize doubles the array + rehashes all => O(n)
  3. Pre-size to ceil(n / 0.75) to avoid resizes
  4. new HashSet<>((int)(n/0.75f)+1) or HashMap.newHashMap(n) (Java 19+)
  5. Passing n directly as capacity still resizes around 0.75n

basics

~20 s

A HashSet has internal buckets. As it fills past a threshold it grows and rehashes, which is costly. If you know how many items you'll add, give it a starting capacity so it avoids repeated resizing.

solid answer

~50 s

HashSet 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, pre-size it: capacity should be at least n / loadFactor, rounded up to a power of two. Java's idiom is new HashSet<>((int)(n / 0.75f) + 1), and Java 19+ adds HashMap.newHashMap(n) for the same intent. A lower load factor reduces collisions and speeds lookups at the cost of memory; a higher one saves memory but increases collision chains. Right-sizing avoids resize churn and stabilises performance.

code

java · 13 lines
java
int n = 10_000;

// Naive: starts at 16, resizes ~10 times while filling.
Set<String> naive = new HashSet<>();

// Right-sized: enough buckets so no resize occurs.
Set<String> sized = new HashSet<>((int) (n / 0.75f) + 1);

// Java 19+: clearest intent — "hold n elements without resizing".
Set<String> modern = new HashSet<>(HashMap.newHashMap(n).keySet().size()); // or build from newHashMap directly

// Common BUG: this still resizes around 0.75 * n = 7500 elements:
Set<String> wrong = new HashSet<>(n);

go deeper

for a junior

Aware that a HashSet can grow and that giving an initial capacity can help for large sets.

for a middle

Explains load factor, the resize-and-rehash cost, and pre-sizing with n / 0.75.

for a senior

Knows the power-of-two index trick, the threshold formula, the n-vs-capacity pitfall, and the Java 19 newHashMap factory; can reason about the time/space trade-off.

for a principal

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 the JVM 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)**. If you start with the default capacity (16, threshold 12) and add 1,000 elements without pre-sizing, you'll trigger resizing roughly every time the array doubles — at ~12, 24, 48, … elements. Each one re-buckets everything. The amortised cost of inserts is still O(1), but you pay avoidable bursts of work and temporary double memory 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. ## 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) ``` The common idiom is `new HashSet<>((int)(n / 0.75f) + 1)`. The constructor rounds the value up to the next power of two for you. Since Java 19 there is a clearer factory: `HashMap.newHashMap(n)` (and the set built around it) computes the right capacity for *n mappings without resizing* directly — use it when available. > Pitfall: `new HashSet<>(n)` (passing n directly as capacity) is a common mistake — that sets capacity to n, but the 0.75 threshold means it still resizes around 0.75n. You must divide by the load factor. ## 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 only correctly distributes bits across all buckets when capacity is a power of two. It's far faster than a modulo and avoids clustering.
  • 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 three times.

saying these in an interview costs you the question

  • 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)

context

resolving links…