Load factor is defined as (m/n) where n is the total size of the hash table and m is the preferred number of entries that can be inserted before an increment in the size of the underlying data structure is required.

Rehashing is a technique in which the table is resized, i.e., the size of the table is doubled by creating a new table.

### How hashing works?

For insertion of a key(K) – value(V) pair into a hash map, 2 steps are required:

- K is converted into a small integer (called its hash code) using a hash function.
- The hash code is used to find an index (hashCode % arrSize) and the entire linked list at that index(Separate chaining) is first searched for the presence of the K already.
- If found, it’s value is updated and if not, the K-V pair is stored as a new node in the list.

## Complexity and Load Factor

- The
**time taken**in the initial step is contingent upon both the value of K and the chosen hash function. For instance, if the key is represented by the string “**abcd**,” the hash function employed might be influenced by the length of the string. However, as n becomes significantly large, where n is the number of entries in the map, and the length of keys becomes negligible compared to n, the hash computation can be considered to occur in constant time, denoted as O(1). - Moving on to the
**second**step, it involves traversing the list of**key-value**pairs located at a specific index. In the worst-case scenario, all n entries might be assigned to the same index, resulting in a time complexity of O(n). Nevertheless, extensive research has been conducted to design hash functions that uniformly distribute keys in the array, mitigating the likelihood of this scenario. **On average**, with n entries and an array size denoted by b, there would be an average of n/b entries assigned to each index. This n/b ratio is referred to as the load factor, representing the burden placed on our map.- It is crucial to maintain a
**low load factor**to ensure that the number of entries at a given index remains minimal, thereby keeping the time complexity nearly constant at O(1).

- Complexity of Hashing
- Time complexity – O(n
*n*) - Space complexity – O(n
*n*)

