Load factor and rehashing in Data Structures Theory - Time & Space Complexity

Time Complexity: Load factor and rehashing

O(n)

Understanding Time Complexity

When using hash tables, it is important to understand how the load factor and rehashing affect performance.

We want to know how the time to insert or find items changes as the table fills up and grows.

Scenario Under Consideration

Analyze the time complexity of this simplified hash table insertion with rehashing.

function insert(key, value) {
  if (loadFactor() > 0.7) {
    rehash();
  }
  index = hash(key) % tableSize;
  table[index] = {key: key, value: value};
  numberOfItems++;
}

function loadFactor() {
  return numberOfItems / tableSize;
}

function rehash() {
  oldTable = table;
  tableSize = tableSize * 2;
  table = new Array(tableSize);
  numberOfItems = 0;
  for (let item of oldTable) {
    if (item !== undefined) {
      insert(item.key, item.value);
    }
  }
}
    

This code inserts items into a hash table, and when the table is more than 70% full, it doubles the size and re-inserts all items.

Identify Repeating Operations

Look at what repeats as the input grows.

• Primary operation: Inserting items into the hash table.
• How many times: Each insert is usually quick, but when rehashing happens, all existing items are re-inserted once.

How Execution Grows With Input

Normally, inserting one item takes about the same time regardless of size.

Input Size (n)	Approx. Operations
10	About 10 simple inserts, occasional rehashing
100	About 100 inserts, with a few rehashes doubling the table
1000	About 1000 inserts, with several rehashes each re-inserting many items

As the table grows, rehashing happens less often but costs more each time because it re-inserts all items.

Final Time Complexity

Time Complexity: O(n)

This means that inserting n items takes time proportional to n, even with rehashing included.

Common Mistake

[X] Wrong: "Rehashing makes insertion very slow every time."

[OK] Correct: Rehashing happens only occasionally, so its cost spreads out, keeping average insertion fast.

Interview Connect

Understanding load factor and rehashing helps you explain how hash tables stay efficient as they grow, a key skill in many coding discussions.

Self-Check

"What if the load factor threshold was set to 0.9 instead of 0.7? How would that affect the time complexity?"

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