Load Factor and Rehashing

As more elements are inserted into a hash table, collisions become more frequent. If the table becomes too crowded, search and insertion degrade from O(1) to O(n).

To maintain constant-time performance, hash tables monitor their Load Factor and perform Rehashing.

What is the Load Factor?

The Load Factor (α) measures how full the hash table is:

α = N / C

Where:

• N = Number of elements currently stored.
• C = Total capacity (number of buckets).

Example

If a hash table has 16 buckets and contains 12 elements:

α = 12 / 16 = 0.75

The Threshold and Rehashing Trigger

In standard HashMap implementations (Java, Kotlin, Python), the default load factor threshold is 0.75:

• When α > 0.75, the table triggers Rehashing.

Why 0.75? A load factor of 0.75 represents the mathematical sweet spot between time efficiency (minimal collisions) and space efficiency (minimal wasted memory). Under Poisson distribution, a load factor of 0.75 results in a 0.6% probability of bucket chains exceeding length 8.

What Happens During Rehashing?

Rehashing is not a simple array copy! Because the array capacity changes, every single element's bucket index changes:

1. Allocate New Table: A new bucket array is allocated with double the capacity (2C).
2. Recompute Indices: For every existing key-value entry:

   New Index = hashCode(key) mod New Capacity

3. Migrate Entries: Insert entries into their new corresponding buckets in the new array.
4. Discard Old Table: The old array is garbage collected.

Copy codeOld Table (Capacity 4):
hash("apple") = 5 -> 5 % 4 = Bucket 1

New Table (Capacity 8 after rehash):
hash("apple") = 5 -> 5 % 8 = Bucket 5! (Index changed!)

Amortized Complexity Analysis

Rehashing copies all N elements, taking O(n) time. However, because capacity doubles geometrically (16 → 32 → 64 → 128), rehashing happens exponentially less frequently as the table grows.

Just like dynamic arrays, the amortized time complexity for hash table insertion remains O(1).

Android Mobile Optimization: Pre-Sizing HashMaps

In Android applications, triggering rehashing on the main UI thread during JSON parsing or data loading causes memory churn and frame drops.

Copy code// Suboptimal: Triggers multiple rehashes (default initial capacity is 16)
val userMap = HashMap<String, User>()
for (user in loadedUsers) { // Suppose 1000 users
    userMap[user.id] = user
}

// Optimized: Pre-calculate initial capacity
// formula: capacity = (expectedSize / loadFactor) + 1
val capacity = ((1000 / 0.75f) + 1).toInt()
val fastMap = HashMap<String, User>(capacity) // Exactly 0 rehashes!

Summary

• Load Factor α = N / C measures table occupancy.
• Default threshold is typically 0.75.
• When exceeded, capacity doubles and all elements are re-indexed in an O(n) rehashing operation.
• Insertion remains O(1) amortized.