The load factor of a hash table is the ratio of the number of stored entries to the number of available table slots or buckets. It is an important measure of table occupancy and strongly influences collision behavior and expected operation cost.
Hash Table Load Factor
The load factor of a hash table is the ratio of the number of stored entries to the number of available table slots or buckets. It is an important measure of table occupancy and strongly influences collision behavior and expected operation cost.
\(\alpha = n/m\)
What this formula means
Scientific principle
Principle
A hash function maps keys to table positions. As more entries occupy a fixed-size table, collisions become more likely. The load factor provides a compact measure of this occupancy.
Derivation
1. Let n represent the number of stored keys.
2. Let m represent the number of table slots or buckets.
3. Load factor is defined as the average number of stored entries per slot or bucket.
4. Dividing the number of stored entries by the number of slots gives α = n/m.
5. In separate chaining, α can exceed one because a bucket may contain multiple entries.
6. In ordinary open addressing, α must remain below one because each key occupies one table slot.
Final Result
α = n/m
Resize Threshold Relation
Resize decisions are commonly triggered when α reaches an implementation-defined threshold.
Interpretation
α < 1: fewer entries than slots on average
α = 1: one entry per slot on average
α > 1: possible in separate chaining
α < 1 is required for ordinary open addressing
Variables and their meanings
| Symbol | Meaning | Unit |
|---|---|---|
α | Hash table load factor | Dimensionless |
n | Number of stored entries | Entries |
m | Number of available slots or buckets | Slots or buckets |
SI units and conversions
Load Factor
Dimensionless
Entry Count
Entries
Table Capacity
Slots or buckets
Conditions of use
The table capacity m must be greater than zero.
The entry count n is nonnegative.
The meaning of a slot depends on the collision-resolution strategy.
For separate chaining, m refers to the number of buckets.
For open addressing, m refers to the number of positions in the table.
Limitations and assumptions
Load factor alone does not determine actual collision distribution.
A poor hash function can cause clustering even at a low load factor.
For open addressing, load factor must remain below one for successful insertion.
A high load factor is not automatically harmful for separate chaining if chains are efficiently managed.
Different implementations use different resizing thresholds and performance trade-offs.
Step-by-step worked examples
| Problem | Solution | Answer |
|---|---|---|
A hash table contains 75 entries and has 100 buckets. Calculate its load factor. |
| The load factor is 0.75, or 75%. |
A separate-chaining hash table has 240 stored entries and 60 buckets. Calculate its load factor. |
| The load factor is 4, meaning the table stores an average of four entries per bucket. |
Real-world applications
Hash map performance analysis
Dictionary and set implementation
Database hash indexing
Hash table resizing strategies
Collision-resolution analysis
Formula Meaning
The load factor of a hash table is the ratio of the number of stored entries to the number of available table slots or buckets. It is an important measure of table occupancy and strongly influences collision behavior and expected operation cost.
Sources and further reading
No source has been supplied for this item yet. Treat the claim as needing editorial verification.