Program to implement Separate Chaining in C++ STL without the use of pointers
Pre-requisite: Separate Chaining, STL in C++
This article implements the Separate Chaining in Hashing with help of STL in C++ without the use of pointers.
Approach: Make an array of vectors to get a dynamic (resizable) array for every hash index rather than using a linked list to do the same. Now it becomes easier to work on the data-set without using linked list. This simple trick is much easier to implement and is more efficient. In this approach:
- The size of the Hash is initialized by the constructor of the class.
- The elements are inserted in the Hash according to the expression:
Vector[i % n].push_back(i); where: Vector = the array of vectors used for hash i = current element to be hashed n = size of the hash
Algorithm: The algorithm for the approach is mentioned below:
- Initialize the size (say n) of vectors.
- While adding an element, go through the following steps:
- Get the value of x=”[value] MOD n“.
- Push back this element’s value in the v[x].
- For Deletion, we follow these steps:
- Get the value of x=”[value] MOD n“.
- Scan for the element to be deleted in v[x].
- If found, remove the element using erase() method.
- If element to be deleted is not found, print “Element not found!”
- Print the hash.
Implementation
// C++ Program to implement Separate
// Chaining in C++ STL without
// the use of pointers
#include <bits/stdc++.h>
using
namespace
std;
// Container for our data-set
class
SeperateHash {
// Data members are kept private
// since they are accessed using methods
private
:
int
n;
vector<vector<
int
> > v;
// Methods are kept public
public
:
// Initialising constructors as the
// minimum required memory will be
// allocated after which compiler
// will not report flag error
SeperateHash(
int
n)
{
// Constructor to initialize
// the vector of vectors
v = vector<vector<
int
> >(n);
// Here, we will allocate
// memory of the unnamed_memory
// to the object. This snippet
// of code won't work for now.
// Program will work whenever
// constructor gets initialized
this
->n = n;
}
int
getHashIndex(
int
x)
{
return
x % n;
}
void
add(
int
x)
{
// Adding the element according
// to hash index
v[getHashIndex(x)].push_back(x);
}
void
del(
int
x)
{
int
i = getHashIndex(x);
// Scan for the element to be removed
for
(
int
j = 0; j < v[i].size(); j++) {
// Erase if present otherwise
// print no element found!
if
(v[i][j] == x) {
v[i].erase(v[i].begin() + j);
cout << x <<
" deleted!"
<< endl;
return
;
}
}
cout <<
"No Element Found!"
<< endl;
}
void
displayHash()
{
// Display the contents
for
(
int
i = 0; i < v.size(); i++) {
cout << i;
for
(
int
j = 0; j < v[i].size(); j++)
cout <<
" -> "
<< v[i][j];
cout << endl;
}
}
};
// Driver Code
int
main()
{
// Array to be used
int
arr[] = { 12, 3, 23, 4, 11,
32, 26, 33, 17, 19 };
// Sending the size
// for separate chaining
SeperateHash obj(10);
// Inserting elements in
// the container accordingly
for
(
int
i = 0; i < 10; i++)
obj.add(arr[i]);
// Display the initial hash
cout <<
"Initial Hash:\n"
;
obj.displayHash();
// Removing the element
// from the container
cout <<
"\nRemoving 23 from Hash: "
;
obj.del(23);
cout << endl;
// Display the final hash
cout <<
"Final Hash:\n"
;
obj.displayHash();
return
0;
}
Output:Initial Hash: 0 1 -> 11 2 -> 12 -> 32 3 -> 3 -> 23 -> 33 4 -> 4 5 6 -> 26 7 -> 17 8 9 -> 19 Removing 23 from Hash: 23 deleted! Final Hash: 0 1 -> 11 2 -> 12 -> 32 3 -> 3 -> 33 4 -> 4 5 6 -> 26 7 -> 17 8 9 -> 19
Advantages of using this approach:
- We don’t need to iterate through the entries like we need to with linked lists.
- Easier debugging of code.
- Easier to implement since the conventional approach has chances of flagging segmentation fault with minor logical errors.
- Power of applying STL methods over the data which provides an edge in competitive programming.
Contact Us