How To Draw A Hash Table

Definition of C++ Hash Table

A Hash table is basically a data structure that is used to store the key value pair. In C++, a hash table uses the hash function to compute the index in an array at which the value needs to be stored or searched. This process of computing the index is called hashing. Values in a hash tabular array are not stored in the sorted club and there are huge chances of collisions in the hash table which is more often than not solved by the chaining process (creation of a linked list having all the values and the keys associated with it).

Algorithm of Hash Table in C++

Beneath given is the footstep by step process which is followed to implement the hash table in C++ using the hash role:

Initializing the tabular array size to some integer value.
Creating a hash table structure hashTableEntry for the annunciation of key and value pairs.
Creating constructor of hashMapTable.
Create the hashFunction() and finding the hash value which volition exist an index to store the bodily data in the hash table using the formula:

hash_value = hashFunction(key); index = hash_value% (table_size)

Respective functions like Insert(), searchKey(), and Remove() are used for the insertion of the chemical element at the fundamental, searching of the element at the fundamental, and removing the element at the key respectively.
Destructor is called to destroy all the objects of hashMapTable.

How does a Hash Tabular array Work in C++?

As discussed higher up, hash tables store the pointers to the actual data/ values. It uses the primal to find the index at which the data/ value needs to be stored. Let usa understand this with the help of the diagram given below:

Consider the hash table size exist ten

Key	Alphabetize (using a hash function)	Data
12	12%ten = 2	23
10	10%x = 0	34
6	6% 10 = 6	54
23	23 % x = three	76
54	54 %10 = 4	75
82	81 %10 = one	87

The element position in the hash table volition be:

0 1 2 3 4 five 6 7 eight nine

As nosotros tin can see higher up, there are high chances of collision as at that place could be ii or more keys that compute the same hash code resulting in the same alphabetize of elements in the hash table. A collision cannot be avoided in instance of hashing even if we have a large table size. We can prevent a collision past choosing the practiced hash part and the implementation method.

Though at that place are a lot of implementation techniques used for it like Linear probing, open up hashing, etc. We volition understand and implement the basic Open hashing technique too called separate chaining. In this technique, a linked listing is used for the chaining of values. Every entry in the hash tabular array is a linked list. So, when the new entry needs to exist washed, the index is computed using the cardinal and table size. Once computed, it is inserted in the list respective to that alphabetize. When there are 2 or more values having the same hash value/ index, both entries are inserted corresponding to that index linked with each other. For instance,

Where,

2 is the index of the hash tabular array retrieved using the hash role

12, 22, 32 are the data values that will be inserted linked with each other

Examples of C++ Hash Table

Allow us implement the hash table using the above described Open hashing or Separate technique:
#include <iostream> #include <list> using namespace std; class HashMapTable { // size of the hash tabular array inttable_size; // Pointer to an array containing the keys list<int> *tabular array; public: // creating constructor of the above class containing all the methods HashMapTable(int cardinal); // hash role to compute the alphabetize using table_size and key inthashFunction(int fundamental) { return (key % table_size); } // inserting the key in the hash tabular array void insertElement(int primal); // deleting the key in the hash table void deleteElement(int cardinal); // displaying the full hash table void displayHashTable(); }; //creating the hash tabular array with the given tabular array size HashMapTable::HashMapTable(intts) { this->table_size = ts; table = new list<int>[table_size]; } // insert part to button the keys in hash tabular array void HashMapTable::insertElement(int key) { int alphabetize = hashFunction(key); table[alphabetize].push_back(key); } // delete function to delete the element from the hash table void HashMapTable::deleteElement(int key) { int index = hashFunction(key); // finding the cardinal at the computed index listing <int> :: iterator i; for (i = table[index].begin(); i != table[index].end(); i++) { if (*i == key) break; } // removing the key from hash table if constitute if (i != table[index].stop()) table[alphabetize].erase(i); } // display function to showcase the whole hash table void HashMapTable::displayHashTable() { for (inti = 0; i<table_size; i++) { cout<<i; // traversing at the recent/ electric current index for (auto j : table[i]) cout<< " ==> " << j; cout<<endl; } } // Principal role intmain() { // array of all the keys to be inserted in hash table intarr[] = {20, 34, 56, 54, 76, 87}; int due north = sizeof(arr)/sizeof(arr[0]); // table_size of hash table as vi HashMapTableht(vi); for (inti = 0; i< due north; i++) ht.insertElement(arr[i]); // deleting chemical element 34 from the hash table ht.deleteElement(34); // displaying the terminal data of hash tabular array ht.displayHashTable(); render 0; }

Output:

Explanation: In the above lawmaking, an array is created for all the keys that need to exist inserted in the has table. Grade and constructors are created for hashMapTable to calculate the hash office using the formula mentioned above. The list is created as the arrow to the array of key values. Specific functions are created for the insertion, deletion, and display of the hash tabular array and called from the main method. While insertion, if ii or more than elements accept the same index, they are inserted using the listing one after the other.

Decision

The in a higher place description clearly explains what a hash table in C++ and how it is used in programs to shop the key value pairs. Hash tables are used as they are very fast to access and process the data. In that location are many chances of collisions while calculating the index using a hash role. We should always look for the methods that volition help in preventing the standoff. Then one needs to be very careful while implementing it in the plan.