- Time complexity – O(n
- Complexity of Rehashing
- Time complexity – O(n
*n*) - Space complexity – O(n
*n*)

- Time complexity – O(n

## Load Factor Example

Let’s understand the load factor through an example.

If we have the initial capacity of HashTable = 16.

We insert the first element and now check if we need to increase the size of the HashTable capacity or not.

It can be determined by the formula:

**Size of hashmap (m) / number of buckets (n)**

In this case, the size of the hashmap is 1, and the bucket size is 16. So, 1/16=0.0625. Now compare this value with the default load factor.

0.0625<0.75

So, no need to increase the hashmap size.

We do not need to increase the size of hashmap up to 12th element, because

12/16=0.75

As soon as we insert the 13th element in the hashmap, the size of hashmap is increased because:

13/16=0.8125

Which is greater than the default hashmap size.

0.8125>0.75

Now we need to increase the hashmap size

## Rehashing

As the name suggests, rehashing means hashing again. Basically, when the load factor increases to more than its pre-defined value (e.g. 0.75 as taken in the above examples), the Time Complexity for search and insert increases.

So to overcome this, the size of the array is increased(usually doubled) and all the values are hashed again and stored in the new double-sized array to maintain a low load factor and low complexity.

This means if we had Array of size 100 earlier, and once we have stored 75 elements into it(given it has Load Factor=75), then when we need to store the 76th element, we double its size to 200.

**But that comes with a price:**

With the new size the Hash function can change, which means all the 75 elements we had stored earlier, would now with this new hash Function yield different Index to place them, so basically we rehash all those stored elements with the new Hash Function and place them at new Indexes of newly resized bigger HashTable.

**It is explained below with an example.**

### Why Rehashing?

Rehashing is done because whenever key-value pairs are inserted into the map, the load factor increases, which implies that the time complexity also increases as explained above. This might not give the required time complexity of O(1). Hence, rehash must be done, increasing the size of the bucketArray so as to reduce the load factor and the time complexity.

Let’s try to understand the above with an example:

Say we had HashTable with Initial Capacity of 4.

We need to insert 4 Keys: 100, 101, 102, 103

And say the Hash function used was division method: Key % ArraySize

So Hash(100) = 1, so Element2 stored at 1st Index.

So Hash(101) = 2, so Element3 stored at 2nd Index.

So Hash(102) = 0, so Element1 stored at 3rd Index.

With the insertion of 3 elements, the load on Hash Table = ¾ = 0.74

So we can add this 4th element to this Hash table, and we need to increase its size to 6 now.

But after the size is increased, the hash of existing elements may/not still be the same.

**E.g.** The earlier hash function was Key%3 and now it is Key%6.

If the hash used to insert is different from the hash we would calculate now, then we can not search the Element.**E.g.** 100 was inserted at Index 1, but when we need to search it back in this new Hash Table of size=6, we will calculate it’s hash = 100%6 = 4

But 100 is not on the 4th Index, but instead at the 1st Index.

So we need the rehashing technique, which rehashes all the elements already stored using the new Hash Function.

### How Rehashing is Done?

Let’s try to understand this by continuing the above example.

**Element1:** Hash(100) = 100%6 = 4, so Element1 will be rehashed and will be stored at 5th Index in this newly resized HashTable, instead of 1st Index as on previous HashTable.

**Element2:** Hash(101) = 101%6 = 5, so Element2 will be rehashed and will be stored at 6th Index in this newly resized HashTable, instead of 2nd Index as on previous HashTable.

**Element3:** Hash(102) = 102%6 = 6, so Element3 will be rehashed and will be stored at 4th Index in this newly resized HashTable, instead of 3rd Index as on previous HashTable.

Since the Load Balance now is 3/6 = 0.5, we can still insert the 4th element now.

**Element4:** Hash(103) = 103%6 = 1, so Element4 will be stored at 1st Index in this newly resized HashTable.

#### Rehashing Steps –

- For each addition of a new entry to the map, check the current load factor.
- If it’s greater than its pre-defined value, then Rehash.
- For Rehash, make a new array of double the previous size and make it the new bucket array.
- Then traverse to each element in the old bucketArray and insert them back so as to insert it into the new larger bucket array.

However, it must be noted that if you are going to store a really large number of elements in the HashTable then it is always good to create a HashTable with sufficient capacity upfront as this is more efficient than letting it perform automatic rehashing.

## Program to Implement Rehashing

The rehashing method is implemented specifically inside rehash(), where we pick the existing buckets, calculate their new hash and place them inside new indices of the newly resized array.

### Java

```
import java.util.ArrayList;
class HashTable {
```*// Each bucket will have a Key and Value store, along with the pointer to the next Element, as it follows the Chaining Collision Resolution method.*
static class Bucket {
Object key;
Object value;
Bucket next; *// Chain*
public Bucket(Object key, Object value) {
this.key = key;
this.value = value;
next = null;
}
}
*// The bucket array where the nodes containing Key-Value pairs are stored*
ArrayList<Bucket> buckets;
*// No. of pairs stored.*
int size;
*// Size of the bucketArray*
int initialCapacity;
*// Default loadFactor*
double loadFactor;
public HashTable(int initialCapacity, double loadFactor) {
this.initialCapacity = initialCapacity;
this.loadFactor = loadFactor;
buckets = new ArrayList<>(initialCapacity);
for (int i = 0; i < initialCapacity; i++) {
buckets.add(null);
}
System.out.println("HashTable created");
System.out.println("Number of pairs in the HashTable: " + size);
System.out.println("Size of HashTable: " + initialCapacity);
System.out.println("Default Load Factor : " + loadFactor + "\n");
}
private int hashFunction(Object key) {
*// Using the inbuilt function from the object class*
*// This can return integer value for any Object.*
int hashCode = key.hashCode();
*// array index = hashCode % initialCapacity*
return (hashCode % initialCapacity);
}
public void insert(Object key, Object value) {
*// Getting the index at which it needs to be inserted*
int bucketIndex = hashFunction(key);
*// The first node of the chain, at that index*
Bucket head = buckets.get(bucketIndex);
*// First, loop through all the nodes present in the chain at that index to check if the key already exists*
while (head != null) {
*// If already present the value is updated*
if (head.key.equals(key)) {
head.value = value;
return;
}
head = head.next;
}
*// new node with the new Key and Value*
Bucket newElementNode = new Bucket(key, value);
*// The head node at the index*
head = buckets.get(bucketIndex);
*// the new node is inserted by making it the head and it's next is the previous head*
newElementNode.next = head;
buckets.set(bucketIndex, newElementNode);
System.out.println("Pair(" + key + ", " + value + ") inserted successfully.\n");
*// Incrementing size as new Key-Value pair is added to the HashTable*
size++;
*// Load factor calculated every time a new element is added.*
double loadFactor = (1.0 * size) / initialCapacity;
System.out.println("Current Load factor = " + loadFactor);
*// If the load factor is more than desired one, rehashing is done*
if (loadFactor > this.loadFactor) {
System.out.println(loadFactor + " is greater than " + this.loadFactor);
System.out.println("Therefore Rehashing will be done.\n");
rehash();
System.out.println("New Size of HashTable: " + initialCapacity + "\n");
}
System.out.println("Number of pairs in the HashTable: " + size);
System.out.println("Size of HashTable: " + initialCapacity + "\n");
}
private void rehash() {
System.out.println("\n***Rehashing Started***\n");
*// The present bucket list is made oldBucket*
ArrayList<Bucket> oldBucket = buckets;
*// New bucketList of double the old size is created*
buckets = new ArrayList<>(2 * initialCapacity);
for (int i = 0; i < 2 * initialCapacity; i++) {
buckets.add(null);
}
*// Now size is made zero and we loop through all the nodes in the original bucket list and insert it into the new list*
size = 0;
initialCapacity *= 2; *// New size = double of the previous size.*
for (Bucket head : oldBucket) {
*// head of the chain at that index*
while (head != null) {
Object key = head.key;
Object val = head.value;
*// calling the insert function for each node in oldBucket as the new list is now the bucketArray*
insert(key, val);
head = head.next;
}
}
System.out.println("\n***Rehashing Ended***\n");
}
public void printHashTable() {
System.out.println("Current HashTable:");
*// loop through all the nodes and print them*
for (Bucket head : buckets) {
*// head of the chain at that index*
while (head != null) {
System.out.println("key = " + head.key + ", val = " + head.value);
head = head.next;
}
}
System.out.println();
}
}
public class HashTableDemo {
public static void main(String[] args) {
*// Creating the HashTable*
HashTable hashTable = new HashTable(5, 0.75);
*// Inserting elements*
hashTable.insert(1, "Element1");
hashTable.printHashTable();
hashTable.insert(2, "Element2");
hashTable.printHashTable();
hashTable.insert(3, "Element3");
hashTable.printHashTable();
hashTable.insert(4, "Element4");
hashTable.printHashTable();
hashTable.insert(5, "Element5");
hashTable.printHashTable();
}
}

### C++

```
#include <iostream>
#include <vector>
class HashTable {
private:
```*// Each bucket will have a Key and Value store, along with the pointer to the next Element, as it follows the Chaining Collision Resolution method.*
struct Bucket {
int key;
std::string value;
Bucket* next; *// Chain*
Bucket(int k, const std::string& v) : key(k), value(v), next(nullptr) {}
};
*// The bucket array where the nodes containing Key-Value pairs are stored*
std::vector<Bucket*> buckets;
*// No. of pairs stored.*
int size;
*// Size of the bucketArray*
int initialCapacity;
*// Default loadFactor*
double loadFactor;
public:
HashTable(int initialCapacity, double loadFactor) : initialCapacity(initialCapacity), loadFactor(loadFactor), size(0) {
buckets.resize(initialCapacity, nullptr);
std::cout << "HashTable created" << std::endl;
std::cout << "Number of pairs in the HashTable: " << size << std::endl;
std::cout << "Size of HashTable: " << initialCapacity << std::endl;
std::cout << "Default Load Factor : " << loadFactor << "\n" << std::endl;
}
*// Hash function*
int hashFunction(int key) {
return key % initialCapacity;
}
*// Insert a key-value pair into the hash table*
void insert(int key, const std::string& value) {
int bucketIndex = hashFunction(key);
Bucket* head = buckets[bucketIndex];
*// Check if the key already exists*
while (head != nullptr) {
if (head->key == key) {
head->value = value;
return;
}
head = head->next;
}
*// Key not found, insert a new node*
Bucket* newElementNode = new Bucket(key, value);
newElementNode->next = buckets[bucketIndex];
buckets[bucketIndex] = newElementNode;
std::cout << "Pair(" << key << ", " << value << ") inserted successfully." << std::endl;
*// Increment size*
size++;
*// Load factor*
double currentLoadFactor = static_cast<double>(size) / initialCapacity;
std::cout << "Current Load factor = " << currentLoadFactor << std::endl;
*// If the load factor is more than desired one, rehashing is done*
if (currentLoadFactor > loadFactor) {
std::cout << currentLoadFactor << " is greater than " << loadFactor << std::endl;
std::cout << "Therefore Rehashing will be done." << std::endl;
rehash();
std::cout << "New Size of HashTable: " << initialCapacity << "\n" << std::endl;
}
std::cout << "Number of pairs in the HashTable: " << size << std::endl;
std::cout << "Size of HashTable: " << initialCapacity << "\n" << std::endl;
}
*// Rehash the hash table*
void rehash() {
std::cout << "\n***Rehashing Started***\n" << std::endl;
*// Make a copy of the old bucket list*
std::vector<Bucket*> oldBucket = buckets;
*// Create a new bucket list with double the old size*
buckets.resize(2 * initialCapacity, nullptr);
*// Reset size*
size = 0;
*// New size = double of the previous size*
initialCapacity *= 2;
*// Loop through all the nodes in the original bucket list and insert them into the new list*
for (Bucket* head : oldBucket) {
while (head != nullptr) {
int key = head->key;
const std::string& val = head->value;
insert(key, val);
head = head->next;
}
}
std::cout << "\n***Rehashing Ended***\n" << std::endl;
}
*// Print the current hash table*
void printHashTable() {
std::cout << "Current HashTable:" << std::endl;
for (Bucket* head : buckets) {
while (head != nullptr) {
std::cout << "key = " << head->key << ", val = " << head->value << std::endl;
head = head->next;
}
}
std::cout << std::endl;
}
};
int main() {
*// Creating the HashTable*
HashTable hashTable(5, 0.75);
*// Inserting elements*
hashTable.insert(1, "Element1");
hashTable.printHashTable();
hashTable.insert(2, "Element2");
hashTable.printHashTable();
hashTable.insert(3, "Element3");
hashTable.printHashTable();
hashTable.insert(4, "Element4");
hashTable.printHashTable();
hashTable.insert(5, "Element5");
hashTable.printHashTable();
return 0;
}

