Rehashing & Extendible Hashing

Imagine your library rack is perfectly arranged. One day, you keep adding more books in the rack. Slowly, shelves start overflowing. You push things left, right, top, bottom… but nothing fits anymore.

At that moment, you do not “adjust.” You reorganize the entire library rack. That idea is called Rehashing. Means in Rehashing
1. Make the library rack bigger
2. Reorganize the entire rack from zero.

.

Now imagine instead of buying a bigger library rack, the rack magically grows new sections only where needed. That idea is called Extendible Hashing. Do not reorganize the entire rack from zero.

Both are advanced collision handling techniques used when simple probing or chaining is not enough.

Let us understand both in a simple and clear way.

.

What is Rehashing?    

“Rehashing means creating a bigger hash table, and inserting all the elements again, to reduce collisions and improve performance.”

Rehashing is a technique used when the load factor of a hash table becomes too high.

Instead of handling more collisions in the same table, we –

• Create a new larger hash table
• Use a new hash function (or same function with new table size)
• Reinsert all existing elements

.

When Do We Perform Rehashing?

Usually when load factor α > 0.7 (or threshold value). This threshold is chosen because after this point, collisions increase rapidly.

Algorithm – Rehashing

1. Monitor load factor α = n/m
2. If α exceeds threshold:
   • Create new table of size 2m (or next prime number)
   • For each element in old table
     • Compute new hash value
     • Insert into new table

3. Replace old table with new table

.

Example

Suppose table size is m = 7 and you have to insert keys – 10, 20, 30, 40, 50
Load factor = 5/7 = 0.714
If threshold = 0.7, rehashing is triggered.
Now new table size = 13

We reinsert all elements using new hash function (k mod 13). Old distribution changes and Collisions reduce. Also, the performance improves again.

.

Time Complexity – Rehashing

Rehashing Insertion – O(n) because all elements must be reinserted. However, this does not happen every time. So amortized time complexity of insertion remains O(1).

.

Space Complexity – Rehashing

Its space complexity is O(m), but temporarily, we need extra space for new table while copying elements.

.

What is Extendible Hashing?

Now we move one level higher. Rehashing rebuilds the whole table.

“Extendible Hashing grows dynamically without rebuilding everything. The Hash Table doubles when needed.”

Extendible Hashing is a dynamic hashing technique where –

• A directory is maintained.
• Directory size doubles when needed.
• Buckets split individually instead of resizing whole table.

It uses bits of hash value to decide bucket location.

Key Concepts

Global Depth – Number of bits used to index directory
Local Depth – Number of bits used by a bucket

When a bucket overflow

• If local depth < global depth → split bucket
• If local depth = global depth → double directory and then split

This is smarter growth.

Algorithm – Extendible Hashing

1. Compute hash value of key
2. Use first d bits (global depth) to find directory index
3. Insert into bucket
4. If bucket overflows
   • If local depth < global depth
     • Split bucket
     • Redistribute elements
   • Else
     • Double directory
     • Increase global depth
     • Split bucket

Example

The numbers are 18, 16, 20, 7, 24, 10, 31, 7.
Bucket Size = 3

Suppose global depth = 1 and local depth = 1

Directory has 2^{Global Depth} = 2¹ entries 

2 Entries are 0 and 1.

.

Insert 4

Binary Form = 00100
Lowest Significant of 00100 = 0
Global Depth = 1
Local Depth = 1
Bucket Size = 3

.

Insert 16

Binary Form = 10000
Lowest Significant of 10000 = 0
Global Depth = 1
Local Depth = 1
Bucket Size = 3

.

Insert 6

Binary Form = 00110
Lowest Significant of 00110 = 0
Global Depth = 1
Local Depth = 1
Bucket Size = 3

.

Insert 22

Binary Form = 10110
Lowest Significant of 10110 = 0
Global Depth = 1
Local Depth = 1
Bucket Size = 3

Overflow condition, If local depth = global depth → double directory and then split

Local Depth of 0 = 2, Global Depth = 2

Directory has 2^{Global Depth} = 2² entries 

4 Enteries are 00, 10, 01, 11

.

Insert 24

Binary Form = 11000
Lowest Significant of 11000 = 0
Global Depth = 1
Local Depth of 00, 10 = 2
Local Depth of 01, 11 = 1
Bucket Size = 3

Local Depth of 0 = 2, Global Depth = 2

.

Insert 10

Binary Form = 01010
Lowest Significant of 01010 = 10
Global Depth = 2
Local Depth of 00, 10 = 2
Local Depth of 01, 11 = 1
Bucket Size = 3

.

Insert 31

Binary Form = 11111
Lowest Significant of 11111 = 1
Global Depth = 2
Local Depth of 00, 10 = 2
Local Depth of 01, 11 = 1
Bucket Size = 3

.

Insert 7

Binary Form = 00111
Lowest Significant of 00111 = 1
Global Depth = 2
Local Depth of 00, 10 = 2
Local Depth of 01, 11 = 1
Bucket Size = 3

.

Insert 9

Binary Form = 01001
Lowest Significant of 01001 = 1
Global Depth = 2
Local Depth of 00, 10 = 2
Local Depth of 01, 11 = 1
Bucket Size = 3

.

Insert 13

Binary Form = 01101
Lowest Significant of 01101 = 1
Global Depth = 2
Local Depth of 00, 10 = 2
Local Depth of 01, 11 = 1
Bucket Size = 3

Overflow condition, If local depth < global depth → split bucket

Local Depth of 01, 11 = 2, Global Depth = 2

Hence, extendible hashing complete.

.

Time Complexity – Extendible Hashing

Searching – O(1)
Insertion – O(1)
Worst case insertion – O(n) during splitting

Since splits are local, performance remains stable.

.

Space Complexity – Extendible Hashing

Extra space required for directory and buckets. So, directory size grows as 2^global_depth.

.

Applications

Rehashing is used in

• Programming language hash maps
• C++ unordered_map
• Java HashMap
• Python dictionaries

Extendible Hashing is used in

• Database indexing
• File systems
• Large disk-based storage systems
• Distributed storage