Rehash (To Maintain Performance)

Quick Index

Efficiency Problem
Solution -- Rehash
Max Load Ratio (Load Factor)
Load Ratio (Rehash) Examples
Min Load Ratio
Rehashing Steps
Auto-Rehashing

Efficiency Problem

Let us first discuss the purpose for rehashing via problem solution.

Consider a hash table with no rehash:

Assume we start off with 16 buckets
We add twenty million elements
At this point the average size of a bucket is over one million elements

🐞 This is a problem. The hash table promises O(1) efficiency, but now it will need to scan/iterate through a million elements in a bucket to find a key. Efficiency has degraded to O(n).

Solution -- Rehash

The efficiency of a hash tables is dependent on small bucket sizes.

That is the reason we rehash. We rebuild the hash table with more buckets and then re-insert all the elements (key-values) into the new buckets.

We do this so the "problem case" we discussed does not occur. Small bucket sizes (one or two elements) is crucial -- to avoid any chance of scanning searches through long lists.

Note we discussed rehash here in terms of "growth" (this is most typical). However, optionally, a hash table may rehash to "shrink" if it is very sparse (has a lot of wasted/empty space).

Max Load Ratio (Load Factor)

The max load ratio helps ensure high performance of the hash table.

In various source literature we will also see the max load ratio referred to as the load factor.

When the actual load ratio goes above the max, we rehash (grow) the hash table.

A common default maxLoadRatio is 0.75.

Load Ratio (Rehash) Examples

Legend

size = number of keys in structure
length = length of table (i.e. number of buckets)
loadRatio = size / length
maxLoadRatio = ratio that triggers a rehash - when exceeded

Example 1

We're using maxLoadRatio = 0.75
Here we have a table of length 16 buckets
Keys are added and the loadRatio increases (recall that loadRatio mean the average number of keys per bucket)
When the 13th key is added, then loadRatio > maxLoadRatio, which triggers a rehash

size	length	loadRatio	maxLoadRatio
1	16	0.06	0.75
2	16	0.13	0.75
10	16	0.63	0.75
11	16	0.69	0.75
12	16	0.75	0.75
13	16	0.81	0.75

Example 2

We're using maxLoadRatio = 0.75
Here we have a table of length 512 buckets
Keys are added and the loadRatio increases (recall that loadRatio mean the average number of keys per bucket)
When the 385th key is added, then loadRatio > maxLoadRatio, which triggers a rehash

size	length	loadRatio	maxLoadRatio
380	512	0.742	0.75
381	512	0.744	0.75
382	512	0.746	0.75
383	512	0.748	0.75
384	512	0.750	0.75
385	512	0.752	0.75

Optionally we may also choose to rehash if the load ratio goes below a given minimum load ratio.

We would rehash in this case to save space. This rehash would not impact search performance.

A common default minLoadRatio is 0.1.

Rehashing Steps

Rehashing is a two-step process:

Increase (or decrease) the number of buckets (create an array of new buckets) [generally double or half the size]
Insert all existing elements (key-values) into the new buckets

The purpose is to improve the load ratio.

Hash table auto-rehashing does the following:

Grow and rehash the table when the load ratio becomes greater than the max load ratio
Shrink and rehash the table when the load ratio becomes smaller than the min load ratio

Note that "grow" is fundamental to maintain performance and "shrink" is optional to reduce wasted space.

Generally when we grow the table we double the size. If we shrink the table (for min load ratio) we would half the size.

Data Structures And Algorithms (DSA) (Chapter 601 - Hash Table Concepts)

Chapter 601 - Hash Table Concepts Rehash (To Maintain Performance)

Index Intro Concept Design 1 Algorithms Concept Design 2 Advantages References

Chapter Top Search Site Contents