A hash table holds 12,000 SKU entries in 16,384 buckets — what is its load factor, and does that value mean lookups are collision-free?
answer
- It is a ratio, not a count
- Two numbers the table already tracks
- Divide entries by buckets
- Ask what an average hides about single buckets
- Random scatter leaves many buckets empty
basics
~20 sLoad factor is entries divided by buckets: 12,000 over 16,384 is about 0.73. It measures average occupancy, not collision-freedom. With a good hash, roughly half those buckets sit empty and thousands of keys already share a bucket with someone.
solid answer
~40 sLoad factor is simply `entries / buckets`, so here it is `12000 / 16384 = 0.73`. It is an average occupancy figure and nothing more — it says nothing about any individual bucket, and it is not a collision count. If you model a good hash as scattering keys uniformly, the number of keys per bucket follows a Poisson distribution with mean 0.73: about 48% of buckets are empty, about 35% hold one entry, and the rest hold two or more. That is roughly four thousand colliding pairs in a table most people would describe as "three-quarters full". Collisions are the normal operating state of a hash table, not a symptom of one that is too full; load factor predicts how *expensive* those collisions get, not whether they exist.
code
pseudocode · 9 linesinsert(table, key, value):
if table.count + 1 > table.maxLoad * length(table.buckets):
grow(table) // rebuild with more buckets
i = hash(key) mod length(table.buckets)
bucket_insert(table.buckets[i], key, value)
table.count = table.count + 1
// count = 12000, length(buckets) = 16384 -> load factor = 0.73
// maxLoad = 0.75 -> no growth yet, though collisions already existgo deeper
Be ready to state the formula instantly — entries divided by buckets — and to compute it from two given numbers without hesitating. Then add the one sentence that separates you from a memoriser: it is an average, so collisions exist long before it approaches 1.
Explain the mechanism behind the average: with a good hash, per-bucket counts follow a random scatter, so roughly half the buckets are empty at occupancy 0.73 while others hold several entries. Connect the ratio to expected operation cost rather than to memory usage.
Show that you diagnose with the bucket-occupancy distribution, not the scalar. Two tables at the same load factor can behave very differently once key skew or a weak hash concentrates entries, and that is what actually shows up in tail latency.
Own the framing that load factor is a policy knob balancing memory against expected probe cost, and that it makes only a statistical promise. Where inputs may be adversarial or heavily skewed, the average is the wrong guarantee to design a latency budget around.
## The number itself A hash table stores entries in an array of **buckets**. The **load factor** (often written as the Greek letter alpha) is the ratio of stored entries to buckets: ``` load factor = entries / buckets ``` With 12,000 inventory entries in a 16,384-bucket table, that is `12000 / 16384 = 0.7324…`, usually quoted as "about 0.73" or "73% occupancy". That is the whole definition. It is a single scalar summarising crowding. It is deliberately cheap to compute — a table keeps a running entry count and knows its bucket count, so the value is available in constant time on every insert, which is exactly why implementations use it as their growth trigger. ## What it is not Three things it does **not** mean: - It is not a **memory-utilisation percentage** of the table's total footprint. Entries carry keys, values and per-entry overhead that live outside the bucket slot count. - It is not a statement about **any individual bucket**. Buckets are not filled in order; a bucket is chosen by the hash of the key. - It is not a **collision indicator**. This is the misconception the question is aimed at: "we are only at 0.73, so we are fine, collisions start when the table fills up." ## Why collisions are already everywhere at 0.73 Model an ideal hash as throwing every key into a uniformly random bucket. The number of keys landing in a given bucket is then approximately Poisson-distributed with mean equal to the load factor. At mean 0.73: | keys in a bucket | share of buckets | |---|---| | 0 | ~48% | | 1 | ~35% | | 2 | ~13% | | 3 or more | ~4% | So nearly half of the 16,384 buckets are never touched, while about 2,800 buckets hold two or more entries. The expected number of colliding **pairs** is about `n(n-1)/2m` = `(12000 × 11999 / 2) / 16384`, roughly 4,400 pairs. A perfectly good hash function produces all of that; nothing is broken. Collisions also appear absurdly early. The birthday argument says that with `m` buckets and randomly distributed keys, the first collision is expected after roughly `1.25 × sqrt(m)` insertions — for 16,384 buckets, around 160 keys, a load factor below 0.01. If your mental rule is "a collision means the table needs to grow", you would be growing after the 160th SKU. ## What the number does predict Cost. Load factor is the single input that turns a hash table's asymptotic promise into a real number: - With **chaining**, each bucket holds a list of colliding entries, and the expected work of a lookup is proportional to `1 + load factor` — one bucket probe plus the expected chain length. Degradation is graceful and roughly linear as the table fills. - With **open addressing**, entries live in the bucket array itself and a lookup walks a probe sequence, whose expected length climbs steeply as occupancy approaches 1. Either way, the familiar "O(1) lookup" is **expected** or **amortized** under a well-behaved hash, not a guarantee. The worst case is O(n): if every key hashes to the same bucket, the load factor still reads 0.73 while every lookup walks 12,000 entries. Load factor is an average, and averages hide adversaries and skewed key distributions. ## Degrees of freedom across real systems Because the tolerable load depends on how collisions are handled, mainstream runtimes made different calls on the same concept: a widely used chained table in the Java standard library grows at 0.75 occupancy, C++'s unordered containers default to a maximum load factor of 1.0, and Python's open-addressed dictionaries grow at roughly two thirds. All three are computing the same ratio; they disagree only about where the ratio becomes uncomfortable. Note also that a chained table's load factor **can exceed 1** — three entries per bucket is a load factor of 3, slow but perfectly legal. Open addressing cannot: with entries stored in the array, the load factor is hard-capped below 1. ## How to say it in an interview "Entries over buckets — here 0.73. It is average occupancy, so it tells me the expected cost of an operation, not whether collisions exist. With a decent hash at 0.73, about half the buckets are empty and a few thousand keys are already sharing. That is normal; what the number is really for is deciding when to grow the table."
- Can a load factor be greater than 1, and what would that imply?Yes, but only with chaining, where overflowing entries live in a list or subtree hanging off the bucket rather than in the array. A load factor of 3 means an average chain of three entries — legal, and merely three times the expected scan work per lookup. Open addressing stores entries inside the bucket array itself, so it can never exceed 1; it is hard-capped and in practice must resize well before that.
- Two tables both report a load factor of 0.73, yet one has far worse lookup latency. What explains it?Load factor is an average and averages hide skew. A weak or poorly matched hash function can pile many keys into a few buckets while leaving the rest empty; the ratio is unchanged but the long chains dominate latency. Key distribution matters too — structured keys such as sequential identifiers or shared prefixes can defeat a hash that mixes poorly. Diagnose by measuring the bucket-occupancy distribution, not the scalar.
- Why is the load factor recomputed on insert rather than measured periodically?Both numbers are already maintained: the table keeps a live entry count and knows its bucket-array length, so the ratio is a division on a path that is already touching both. Checking it on every insert means the growth threshold can never be overshot by more than one entry, which keeps the cost bound tight. A periodic sampler would let occupancy drift past the threshold between samples, exactly when operations are getting expensive.
Think of a coat-check rack where each coat is assigned a hook by a dice roll rather than in order. At 73% occupancy the rack looks roomy, but plenty of hooks are bare while others carry two or three coats.
saying these in an interview costs you the question
- Says collisions only begin when the table is nearly full
- Calls load factor the percentage of memory used
- Claims a load factor above 0.5 means every bucket is occupied
- Treats hash lookups as O(1) with no expected-case caveat
- Assumes uniform hashing fills buckets evenly one after another
- Believes any collision signals a broken hash function