### C

```
#include <stdio.h>
#include <stdlib.h>
```*// Each bucket will have a Key and Value store, along with the pointer to the next Element, as it follows the Chaining Collision Resolution method.*
struct Bucket {
int key;
char *value;
struct Bucket *next; *// Chain*
};
*// The bucket array where the nodes containing Key-Value pairs are stored*
struct HashTable {
struct Bucket **buckets;
int size;
int initialCapacity;
double loadFactor;
};
*// Function to create a new Bucket node*
struct Bucket *newBucket(int key, const char *value) {
struct Bucket *newNode = (struct Bucket *)malloc(sizeof(struct Bucket));
newNode->key = key;
newNode->value = strdup(value); *// strdup allocates memory for a new string and copies the input string*
newNode->next = NULL;
return newNode;
}
*// Function to create a new HashTable*
struct HashTable *newHashTable(int initialCapacity, double loadFactor) {
struct HashTable *hashTable = (struct HashTable *)malloc(sizeof(struct HashTable));
hashTable->initialCapacity = initialCapacity;
hashTable->loadFactor = loadFactor;
hashTable->size = 0;
*// Allocate memory for the array of buckets*
hashTable->buckets = (struct Bucket **)malloc(initialCapacity * sizeof(struct Bucket *));
for (int i = 0; i < initialCapacity; i++) {
hashTable->buckets[i] = NULL;
}
printf("HashTable created\n");
printf("Number of pairs in the HashTable: %d\n", hashTable->size);
printf("Size of HashTable: %d\n", hashTable->initialCapacity);
printf("Default Load Factor: %f\n\n", hashTable->loadFactor);
return hashTable;
}
*// Hash function*
int hashFunction(int key, int initialCapacity) {
return key % initialCapacity;
}
*// Function to insert a key-value pair into the hash table*
void insert(struct HashTable *hashTable, int key, const char *value) {
int bucketIndex = hashFunction(key, hashTable->initialCapacity);
struct Bucket *head = hashTable->buckets[bucketIndex];
*// Check if the key already exists*
while (head != NULL) {
if (head->key == key) {
free(head->value); *// Free the old value*
head->value = strdup(value);
return;
}
head = head->next;
}
*// Key not found, insert a new node*
struct Bucket *newElementNode = newBucket(key, value);
newElementNode->next = hashTable->buckets[bucketIndex];
hashTable->buckets[bucketIndex] = newElementNode;
printf("Pair(%d, %s) inserted successfully.\n", key, value);
*// Increment size*
hashTable->size++;
*// Load factor*
double currentLoadFactor = (double)hashTable->size / hashTable->initialCapacity;
printf("Current Load factor = %f\n", currentLoadFactor);
*// If the load factor is more than desired one, rehashing is done*
if (currentLoadFactor > hashTable->loadFactor) {
printf("%f is greater than %f\n", currentLoadFactor, hashTable->loadFactor);
printf("Therefore Rehashing will be done.\n");
rehash(hashTable);
printf("New Size of HashTable: %d\n\n", hashTable->initialCapacity);
}
printf("Number of pairs in the HashTable: %d\n", hashTable->size);
printf("Size of HashTable: %d\n\n", hashTable->initialCapacity);
}
*// Function to rehash the hash table*
void rehash(struct HashTable *hashTable) {
printf("\n***Rehashing Started***\n\n");
*// Make a copy of the old bucket list*
struct Bucket **oldBucket = hashTable->buckets;
*// Create a new bucket list with double the old size*
hashTable->buckets = (struct Bucket **)malloc(2 * hashTable->initialCapacity * sizeof(struct Bucket *));
for (int i = 0; i < 2 * hashTable->initialCapacity; i++) {
hashTable->buckets[i] = NULL;
}
*// Reset size*
hashTable->size = 0;
*// New size = double of the previous size*
hashTable->initialCapacity *= 2;
*// Loop through all the nodes in the original bucket list and insert them into the new list*
for (int i = 0; i < hashTable->initialCapacity / 2; i++) {
struct Bucket *head = oldBucket[i];
while (head != NULL) {
int key = head->key;
const char *val = head->value;
insert(hashTable, key, val);
head = head->next;
}
}
printf("\n***Rehashing Ended***\n\n");
}
*// Function to print the current hash table*
void printHashTable(struct HashTable *hashTable) {
printf("Current HashTable:\n");
for (int i = 0; i < hashTable->initialCapacity; i++) {
struct Bucket *head = hashTable->buckets[i];
while (head != NULL) {
printf("key = %d, val = %s\n", head->key, head->value);
head = head->next;
}
}
printf("\n");
}
*// Function to free the memory allocated for the hash table*
void freeHashTable(struct HashTable *hashTable) {
for (int i = 0; i < hashTable->initialCapacity; i++) {
struct Bucket *head = hashTable->buckets[i];
while (head != NULL) {
struct Bucket *temp = head;
head = head->next;
free(temp->value);
free(temp);
}
}
free(hashTable->buckets);
free(hashTable);
}
int main() {
*// Creating the HashTable*
struct HashTable *hashTable = newHashTable(5, 0.75);
*// Inserting elements*
insert(hashTable, 1, "Element1");
printHashTable(hashTable);
insert(hashTable, 2, "Element2");
printHashTable(hashTable);
insert(hashTable, 3, "Element3");
printHashTable(hashTable);
insert(hashTable, 4, "Element4");
printHashTable(hashTable);
insert(hashTable, 5, "Element5");
printHashTable(hashTable);
*// Free the allocated memory*
freeHashTable(hashTable);
return 0;
}

