Hashing Implementation in C++
In the C++ STL, hashing is a mapping mechanism that associates a hash value with a key. An array's elements are referred to as its keys; each key has a hash value that makes it simple to locate it in the hash table. This facilitates quicker access to the piece needed, and depending on the hash function chosen, the efficiency may change.
Why is hashing important?
Although it's still possible to find the required key using the most widely used data structures, including arrays and linked lists, hashing is more effective.
Arrays can be useful when we need to randomly access any element from a given index. However, to achieve this, we must know the element's index. At this point, hashing enters the picture. The hash function determines the hash value that indicates the location of a key. With the aid of its hash value, retrieving this key whenever necessary is simple.
For Example, the hashing approach uses a person's name to make it easier to retrieve their contact information.
Components in Hashing:
There are 3 main components in Hashing:
- Key: The hash function, which accepts any string or integer as input, determines an index or location for an item's storage in a data structure.
- Hash Function: After receiving the input key, the hash function outputs the element's index in an array known as a hash table. The hash index is the name given to the index.
- Hash Table: A hash table is a type of data structure that uses a unique function known as a hash function to map keys to values. Data is hashed and stored associatively in an array with distinct indexes for each data value.
![Hashing Implementation in C++](https://static.tutorialandexample.com/cpp/hashing-implementation-in-cpp1.png)
Collisions on Hashing:
A collision occurs when the same hash value is generated by multiple keys and maps to the same index of the array.
A collision in hashing happens when two distinct inputs provide the same hash value. Due to the pigeonhole principle, which states that there will always be more inputs than hash values when mapping a large number of inputs to a smaller set of hash values, some inputs will inevitably share the same hash.
![Hashing Implementation in C++](https://static.tutorialandexample.com/cpp/hashing-implementation-in-cpp2.png)
For Example:
Let the Hash function be "key%10."
Elements to insert/ keys 11, 22, 33, 44, 55, 66, 71
Applying the hash function to the above keys:
11%10=1
22%10=2
33%10=3
44%10=4
55%10=5
66%10=6
71%10=1
As we can see, the 1st key index and 7th key index are the same (1). This condition is called collision.
To address collision, we can utilize a collision resolution method unlike chaining to deal with collisions. We store the values in linked lists or other data structures rather than straight into the hash table slots. A list of values that have been hashed to each slot on the table is therefore stored there. In this manner, we can save all the keys without losing any data, even if they hash to the same spot.
Collision resolution techniques:
There are 2 collision resolution techniques:
- Separate chaining
- Open Addressing
Separate chaining:
One of the simplest techniques to use and comprehend is separate chaining.
Using this method, the collision slot is converted to a linked list, and the new key is appended to the list. This connected list of slots resembles a chain, and it is called separate chaining. It is more commonly used in situations where we need to figure out how many keys to add or remove.
The Separate Chaining technique combines a hash table with a linked list to overcome the collision. This approach uses more memory to fix the issue. O(n), where n is the number of keys that hash to the same slot, is the temporal complexity of both searching for and removing an element from the hash table.
C++ Program:
#include<bits/stdc++.h>
using namespace std;
class Hash
{
int BUCKET;
list<int> *table;
public:
Hash(int V);
void insertItem(int x);
void deleteItem(int key);
int hashFunction(int x) {
return (x % BUCKET);
}
void displayHash();
};
Hash::Hash(int b)
{
this->BUCKET = b;
table = new list<int>[BUCKET];
}
void Hash::insertItem(int key)
{
int index = hashFunction(key);
table[index].push_back(key);
}
void Hash::deleteItem(int key)
{
int index = hashFunction(key);
list <int> :: iterator i;
for (i = table[index].begin();
i != table[index].end(); i++) {
if (*i == key)
break;
}
if (i != table[index].end())
table[index].erase(i);
}
void Hash::displayHash() {
for (int i = 0; i < BUCKET; i++) {
cout << i;
for (auto x : table[i])
cout << " --> " << x;
cout << endl;
}
}
int main()
{
int a[] = {15, 11, 27, 8, 12};
int n = sizeof(a)/sizeof(a[0]);
Hash h(7);
for (int i = 0; i < n; i++)
h.insertItem(a[i]);
h.deleteItem(12);
h.displayHash();
return 0;
}
Output:
![Hashing Implementation in C++](https://static.tutorialandexample.com/cpp/hashing-implementation-in-cpp3.png)
This C++ code uses independent chaining to resolve collisions to construct a simple hash table. The hash table functionality is encapsulated in the Hash class, which comprises member variables for an array of linked lists (table) and the number of buckets (BUCKET). The hash table is initialized with a predetermined number of buckets by the constructor. A hash function is used by the insertion (insertItem) and deletion (deleteItem) methods to find the index where the key should be placed in the hash table. Elements are appended to the linked list at the appropriate index in the event of a collision. The elements of each bucket are printed together with their contents by using the displayHash function. An entry is removed from the hash table, and an array of integers is added to the main function.
This code offers a straightforward implementation of hash tables with fundamental functions. It provides effective data storage and retrieval with collision handling and acts as a basis for more intricate implementations.
Open Addressing:
Open addressing is a technique for handling collisions, unlike separate chaining. Every element in open addressing is kept in the hash table itself. Therefore, the table's size must always be more than or equal to the total number of keys (keep in mind that, if necessary, we can expand the table's size by transferring older data). Another name for this strategy is closed hashing.
Operations performed in Open Addressing / closed hashing:
- Insert(n): Keep looking until you find a vacant position. Insert "n" when you've located an empty slot.
- Search(n): Continue probing until either an empty slot is reached or the slot's key does not equal n.
- Delete(n): The search might not succeed if we remove a key. Therefore, the slots of deleted keys are specifically noted as "deleted."
Although an item can be inserted into a deleted slot using the insert, the search continues after the deleted slot.
Different Approaches to Open Addressing:
- Linear Probing:
During linear probing, a single key-value pair is stored in each cell of a hash table. Linear probing looks up the nearest subsequent free position in the hash table and inserts the new key there when the hash function maps a new key to a cell that is currently occupied by another key, causing a collision.
- Quadratic Probing:
One technique for fixing collisions that can happen when adding data to a hash table is quadratic probing. Quadratic probing determines a new position when a collision occurs (two keys hashing to the same spot) by appending subsequent squares of an increasing value (often beginning at 1) to the initial position until an empty slot is located.
- Double Hashing:
The first hash function establishes the key-value pair's starting position in the table in the event of a collision. If that spot is already taken, the second hash function determines an offset from the starting position. The next available place, which is the sum of the original position and the offset, is where the key-value pair is subsequently stored.
A hash table's performance can be enhanced, and the number of collisions can be decreased with the use of this collision resolution technique. Determining the offset, however, involves additional computation, which may lengthen the time needed to insert or search for a key-value combination.
C++ program for Open Addressing:
#include <bits/stdc++.h>
using namespace std;
struct HashNode
{
int key;
int value;
};
const int capacity = 20;
struct HashNode** arr;
struct HashNode* dummy;
void insert(int key, int V,int size)
{
struct HashNode* temp
= (struct HashNode*)malloc(sizeof(struct HashNode));
temp->key = key;
temp->value = V;
int hashIndex = key % capacity;
while (arr[hashIndex] != NULL
&& arr[hashIndex]->key != key
&& arr[hashIndex]->key != -1) {
hashIndex++;
hashIndex %= capacity;
}
if (arr[hashIndex] == NULL || arr[hashIndex]->key == -1)
size++;
arr[hashIndex] = temp;
}
int deleteKey(int key,int size)
{
int hashIndex = key % capacity;
while (arr[hashIndex] != NULL) {
if (arr[hashIndex]->key == key) {
arr[hashIndex] = dummy;
size--;
return 1;
}
hashIndex++;
hashIndex %= capacity;
}
return 0;
}
int find(int key)
{
int hashIndex = (key % capacity);
int counter = 0;
while (arr[hashIndex] != NULL) {
int counter = 0;
if (counter++ > capacity)
break;
if (arr[hashIndex]->key == key)
return arr[hashIndex]->value;
hashIndex++;
hashIndex %= capacity;
}
return -1;
}
int main()
{
int size=0;
arr = (struct HashNode**)malloc(sizeof(struct HashNode*)
* capacity);
for (int i = 0; i < capacity; i++)
arr[i] = NULL;
dummy= (struct HashNode*)malloc(sizeof(struct HashNode));
dummy->key = -1;
dummy->value = -1;
insert(1, 5,size);
insert(2, 15,size);
insert(3, 20,size);
insert(4, 7,size);
if (find(4,size) != -1)
cout << "Value of Key 4 = " << find(4) << endl;
else
cout << ("Key 4 does not exists\n");
if (deleteKey(4))
cout << ("Node value of key 4 is deleted "
"successfully\n");
else {
cout << ("Key does not exists\n");
}
if (find(4) != -1)
cout << ("Value of Key 4 = %d\n", find(4));
else
cout << ("Key 4 does not exists\n");
}
Output:
![Hashing Implementation in C++](https://static.tutorialandexample.com/cpp/hashing-implementation-in-cpp4.png)
This C++ code implements a hash table with linear probing for collision resolution. It provides functions for finding key-value pairs, deleting, and inserting. For each function, the index is found using a hash function, collisions are handled by linearly probing to the next available slot, and a size variable is updated correspondingly.