In this post, we will explore the application of open addressing within a hash table in C++.
Utilizing hash tables is crucial for incorporating associative arrays or key-value mappings due to its reliance on hash maps. Collisions occur when distinct keys produce the same hash value. In the event of a collision, an open addressing approach is employed to find an alternative slot for storing the conflicting key and its associated value.
Key Elements:
- Hash Function: Given a key as input, this function returns the index in the hash table where the matching value should be kept. Keys ought to be distributed evenly throughout the table by it.
- Collision Resolution: The process of open addressing, also known as "probe sequence" searching, locates an empty slot in the hash table to resolve collisions. For doing this, a number of techniques can be applied, including double hashing, quadratic probing, and linear probing.
- Load Factor: The load factor is the proportion of the hash table's size to the number of elements it contains. A high load factor can result in increased collisions and decreased performance.
Approach:
Storing the {key, value} pair to be hashed in each array element and utilizing an array of structures as the hash table, paired with the modulus hash function, provides a solution to the presented issue. Strategies such as linear probing and open addressing can effectively handle collisions that may arise during the hashing process.
Define a node to be hashed, such as a HashNode structure, to a key-value pair.
- In order to store all key-value pairs, initialize an array with a pointer of type HashNode, such as *arr .
- Put in (Key, Value): Put the {Key, Value} pair into the hash table.
- Set the initial value of a HashNode variable, such as temp, to {Key, Value}.
- Using the hash function, determine the index where the key can be stored. After that, put the index into a variable called HashIndex.
- In order to perform linear probing, update the hashindex continuously using the formula HashIndex = (HashIndex+1)%capacity, provided that arr[HashIndex] is not empty or that another Key exists.
- Insert the specified Node by assigning the address of temp to arr[HashIndex] if arr[HashIndex] is not null.
Find(Key): The function Find(Key) retrieves the Key's value from the hash table.
- A hash function can be used to find the index where the key might be located. After that, the index can be stored in a variable called HashIndex.
- The value of the key is returned by Key if it is present in the arr[HashIndex].
- If not, use linear probing, updating the hash index continuously using the formula hash index = (HashIndex+1)%capacity. If the key is located, return its value at that HashIndex and then return true.
- It returns -1 to indicate that the key could not be located. If not, give the Key's value back.
Delete(Key): Key is removed from the hash table using the Delete(Key) function.
- Using a hash function, we can find the index where the key might be and store it in a variable called HashIndex.
- If it is present in the arr[HashIndex], return true and delete the key by assigning {-1, -1} to the arr[HashIndex].
- In the event that HashIndex = (HashIndex+1)%capacity is not reached, perform linear probing by iteratively updating HashIndex. Afterwards, return true if the key is located, and remove the key's value at that hash index.
- A false return is given if the Key cannot be located.
Example:
Let's consider an illustration to apply open addressing in a hash table using C++.
Example
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int TABLE_SIZE = 5;
// Define a class for hash nodes
class HashNode {
public:
int key;
int value;
HashNode(int key, int value) {
this->key = key;
this->value = value;
}
};
// Define a class for a deleted node
class DeletedNode : public HashNode {
private:
static DeletedNode *instance;
DeletedNode() : HashNode(-1, -1) {}
public:
static DeletedNode *getInstance() {
if (instance == NULL)
instance = new DeletedNode();
return instance;
}
};
DeletedNode *DeletedNode::instance = NULL;
// Define a class for the hash table
class HashMapTable {
private:
HashNode **table;
public:
HashMapTable() {
table = new HashNode*[TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; i++) {
table[i] = NULL;
}
}
// Hash function
int hashFunction(int key) {
return key % TABLE_SIZE;
}
// Insert an element into the table
void insert(int key, int value) {
int hashValue = hashFunction(key);
int initial = -1;
int deletedIndex = -1;
while (hashValue != initial && (table[hashValue] == DeletedNode::getInstance() || table[hashValue] != NULL && table[hashValue]->key != key)) {
if (initial == -1)
initial = hashValue;
if (table[hashValue] == DeletedNode::getInstance())
deletedIndex = hashValue;
hashValue = hashFunction(hashValue + 1);
}
if (table[hashValue] == NULL || hashValue == initial) {
if (deletedIndex != -1)
table[deletedIndex] = new HashNode(key, value);
else
table[hashValue] = new HashNode(key, value);
}
if (initial != hashValue) {
if (table[hashValue] != DeletedNode::getInstance()) {
if (table[hashValue] != NULL) {
if (table[hashValue]->key == key)
table[hashValue]->value = value;
}
}
else
table[hashValue] = new HashNode(key, value);
}
}
// Search for an element by key
int searchKey(int key) {
int hashValue = hashFunction(key);
int initial = -1;
while (hashValue != initial && (table[hashValue] == DeletedNode::getInstance() || table[hashValue] != NULL && table[hashValue]->key != key)) {
if (initial == -1)
initial = hashValue;
hashValue = hashFunction(hashValue + 1);
}
if (table[hashValue] == NULL || hashValue == initial)
return -1;
else
return table[hashValue]->value;
}
// Remove an element by key
void remove(int key) {
int hashValue = hashFunction(key);
int initial = -1;
while (hashValue != initial && (table[hashValue] == DeletedNode::getInstance() || table[hashValue] != NULL && table[hashValue]->key != key)) {
if (initial == -1)
initial = hashValue;
hashValue = hashFunction(hashValue + 1);
}
if (hashValue != initial && table[hashValue] != NULL) {
delete table[hashValue];
table[hashValue] = DeletedNode::getInstance();
}
}
~HashMapTable() {
delete[] table;
}
};
int main() {
HashMapTable hash;
int key, value, choice;
while(true) {
cout << "1. Insert element into the table" << endl;
cout << "2. Search element from the key" << endl;
cout << "3. Delete element at a key" << endl;
cout << "4. Exit" << endl;
cout << "Enter your choice: ";
cin >> choice;
switch(choice) {
case 1:
cout << "Enter element to be inserted: ";
cin >> value;
cout << "Enter key at which element to be inserted: ";
cin >> key;
hash.insert(key, value);
break;
case 2:
cout << "Enter key of the element to be searched: ";
cin >> key;
if (hash.searchKey(key) == -1)
cout << "No element found at key " << key << endl;
else
cout << "Element at key " << key << " : " << hash.searchKey(key) << endl;
break;
case 3:
cout << "Enter key of the element to be deleted: ";
cin >> key;
hash.remove(key);
break;
case 4:
exit(0);
default:
cout << "\nEnter correct option\n";
}
}
return 0;
}
Output:
Output
1. Insert element into the table
2. Search element from the key
3. Delete element at a key
4. Exit
Enter your choice: 1
Enter element to be inserted: 10 20 30 40
Enter key at which element to be inserted: 1. Insert element into the table
2. Search element from the key
3. Delete element at a key
4. Exit
