One of the key challenges in hash table implementation is handling collisions, where two keys hash to the same index. Chaining and Open Addressing are two techniques that help us to manage these collisions gracefully. In this tutorial, you will learn how to handle collisions using the Chaining method in detail.
What is Hash Table Chaining?
In chaining collision, each bucket or index of the hash table contains a linked list or another data structure. When a collision occurs, the colliding elements are appended to the linked list at the corresponding index. Chaining allows multiple elements with the same hash value to coexist at the same index.
Advantages of Chaining in Hash Table.
- Chaining handles collisions effectively, ensuring that no data is lost.
- Chaining facilitates dynamic resizing, accommodating varying numbers of elements.
- Implementing chaining is straightforward, making it an attractive option for hash table design.
Disadvantages of Chaining in Hash Table.
- Each element requires additional memory for the linked list pointers, contributing to increased memory overhead.
- In scenarios with high collision rates, the performance of the linked lists might degrade, impacting overall hash table performance.
Implementation of Chaining.
Instead of storing multiple elements at the same index, chaining involves maintaining a linked list (or another data structure) at each index to store all colliding elements.
Hash Function: The hash function calculates the hash value for each key. The hash value determines the index at which the key's corresponding value will be stored.
Index Calculation: Calculate the hash value using the hash function: index = hash(key) % table_size.
Collision Occurs: If two keys hash to the same index, a collision occurs. In chaining, this is not a problem.
Linked List Handling: Each index in the hash table contains a linked list. If the linked list is empty, insert the key-value pair at the corresponding index and if the linked list is not empty, append the key-value pair to the end of the list.
Searching: When searching for a key, calculate its hash and navigate the linked list at the corresponding index. If the key is found in the linked list, return its associated value and if the linked list is empty or the key is not found, the key is not in the hash table.
Deleting: To delete a key, calculate its hash and search for it in the linked list. If found, remove the node from the linked list. If the linked list becomes empty after deletion, update the index in the hash table.
C++ code to implement Chaining in Hash Table:
// C++ code of chaining in hash table #include <iostream> #include <list> using namespace std; // HashTable class with Chaining class HashTable { private: int table_size; // Size of the hash table // Array of linked lists list<pair<int, int>>* table; // Hash function to determine the index int hash(int key) { return key % table_size; } public: // Constructor to initialize the hash table HashTable(int size) { table_size = size; table = new list<pair<int, int>>[table_size]; } // Function to insert a key-value pair into the hash table void insert(int key, int value) { int index = hash(key); table[index].push_back(make_pair(key, value)); } // Function to search for a key and return its value int search(int key) { int index = hash(key); for (auto& it : table[index]) { if (it.first == key) { return it.second; // Key found, return its value } } return -1; // Key not found } // Function to delete a key from the hash table void remove(int key) { int index = hash(key); for (auto it = table[index].begin(); it != table[index].end(); ++it) { if (it->first == key) { table[index].erase(it); // Remove the key-value pair break; } } } // Function to display the hash table void display() { for (int i = 0; i < table_size; ++i) { cout << "[" << i << "] -> "; for (const auto& it : table[i]) { cout << "(" << it.first << ", " << it.second << ") -> "; } cout << "nullptr\n"; } } }; // Main function for testing int main() { // Create a hash table with a size of 5 HashTable hashTable(5); // Insert key-value pairs hashTable.insert(25, 250); hashTable.insert(14, 140); hashTable.insert(7, 70); // Display the hash table cout << "Hash Table after Insertion:\n"; hashTable.display(); // Search for a key int searchResult = hashTable.search(14); if (searchResult != -1) { cout << "Value for key 14: " << searchResult << "\n"; } else { cout << "Key 14 not found.\n"; } // Remove a key hashTable.remove(14); cout << "\nHash Table after Removal:\n"; hashTable.display(); return 0; }
Hash Table after Insertion:
[0] -> (25, 250) -> nullptr
[1] -> nullptr
[2] -> (7, 70) -> nullptr
[3] -> nullptr
[4] -> (14, 140) -> nullptr
Value for key 14: 140
Hash Table after Removal:
[0] -> (25, 250) -> nullptr
[1] -> nullptr
[2] -> (7, 70) -> nullptr
[3] -> nullptr
[4] -> nullptr
This C++ code defines a HashTable class with chaining. It includes functions for inserting, searching, removing keys, and displaying the hash table. The main function demonstrates the usage of the hash table with a few key-value pairs.