### Python

```
class Bucket:
def __init__(self, key, value):
self.key = key
self.value = value
self.next = None
class HashTable:
def __init__(self, initial_capacity, load_factor):
self.initial_capacity = initial_capacity
self.load_factor = load_factor
self.size = 0
self.buckets = [None] * initial_capacity
print("HashTable created")
print(f"Number of pairs in the HashTable: {self.size}")
print(f"Size of HashTable: {self.initial_capacity}")
print(f"Default Load Factor: {self.load_factor}\n")
def hash_function(self, key):
return key % self.initial_capacity
def insert(self, key, value):
bucket_index = self.hash_function(key)
head = self.buckets[bucket_index]
```*# Check if the key already exists*
while head is not None:
if head.key == key:
head.value = value
return
head = head.next
*# Key not found, insert a new node*
new_element_node = Bucket(key, value)
new_element_node.next = self.buckets[bucket_index]
self.buckets[bucket_index] = new_element_node
print(f"Pair({key}, {value}) inserted successfully.")
*# Increment size*
self.size += 1
*# Load factor*
current_load_factor = self.size / self.initial_capacity
print(f"Current Load factor = {current_load_factor}")
*# If the load factor is more than desired one, rehashing is done*
if current_load_factor > self.load_factor:
print(f"{current_load_factor} is greater than {self.load_factor}")
print("Therefore Rehashing will be done.\n")
self.rehash()
print(f"New Size of HashTable: {self.initial_capacity}\n")
print(f"Number of pairs in the HashTable: {self.size}")
print(f"Size of HashTable: {self.initial_capacity}\n")
def rehash(self):
print("\n***Rehashing Started***\n")
*# Make a copy of the old bucket list*
old_bucket = self.buckets[:]
*# Create a new bucket list with double the old size*
self.buckets = [None] * (2 * self.initial_capacity)
*# Reset size*
self.size = 0
*# New size = double of the previous size*
self.initial_capacity *= 2
*# Loop through all the nodes in the original bucket list and insert them into the new list*
for head in old_bucket:
while head is not None:
key = head.key
val = head.value
self.insert(key, val)
head = head.next
print("\n***Rehashing Ended***\n")
def print_hash_table(self):
print("Current HashTable:")
*# Loop through all the nodes and print them*
for head in self.buckets:
while head is not None:
print(f"key = {head.key}, val = {head.value}")
head = head.next
print()
*# Creating the HashTable*
hash_table = HashTable(5, 0.75)
*# Inserting elements*
hash_table.insert(1, "Element1")
hash_table.print_hash_table()
hash_table.insert(2, "Element2")
hash_table.print_hash_table()
hash_table.insert(3, "Element3")
hash_table.print_hash_table()
hash_table.insert(4, "Element4")
hash_table.print_hash_table()
hash_table.insert(5, "Element5")
hash_table.print_hash_table()

