Load factor and rehashing in Data Structures Theory - Step-by-Step Execution

Concept Flow - Load factor and rehashing

Start with empty hash table

↓

Insert new key

↓

Calculate load factor

↓

Is load factor > threshold?

No→Continue inserting

Yes↓

Trigger rehashing

↓

Create larger table

↓

Re-insert all keys

↓

Resume insertions

This flow shows how inserting keys updates the load factor, and when it exceeds a limit, triggers rehashing to a bigger table.

Execution Sample

Data Structures Theory

Insert keys: A, B, C, D
Load factor threshold = 0.75
Table size starts at 4
Rehash when load factor > 0.75

We insert keys one by one, check load factor after each, and rehash when needed.

Analysis Table

Step	Keys Inserted	Table Size	Load Factor	Action
1	A	4	0.25 (1/4)	Insert key A
2	A, B	4	0.5 (2/4)	Insert key B
3	A, B, C	4	0.75 (3/4)	Insert key C
4	A, B, C, D	4	1.0 (4/4)	Load factor > 0.75, trigger rehash
5	A, B, C, D	8	0.5 (4/8)	Rehash to bigger table, re-insert keys
6	A, B, C, D, E	8	0.625 (5/8)	Insert key E
7	A, B, C, D, E, F	8	0.75 (6/8)	Insert key F
8	A, B, C, D, E, F, G	8	0.875 (7/8)	Load factor > 0.75, trigger rehash
9	A, B, C, D, E, F, G	16	0.4375 (7/16)	Rehash to bigger table, re-insert keys
10	A, B, C, D, E, F, G, H	16	0.5 (8/16)	Insert key H

💡 Process stops after inserting key H with load factor below threshold.

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10
Keys Inserted	[]	[A]	[A, B]	[A, B, C]	[A, B, C, D]	[A, B, C, D]	[A, B, C, D, E]	[A, B, C, D, E, F]	[A, B, C, D, E, F, G]	[A, B, C, D, E, F, G]	[A, B, C, D, E, F, G, H]
Table Size	4	4	4	4	4	8	8	8	8	16	16
Load Factor	0	0.25	0.5	0.75	1.0	0.5	0.625	0.75	0.875	0.4375	0.5

Key Insights - 3 Insights

Why does the load factor become 1.0 at step 4 even though the threshold is 0.75?

At step 4, inserting the 4th key fills the table completely (4 keys in size 4), so load factor is 4/4 = 1.0, which is above the 0.75 threshold, triggering rehashing as shown in execution_table row 4.

What happens to the keys during rehashing at step 5?

During rehashing, the table size doubles from 4 to 8, and all existing keys are re-inserted into the new larger table, reducing the load factor to 0.5 as shown in execution_table row 5.

Why does rehashing happen again at step 8?

At step 8, inserting the 7th key into a table of size 8 results in load factor 7/8 = 0.875, which exceeds the 0.75 threshold, so rehashing is triggered again as shown in execution_table row 8.

Visual Quiz - 3 Questions

Look at the execution table at step 4. What is the load factor and what action is taken?

A Load factor is 1.0; rehashing is triggered

B Load factor is 0.75; continue inserting

C Load factor is 0.5; no action

D Load factor is 0.25; rehashing is triggered

💡 Hint

Check the 'Load Factor' and 'Action' columns at step 4 in the execution_table.

At which step does the table size first increase from 4 to 8?

A Step 7

B Step 3

C Step 5

D Step 9

💡 Hint

Look at the 'Table Size' column in the variable_tracker after each step.

If the load factor threshold was changed to 0.9, at which step would the first rehash occur?

A Step 4

B Step 8

C Step 5

D Step 9

💡 Hint

Compare load factors in execution_table rows to the new threshold 0.9.

Concept Snapshot

Load factor = (number of keys) / (table size).
When load factor exceeds a threshold (e.g., 0.75), rehashing occurs.
Rehashing means creating a bigger table and re-inserting all keys.
This keeps the hash table efficient by reducing collisions.
Rehashing doubles the table size to lower load factor.
Insertions continue after rehashing with updated table size.

Full Transcript

This visual execution trace shows how load factor and rehashing work in a hash table. We start with an empty table of size 4. Each inserted key increases the load factor, calculated as keys divided by table size. When the load factor exceeds 0.75, rehashing triggers. Rehashing creates a new table twice as big and re-inserts all keys, lowering the load factor. This process repeats as more keys are added, keeping the table efficient. The execution table and variable tracker show step-by-step changes in keys, table size, and load factor, highlighting when rehashing happens.