Hash Table Load Factor

In one sentence: The load factor is how full a hash table is on average: the number of keys divided by the number of buckets.

$\alpha = \frac{n}{m}$

Read it out loud: “alpha equals n over m. Alpha is the Greek letter a, said AL-fuh, and it is the load factor. The load factor equals the number of keys, written n, divided by the number of buckets, written m. A bucket is one numbered slot in the table.”

Before you start

The ideas and signs this page uses, explained from zero. For powers of ten, Greek letters and other notation in general, see Math basics.

Keys: A key is the name you look something up by, like a person’s name in a phone book. The table stores each key, often with a value attached, such as the phone number. The number of keys stored in the table is written $n$ , and it goes up when you add an item and down when you remove one.
Buckets: A bucket is one numbered slot in the table where keys are stored. A table with $m = 100$ buckets has 100 slots, numbered 0 to 99. Keys are placed into buckets by number, a bit like putting letters into numbered mailboxes. The number of buckets is written $m$ .
Hash function: A hash function is a rule that turns a key into a bucket number. For example, a rule might turn the word cat into bucket 42 of 100. A good hash function spreads the keys evenly across the buckets, so that no bucket gets far more keys than the others.
Collisions and chaining: A collision happens when two keys land in the same bucket. With chaining, each bucket holds a short list of all the keys that landed there. A lookup then searches the list in that bucket until it finds the key or reaches the end of the list.
Averages, like $\frac{80}{100} = 0.8$: An average is a total divided by the number of groups. The load factor is an average: keys per bucket. If there are 80 keys in 100 buckets, the average is $\frac{80}{100} = 0.8$ keys per bucket. Think of it as: each bucket holds about 0.8 of a key, on average.
The Greek letter alpha, $\alpha$: $\alpha$ is the Greek letter alpha, said AL-fuh. Greek letters are only names for quantities. Here the letter $\alpha$ is the name for the load factor, and other formulas on this site use the same letter for different quantities, so read each page for its own meaning.
Threshold: A threshold is a fixed limit that triggers an action when it is passed. In this page the threshold is 0.75. When the load factor goes above 0.75, the program resizes the table, which means building a bigger table and moving the keys into it.

What each symbol means

Symbol	Meaning
$\alpha$	The load factor, a plain number with no unit. It says how many keys there are, on average, for each bucket. A value of 0.5 means about half a key per bucket, and a value of 2 means two keys per bucket on average.
$n$	The number of keys stored in the table right now, a whole number such as 80. It counts the stored items, so it has no unit. It changes whenever a key is added or removed.
$m$	The number of buckets, the numbered slots that keys are sorted into by the hash function. It is a whole number such as 100. It has no unit and changes only when the table is resized.

The formula piece by piece

$n$: The number of keys stored in the table. A phone-book app with 80 contacts has $n = 80$ . This number grows as keys are added, and it is the amount of data that must be sorted into buckets.
$m$: The number of buckets, the slots that keys are sorted into. It is set when the table is created and changes only when the table is resized. With $m = 100$ , there are 100 slots available for the keys.
$\frac{n}{m}$: The keys divided by the buckets, which gives the average number of keys per bucket. With $n = 80$ and $m = 100$ , the ratio is $\frac{80}{100} = 0.8$ . A ratio below 1 means there are fewer keys than buckets, on average.
$\alpha = \frac{n}{m}$: In one plain sentence: the load factor, written alpha, equals the number of keys divided by the number of buckets, and it tells you how full the table is on average.

What the formula is doing, and why

What goes in and what comes out. The load factor takes two counts, the keys $n$ and the buckets $m$ , and gives one plain number $\alpha$ with no unit. A load factor of 0.5 means there is about half a key per bucket, on average. A load factor of 2 means two keys per bucket, on average, and the lists are twice as long.

Why does it control lookup speed? With chaining, each bucket holds a short list of the keys that landed there. If the hash function spreads keys evenly, the average list has length $\alpha$ . An unsuccessful lookup, one that does not find the key, checks about $\alpha$ keys on average. So the work per lookup depends on $\alpha$ , not on the total size of the table. A small load factor means short lists and fast lookups.

Why must the table grow? As keys are added, $\alpha$ rises, so the lists get longer. A common plan is to choose a threshold, such as 0.75, and resize when $\alpha$ passes it. Doubling the number of buckets cuts $\alpha$ in half. Every key is then moved to its new bucket, because the bucket number depends on how many buckets there are.

