Load Factor and Rehashing | DSA in C++ - Software Development PDF Download

Introduction

Load factor and rehashing are essential concepts in data structures and algorithms when working with hash tables. Understanding these concepts is crucial for designing efficient and scalable programs. In this article, we will explore load factor and rehashing in the context of C++ programming. We will provide clear explanations, multiple examples, and simple code snippets to help you grasp these concepts easily.

What is a Load Factor?

A load factor is a metric used to measure how full a hash table is. It represents the ratio of the number of elements stored in the hash table to the total number of slots available. A load factor of 1 means the hash table is fully occupied, while a load factor of 0.5 indicates that the table is only half full.

Load Factor Calculation

The load factor can be calculated using the formula:

Load Factor = Number of elements / Total number of slots

For example, let's say we have a hash table with 10 slots and 6 elements. The load factor would be:

Load Factor = 6 / 10 = 0.6

3. Understanding Rehashing

Rehashing is the process of resizing the hash table and reinserting all the elements into the new table when the load factor exceeds a predefined threshold. It helps maintain a balanced load factor, which leads to efficient retrieval and insertion operations.

When the load factor exceeds the threshold, the hash table is expanded by creating a new table with a larger number of slots. Then, all the elements from the original table are rehashed and inserted into the new table based on the new slot indices calculated using the updated hash function.

Rehashing is essential to ensure that the load factor remains within an acceptable range, typically between 0.5 and 0.8, to avoid performance degradation.

Code Examples

Load Factor Calculation

#include <iostream>

using namespace std;

int main() {

    int numElements = 6;

    int totalSlots = 10;

    double loadFactor = static_cast<double>(numElements) / totalSlots;

    cout << "Load Factor: " << loadFactor << endl;

    return 0;

}

Output:

Load Factor: 0.6

Rehashing Implementation

#include <iostream>

#include <vector>

using namespace std;

class HashTable {

private:

    vector<int> table;

    int capacity;

    int size;

    void rehash() {

        // Create a new table with double the capacity

        int newCapacity = capacity * 2;

        vector<int> newTable(newCapacity, -1);

        // Reinsert all the elements into the new table

        for (int i = 0; i < capacity; i++) {

            if (table[i] != -1) {

                int key = table[i];

                int newIndex = key % newCapacity;

                while (newTable[newIndex] != -1) {

                    newIndex = (newIndex + 1) % newCapacity; // Linear probing

                }

                newTable[newIndex] = key;

            }

        }

        // Update the capacity and table

        capacity = newCapacity;

        table = newTable;

    }

public:

    HashTable(int initialCapacity) : capacity(initialCapacity), size(0) {

        table.resize(capacity, -1);

    }

    void insert(int key) {

        if (size / static_cast<double>(capacity) > 0.8) {

            rehash();

        }

        int index = key % capacity;

        while (table[index] != -1) {

            index = (index + 1) % capacity; // Linear probing

        }

        table[index] = key;

        size++;

    }

};

int main() {

    HashTable ht(5);

    ht.insert(10);

    ht.insert(20);

    ht.insert(30);

    ht.insert(40);

    ht.insert(50);

    ht.insert(60); // Rehashing occurs after this insertion

    return 0;

}

Sample Problems and Solutions

Problem 1: Calculate the load factor for a hash table with 20 elements and 30 slots.

#include <iostream>

using namespace std;

int main() {

    int numElements = 20;

    int totalSlots = 30;

    double loadFactor = static_cast<double>(numElements) / totalSlots;

    cout << "Load Factor: " << loadFactor << endl;

    return 0;

}

Output:

Load Factor: 0.666667

Problem 2: Implement a hash table with a capacity of 8. Insert the following elements: 10, 20, 30, 40, 50, 60, 70, 80, 90.

Refer to the "Rehashing Implementation" code example for a complete implementation.

Conclusion

Load factor and rehashing play crucial roles in the design and implementation of efficient hash tables. By understanding these concepts, you can build scalable and high-performance applications that handle a large number of elements. Remember to keep the load factor within an acceptable range to avoid performance degradation.