Running this with the insertion and printing of 5 Key-values will output:

```
HashMap created
Number of pairs in the Map: 0
Size of Map: 5
Default Load Factor : 0.75
Pair(1, Element1) inserted successfully.
Current Load factor = 0.2
Number of pairs in the Map: 1
Size of Map: 5
Current HashMap:
key = 1, val = Element1
Pair(2, Element2) inserted successfully.
Current Load factor = 0.4
Number of pairs in the Map: 2
Size of Map: 5
Current HashMap:
key = 1, val = Element1
key = 2, val = Element2
Pair(3, Element3) inserted successfully.
Current Load factor = 0.6
Number of pairs in the Map: 3
Size of Map: 5
Current HashMap:
key = 1, val = Element1
key = 2, val = Element2
key = 3, val = Element3
Pair(4, Element4) inserted successfully.
Current Load factor = 0.8
0.8 is greater than 0.75
Therefore Rehashing will be done.
***Rehashing Started***
Pair(1, Element1) inserted successfully.
Current Load factor = 0.1
Number of pairs in the Map: 1
Size of Map: 10
Pair(2, Element2) inserted successfully.
Current Load factor = 0.2
Number of pairs in the Map: 2
Size of Map: 10
Pair(3, Element3) inserted successfully.
Current Load factor = 0.3
Number of pairs in the Map: 3
Size of Map: 10
Pair(4, Element4) inserted successfully.
Current Load factor = 0.4
Number of pairs in the Map: 4
Size of Map: 10
***Rehashing Ended***
New Size of Map: 10
Number of pairs in the Map: 4
Size of Map: 10
Current HashMap:
key = 1, val = Element1
key = 2, val = Element2
key = 3, val = Element3
key = 4, val = Element4
Pair(5, Element5) inserted successfully.
Current Load factor = 0.5
Number of pairs in the Map: 5
Size of Map: 10
Current HashMap:
key = 1, val = Element1
key = 2, val = Element2
key = 3, val = Element3
key = 4, val = Element4
key = 5, val =
```