Why not keep the load factor tiny? A lower threshold keeps lookups faster, but it uses more memory, since many buckets stay empty. A higher threshold saves memory but makes the lists longer and lookups slower. The threshold is a trade-off between speed and memory, and there is no single correct value.

A real example. The Java HashMap class uses a default load factor of 0.75 and starts with 16 buckets. Once it holds more than 12 entries, it doubles the table. Other designs choose their own threshold, because the best choice depends on whether speed or memory matters more for the job.

An everyday picture

Think of a row of 100 coat hooks at a party. The load factor is the number of coats divided by the number of hooks. With 80 coats on 100 hooks, each hook holds less than one coat on average. Hang far more coats per hook and each hook becomes a tall stack, so finding one coat takes longer. Then you add more hooks, which is what resizing a table does.

Worked example: A table with 80 keys

A hash table has $m = 100$ buckets and stores $n = 80$ keys. It resizes when the load factor passes 0.75. We find the load factor now, decide whether to resize, and then find the load factor after the table doubles.

Find the load factor now. Divide the keys by the buckets: $\alpha = \frac{80}{100} = 0.8$ . This means there are 0.8 keys per bucket on average, which is 80 keys spread over 100 slots.
Compare with the threshold. The threshold is 0.75. Since 0.8 is greater than 0.75, the load factor has passed the limit, so the table must resize before more keys are added.
Find the average lookup work now. With chaining, an unsuccessful lookup checks about 0.8 keys on average, because each bucket holds about 0.8 keys. That is only a short list, but the plan says to keep the average below 0.75, so the table grows now.
Double the buckets. The new number of buckets is $2 \times 100 = 200$ . The 80 keys must now be placed again, because the bucket number is calculated from the new bucket count, so every key may move to a different bucket.
Find the load factor after doubling. Divide again: $\alpha = \frac{80}{200} = 0.4$ . Now the average is 0.4 keys per bucket, well below the threshold, so the table has room to grow before the next resize.
Read the result. Doubling cut the load factor in half, from 0.8 to 0.4, because the same 80 keys now share twice as many buckets. Each lookup now checks about 0.4 keys on average instead of 0.8.

Answer: The load factor is 0.8, which passes the 0.75 threshold, so the table doubles to 200 buckets. The load factor then drops to 0.4, and a lookup checks about 0.4 keys on average.

The numbers in this example are recomputed by script every time the site is built.

Common mistakes

Swapping the two counts. The load factor is keys divided by buckets, so $\frac{n}{m}$ and $\frac{m}{n}$ mean different things. With 80 keys and 100 buckets, the wrong ratio $\frac{100}{80} = 1.25$ would suggest a table that is fuller than it really is.
Thinking a load factor above 1 is an error. With chaining, $\alpha$ can go above 1. The lists get longer, and lookups slow down, but nothing breaks.
Expecting no collisions at a low load factor. Even at $\alpha = 0.5$ , some buckets get two keys, because a hash function scatters keys in a way that looks random.
Forgetting to resize. Without resizing, the lists keep growing and every lookup gets slower.

Where you will meet it

The HashMap class in Java, which resizes when the load factor passes a set threshold.
Symbol tables in compilers and interpreters, which are the lists of names a program uses, such as variable names. Lookups must stay fast as the number of names grows.
In-memory key-value stores, which keep data in computer memory and balance memory use against lookup speed by choosing a load factor.
Choosing the starting size of a map before loading a large batch of data, so the table does not resize many times.

Questions people ask

Can the load factor be greater than 1?

With chaining, yes. $\alpha = 2$ means two keys per bucket on average, so the lists are twice as long. With open addressing, where each key takes its own slot and a collision moves the key to another free slot, $\alpha$ can never go above 1, because each slot holds at most one key.

What is a good load factor?

It depends on the design. Java’s 0.75 is a common choice for chained tables. A lower value makes lookups faster but uses more memory, and a higher value saves memory but makes lookups slower.

Why does resizing double the table?

Doubling cuts the load factor in half in one step, which leaves room for many new keys before the next resize. Moving every key costs time, but doubling means the table is rebuilt only rarely, so that cost averages out over many inserts.

Birthday Problem: The birthday problem asks how likely it is that some pair of items in a random group match, and the answer rises faster than most people expect.
Pigeonhole Principle: If you put more things than boxes into the boxes, at least one box must hold two or more things.
Bloom Filter False Positive Rate: This formula gives the chance that a Bloom filter, a small memory-saving checklist, wrongly says an item is on the list, based on how many bits and checks it uses.