C++

Implementing Hash Table in C++

If you have ever worked in a python environment, then you must have known about the usage of the object “dictionary” that contains a key-value pair within it. Just like dictionaries, C++ came up with the concept of key-value pair. This pair will be stored in the data structure hash table of C++. The data structure hash table will be using the hash function to calculate the array index to insert values into the table using indexes and search them as well.

Within this guide, we will discuss the use of methods to create, add, delete, search values from the hash tables using some of its functions.

Let’s start with the login from Linux. Try making a C++ file using the “touch” instruction in the shell and make use of any available built-in editor from your Linux system to open it (i.e. Gnu Nano).

Example: Hash Table

You will see that the empty file is opened on your Linux terminal screen. Within this file, we have to include some of the main and necessary libraries of C++ to make our code executable upon using different concepts.

So, we have added the “iostream” for input and output usage in the script via the cin and cout objects. The string library has been used to make use of string values in our code. The “cstdlib”, and “cstdio” library has been used to get the standard character and input values for the use of hash tables. Before using any function or class, we have declared a standard “namespace” in the code and after that, we have initialized a constant integer variable “T_S” for the hash table size to get 200 records.

The class HashTableEntry is here to initialize the value of the key-value pair of a table by getting the value as an input from the user. The constructor function HashTableEntry() will be utilized for this.

Here comes the other class “HashMapTable” declaring a private pointer object “tb” for the class “HashTableEntry”.

The creation of an object “hash” in the main() function for class HashMapTable, the first function to get executed, is the construction function “HashMapTable”. This constructor is used to construct the key-value pair type table of size “T_S” i.e. 200.

To construct a key-value table of size 200, we have been utilizing the “for” loop up to size 200 initializing each index to NULL.

This function will calculate the modulus of key “a” and table size “T_s” and return it.

If the user chooses option ‘1’, the “Input” function will get executed upon getting key-value pair from the user. The “HashFunc” function will be called by passing the value “a” to it. The returned modulus will be saved to the “h” variable. This “h” will be used as an index number for table “tb” within the while loop.

If the specific index value of a table is not NULL and table index “h” for key “a” is not equal to key “a”, it will be called the HashFunc() again to calculate the modulus and save the result to “h”. If the specific index of the table is not null, we will delete that particular value from the table and generate a new key-value entry at the specific index.

The SearchKey() function will take the key, check the modulus and search for the value in the table index. If the value at index “h” is NULL, it will return -1 otherwise returned the value “b” of a specific index “h” from the table.

The delete() function will take the key and the specific value for this key. Delete the value if the specified index is not empty and display the success message using the cout statement.

The destructor is used to delete the whole hash table.

After starting the main() method, we have created an object “hash” for the class HashMapTable. Due to object formation, the constructor will be called and a table will be created. Then, we have initialized 2 integer variables a, b, and c. We have been using the menu representation for a user to create a table, insert, delete, and display records choosing some option.

So, the while() loop will continue to execute until the user exits. We have been using cout standard output statements to create a menu i.e. choose 1 to enter a value, 2 to search, 3 to delete, and 4 to exit. A user has been asked to choose an option and a cin statement is used to get input (1,2,3,4) in a variable ‘c’ from the user.

Now, here comes the switch statement using the variable “c” as an option value to act accordingly.

Now, if the user has pressed 1 as an option, case 1 of a switch will get executed. It will execute some cout statements and ask you to enter the key first and then the pair value for a particular key using cin statement and saving key-value input to “a” and “b” variables. The “Input” function will be called using a “hash” object and the variable “a”, “b” will be passed to it.

If a user chooses 2, case 2 will get executed and ask a user to enter a key or search. The “cin” will get a key from the user to put in the variable “a”. The “if” statement will call the “SearchKey()” method using the “hash” object.

If we don’t find any key from the table i.e. “-1”, we will display a message “No Value found at key a”. Otherwise, we will display the key and its specific value returned by the “SearchKey” function.

In choosing option 3, the user will be asked to enter the key to delete it from the table. The function “delete()” will be executed.

If the user chooses option 4, the program will exit.

Now, it’s time to compile this code with Ubuntu’s “g++” special compiler for C++ files.

The compilation was successful and we executed it with the “./a.out” query. The 4 option menu has been displayed and the user has been asked to enter his/her choice (1,2,3,4). The user has added 1 to insert value in the Hash table. The user entered the key and its value for the table. This record got inserted successfully and the menu got displayed again.

The user entered “2” as an option to search for the specific key value. In return, we got the value “14” for key 1 in the hash table. The options menu will be displayed again.

This time, the user chooses option 3 to delete the already held value from the hash table using its key. So, the user was asked to enter the key for which you want to delete the value (i.e. 1). The system will display the message that the specific element has been removed.

Again, the menu has been displayed. The user has chosen option 4 to exit the program.

Conclusion

This article is all about the creation of a Hash table using the C++ code in the Ubuntu 20.04 system. Along with that, we also discovered the methods to insert the key-value pair in the hash table, display the specific key-value pair, delete a specific key-value pair and exit the code. We used the menu to make it simple and the switch statements to choose options.

About the author

Aqsa Yasin

I am a self-motivated information technology professional with a passion for writing. I am a technical writer and love to write for all Linux flavors and Windows.