Linear Probing is the simplest approach to handle the collisions in Hash Table. For instance, if the hash index is already occupied, sequentially search for the free index and insert the new key-value pair.
Prefer the Linear Probing method when the application data is limited. Alternatively, look for the Hash Table implementation using the Separate Chaining method when the data is dynamic and expected to grow larger.
1. Hash Table Representation
An example Hash Table of size 8 is represented here. The hash() function returns the same index for the keys “delete” and “int”. The key “delete” is inserted on the hash index 3. Later the key “int” results in the same hash index 3 which is already occupied. As a result, search for the next free index and insert the key at index 4.
/**
* Hash Table Node
*/
struct Node
{
std::string key;
int val;
};
// Hash Table
Node** hash_table = new Node*[capacity];
// Hash Table maximum capacity
int capacity;
2. Implementation of Hash Table using Linear Probing in C++
/**
* C++ example to demonstrate Hash Table implementation using Linear Probing
*/
#include <iostream>
#include <iomanip>
using namespace std;
/**
* Hash Table Node
*/
struct Node
{
std::string key;
int val;
};
/**
* Hash Table implementation using Linear Probing
*/
class HashTable
{
private:
// Hash Table
Node** hash_table;
// Hash Table maximum capacity
int capacity;
// Hash Table current size
int size;
// Empty node used for deletion
Node* del_node;
public:
// Constructor
HashTable(int capacity);
// Destructor
~HashTable();
// Insert the key-value pair
// Return the node inserted, NULL otherwise.
Node* insert(std::string key, int val);
// Delete the element by key
// Returns true on success, false otherwise.
bool remove(std::string key);
// Access the key-value pair
// Returns the node associated with the key
Node* get(std::string key);
// Traverse and print the hash table
void display(std::string msg);
private:
// Hash function to determine the index for every key
int hash(std::string key, int capacity);
};
HashTable::HashTable(int capacity) : capacity(capacity), size(0)
{
// Create the hash table for the given capacity
hash_table = new Node*[capacity];
// Initialize the table entries to NULL
for (int i=0; i < capacity; ++i) {
hash_table[i] = NULL;
}
// Initialize the deleted node
del_node = new Node();
del_node->key = "";
del_node->val = -1;
}
HashTable::~HashTable()
{
for (int i=0; i < capacity; ++i) {
if (hash_table[i] != NULL && ! hash_table[i]->key.empty()) {
// Delete the table record
delete hash_table[i];
hash_table[i] = NULL;
}
}
// Free the del node
free(del_node);
}
Node* HashTable::insert(std::string key, int val)
{
// Step 1. Check if the hash table size reached its capacity. If true, return.
if (size == capacity) {
return NULL;
}
// Step 2. Initialize the target index for insertion as -1.
int target_index = -1;
// Step 3. Determine the hash index for the key.
int hash_index = hash(key, capacity);
// Step 4. Check if the hash index is free. If true, set this as target index.
if (hash_table[hash_index] == NULL ||
hash_table[hash_index]->key.empty() || hash_table[hash_index]->key == key) {
target_index = hash_index;
} else {
// Step 5. Otherwise, sequentially search the table for the free index.
// Iterate the table once in circular motion from the next index.
int i = (hash_index+1) % capacity;
while (i != hash_index) {
if (hash_table[i] == NULL || hash_table[i]->key.empty() || hash_table[i]->key == key) {
// Step 6. If a free index is found, set this as target index and
// stop the iteration
target_index = i;
break;
}
i = (i+1) % capacity;
}
}
// Step 7. Create the new node.
Node *new_node = new Node();
new_node->key = key;
new_node->val = val;
// Step 8. Insert the new node to target index.
hash_table[target_index] = new_node;
++size;
return new_node;
}
bool HashTable::remove(std::string key)
{
// Step 1. Initialize the target index as -1.
int target_index = -1;
// Step 2. Determine the hash index for the key.
int hash_index = hash(key, capacity);
// Step 3. Check if the key exists in the hash index.
if (hash_table[hash_index]->key == key) {
// Step 4. If true, set the hash index as target for deletion
target_index = hash_index;
} else {
// Step 5. Otherwise, sequentially search the table for the key.
// Iterate the table once in circular motion from the next index.
// Stop the iteration if any NULL node found inbetween.
int i = (hash_index+1) % capacity;
while (i != hash_index && hash_table[i] != NULL) {
if (hash_table[i]->key == key) {
// Step 6. If key is found, set the index as target for deletion.
target_index = i;
break;
}
i = (i+1) % capacity;
}
}
// Step 7. Otherwise, if the key is not found, return false.
if (target_index == -1) {
return false;
}
// Step 8. Delete the target node and return true.
delete hash_table[target_index];
hash_table[target_index] = del_node;
--size;
return true;
}
Node* HashTable::get(std::string key)
{
// Step 1. Determine the hash index for the key
int hash_index = hash(key, capacity);
// Step 2. Check if the key is found on the hash index
if (hash_table[hash_index]->key == key) {
// Step 3. If true, return the node.
return hash_table[hash_index];
}
// Step 3. Otherwise traverse the table once in circular motion from the next index.
// Stop the iteration if any NULL node found inbetween.
int i = (hash_index+1) % capacity;
while (i != hash_index && hash_table[i] != NULL) {
if (hash_table[i]->key == key) {
// Step 4. If key is found, return the node.
return hash_table[i];
}
i = (i+1) % capacity;
}
return NULL;
}
void HashTable::display(std::string msg)
{
cout << msg << endl;
cout << "(size = " << size << ")" << endl;
// Traverse the entire hash table
for (int i=0; i < capacity; ++i) {
cout << " +--------+--------+" << endl;
cout << i << " |";
Node* p = hash_table[i];
if (p == NULL ) {
// NULL record, print empty
cout << " " << setw(6) << "" << " | " << setw(6) << "" << " |";
} else {
// Print the record from the table
cout << " " << setw(6) << left << p->key << " | " << setw(6) << right << p->val << " |";
}
cout << endl;
}
cout << " +--------+--------+" << endl << endl;
}
int HashTable::hash(std::string key, int capacity)
{
// A simple hash method to sum the ASCII values
int hash = 0;
for (int i=0; i < key.size(); ++i) {
hash += key[i];
}
return hash % capacity;
}
// The main function to begin the execution
int main()
{
// Create the hash table of capacity 8
HashTable keywords(8);
// Insert key-value pairs
keywords.insert("new", 1001);
keywords.insert("delete", 1002);
keywords.insert("int", 1003);
keywords.insert("float", 1004);
keywords.insert("if", 1005);
keywords.insert("for", 1006);
keywords.display("HASH TABLE after insertion of keywords 'new', 'delete', 'int', 'float', 'if', and 'for'");
// Delete key-value pairs
keywords.remove("int");
keywords.remove("for");
keywords.remove("delete");
keywords.display("HASH TABLE after deletion of keywords 'int', 'for', and 'delete'");
// Access a key
Node* node = keywords.get("new");
cout << "Accessing key 'new' returned value: " << node->val << endl;
return 0;
}
Output
HASH TABLE after insertion of keywords 'new', 'delete', 'int', 'float', 'if', and 'for'
(size = 6)
+--------+--------+
0 | for | 1006 |
+--------+--------+
1 | | |
+--------+--------+
2 | new | 1001 |
+--------+--------+
3 | delete | 1002 |
+--------+--------+
4 | int | 1003 |
+--------+--------+
5 | | |
+--------+--------+
6 | float | 1004 |
+--------+--------+
7 | if | 1005 |
+--------+--------+
HASH TABLE after deletion of keywords 'int', 'for', and 'delete'
(size = 3)
+--------+--------+
0 | | -1 |
+--------+--------+
1 | | |
+--------+--------+
2 | new | 1001 |
+--------+--------+
3 | | -1 |
+--------+--------+
4 | | -1 |
+--------+--------+
5 | | |
+--------+--------+
6 | float | 1004 |
+--------+--------+
7 | if | 1005 |
+--------+--------+
Accessing key 'new' returned value: 10013. Hash Table Operations
3.1. Insert Key-Value Pair into Hash Table
Firstly, determine the array index by the key and proceed with the insertion. If the index is already occupied, sequentially search for the next free index in a circular motion. It means to proceed with the search from the top of the table when it reaches the end and continue until it reaches the hash index.
Algorithm
- Check if the hash table size reached its capacity. If true, return.
- Initialize the target index for insertion as -1.
- Determine the hash index for the key.
- Check if the hash index is free. If true, set this as the target index.
- Otherwise, sequentially search the table for the free index. Iterate the table once in a circular motion from the next index.
- If a free index is found, set this as the target index and stop the iteration.
- Create the new node.
- Insert the new node into the target index.
Examples
An example to demonstrate the hash table insertions using the linear probing method.
- Insert the key “new” to index (2) as per the hash function.
- Next, Insert the key “delete” to index (3) by following the same procedure.
- The hash function returns the duplicate index (3) for the key “int”. But, the index is already occupied and has the key “delete”. So, we need to look for the subsequent indexes. Since the next index (4) is free, we can insert the “int”.
3.2. Delete Key-Value Pair from Hash Table
Firstly, determine the array index by the key, and sequentially search for the key. Proceed the search from the top of the table when it reaches the end until the starting point. Stop the search when the key is found, or encountered a NULL node. If the key exists, delete the key-value pair and replace it with an empty node.
Algorithm
- Initialize the target index as -1.
- Determine the hash index for the key.
- Check if the key exists in the hash index.
- If true, set the hash index as a target for deletion.
- Otherwise, sequentially search the table for the key. Iterate the table once in a circular motion from the next index. Stop the iteration if any NULL node is found in between.
- If the key is found, set the index as a target for deletion. Return false otherwise.
- Delete the target, replace it with an empty node, and return true.
Examples
An example to demonstrate the hash table deletion with the linear probing method.
- The key “delete” is available at index (3). Remove the key-value pair by replacing it with -1.
- Next, the key “new” is available at the index (2). Repeat the same procedure to remove the pair.
- The next key “int” is not available at the index (3), so we need to probe the subsequent indexes. Finally, remove the key available at the next index (4).
3.3. Access the Key-Value Pair in Hash Table
Firstly, determine the array index by the key. Then check if the key is present on the index. Otherwise, search for the key in the subsequent indexes in a linear fashion.
Algorithm
- Determine the hash index for the key
- Check if the key is exits on the hash index
- Otherwise, traverse the table once in a circular motion from the next index. Stop the iteration if any NULL node is found in between.
- If the key is found, return the node, NULL otherwise.
Examples
Let’s see the examples to look up the keys “new” and “delete” from the following Hash Table.
- Accessing the key “new” locates the exact index (2) using the hash function.
- Whereas, accessing the key “int” is not straightforward. The hash function returns the index (3), but it is available at the index (4). We need to locate this by probing the sequent indexes.
4. References
- std::unordered_map – Hash Table implementation in C++ standard library.