As we can see from the above,

Initialcapacity = 5

Load Factor = 0.75

Element1 added, LoadFactor = 0.2, and as 0.2 < 0.75, so no need to rehash.

Element2 added, LoadFactor = 0.4, and as 0.4 < 0.75, so no need to rehash.

Element3 added, LoadFactor = 0.6, and as 0.6 < 0.75, so no need to rehash.

Element4 will have LoadFactor = 0.8, and as 0.8 > 0.75, the HashTable is rehashed.

BucketSize is doubled, and all existing elements are picked and their new hash is created and placed at new Index in newly resized Hash Table.

New size = 5 * 2 = 10.

Element4 added, LoadFactor = 0.4, after rehashing.

Element5 added, LoadFactor = 0.5, and as 0.5 < 0.75, so no need to rehash.

**Supercharge Your Coding Skills! Enroll Now in Scaler Academy’s DSA Course and Master Algorithmic Excellence.**

## Conclusion

- So we have seen the Hash Table usually guarantees Constant Time complexity of insertion and Search, given we have minimal collision in it. But since nothing comes perfect, even such a Hash Table will eventually run out of size and would need to resize it.
- This measure of when the resize must be done is governed by the Load Factor.
- But again, the resize is not just increasing the size. That’s because with the resize the Hash function used might also change.
- With the change in Hash Table, it means we now need to place the existing elements at their older indices to new indices in this newly resized Hash Table.
- So we pick all earlier stored elements, rehash them with a new hash function, and place them at a new Index.
- So both Load Factor and Rehashing come hand-in-hand ensuring the Hash Table is able to provide almost Constant Time with insertion and search operations.