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.

Practice

1. What does the load factor in a hash table represent?

easy

A. The ratio of stored elements to the total capacity of the table

B. The speed at which data is inserted into the table

C. The number of collisions that have occurred

D. The size of each element stored in the table

Solution

1. Step 1: Understand load factor definition

   Load factor is defined as the number of elements divided by the total slots in the hash table.

2. Step 2: Match definition to options

   The ratio of stored elements to the total capacity of the table correctly describes this ratio, while others describe unrelated concepts.

3. Final Answer:

   The ratio of stored elements to the total capacity of the table -> Option A

4. Quick Check:

   Load factor = elements / capacity [OK]

Hint: Load factor = elements ÷ table size [OK]

Common Mistakes:

• Confusing load factor with number of collisions
• Thinking load factor measures speed
• Mixing load factor with element size

2. Which of the following is the correct action when the load factor exceeds a threshold in a hash table?

easy

A. Delete random elements to reduce load

B. Reduce the size of the table to save memory

C. Rehash the table by increasing its size

D. Ignore and continue inserting elements

Solution

1. Step 1: Identify what happens when load factor is high

   A high load factor means the table is too full, causing more collisions and slower operations.

2. Step 2: Choose the correct response to high load factor

   Rehashing by increasing the table size reduces load factor and improves performance, which matches Rehash the table by increasing its size.

3. Final Answer:

   Rehash the table by increasing its size -> Option C

4. Quick Check:

   High load factor -> rehash with bigger table [OK]

Hint: Rehash by resizing when load factor is too high [OK]

Common Mistakes:

• Deleting elements randomly instead of resizing
• Ignoring the problem causing slowdowns
• Reducing table size which worsens collisions

3. Consider a hash table with capacity 10 and 7 elements inserted. If the load factor threshold is 0.7, what happens after inserting the 8th element?

medium

A. No rehashing occurs because load factor is still below threshold

B. Rehashing occurs because load factor exceeds threshold

C. Table size is reduced to maintain load factor

D. Insertion is rejected to keep load factor constant

Solution

1. Step 1: Calculate load factor after 7 elements

   Load factor = 7 / 10 = 0.7, which equals the threshold.

2. Step 2: Calculate load factor after 8 elements

   Load factor = 8 / 10 = 0.8, which exceeds the threshold of 0.7, triggering rehashing.

3. Final Answer:

   Rehashing occurs because load factor exceeds threshold -> Option B

4. Quick Check:

   Load factor > threshold -> rehash [OK]

Hint: Load factor > threshold triggers rehash [OK]

Common Mistakes:

• Assuming threshold is inclusive and no rehash needed
• Thinking table shrinks instead of grows
• Believing insertion is rejected

4. A hash table implementation does not rehash when the load factor exceeds the threshold. What is the most likely problem caused by this?

medium

A. Insertions and lookups will become slower due to collisions

B. The table will automatically shrink in size

C. The table will run out of memory quickly

D. Elements will be deleted automatically to reduce load

Solution

1. Step 1: Understand effect of no rehashing at high load

   Without rehashing, the table stays full, causing many collisions.

2. Step 2: Identify impact on operations

   More collisions slow down insertions and lookups, matching Insertions and lookups will become slower due to collisions.

3. Final Answer:

   Insertions and lookups will become slower due to collisions -> Option A

4. Quick Check:

   No rehash -> more collisions -> slower operations [OK]

Hint: No rehash means slower operations from collisions [OK]

Common Mistakes:

• Thinking memory runs out immediately
• Assuming table shrinks automatically
• Believing elements get deleted automatically

5. You have a hash table with capacity 16 and a load factor threshold of 0.75. After inserting 12 elements, you decide to rehash by doubling the capacity. What is the new load factor immediately after rehashing, before adding any new elements?

hard

A. 0.5

B. 0.75

C. 1.5

D. 0.375

Solution

1. Step 1: Calculate load factor before rehashing

   Load factor = 12 / 16 = 0.75, which triggers rehashing.

2. Step 2: Calculate load factor after doubling capacity

   New capacity = 16 * 2 = 32. Load factor = 12 / 32 = 0.375 immediately after rehash.

3. Final Answer:

   0.375 -> Option D

4. Quick Check:

   Load factor after resize = elements / new capacity = 12/32 = 0.375 [OK]

Hint: Load factor after resize = old elements ÷ new capacity [OK]

Common Mistakes:

• Using old capacity instead of new capacity
• Multiplying load factor by 2 incorrectly
• Confusing load factor with threshold