EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 600+ Courses All in One Bundle
  • Login

C++ Hash Table

By Yashi GoyalYashi Goyal

Home » Software Development » Software Development Tutorials » C ++ Programming Tutorial » C++ Hash Table

C++ 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 table are not stored in the sorted order and there are huge chances of collisions in the hash table which is generally 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++

Below given is the step by step procedure which is followed to implement the hash table in C++ using the hash function:

Start Your Free Software Development Course

Web development, programming languages, Software testing & others

  • Initializing the table size to some integer value.
  • Creating a hash table structure hashTableEntry for the declaration of key and value pairs.
  • Creating constructor of hashMapTable.
  • Create the hashFunction() and finding the hash value which will be an index to store the actual 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 element at the key, searching of the element at the key, and removing the element at the key respectively.
  • Destructor is called to destroy all the objects of hashMapTable.

How does a Hash Table Work in C++?

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

Consider the hash table size be 10

Key Index (using a hash function) Data
12 12%10 = 2 23
10 10%10 = 0 34
6 6% 10 = 6 54
23 23 % 10 = 3 76
54 54 %10 = 4 75
82 81 %10 = 1 87

The element position in the hash table will be:

0             1            2            3            4           5            6             7          8            9

34 87 23 76 75 54

As we can see above, there are high chances of collision as there could be 2 or more keys that compute the same hash code resulting in the same index of elements in the hash table. A collision cannot be avoided in case of hashing even if we have a large table size. We can prevent a collision by choosing the good hash function and the implementation method.

Though there are a lot of implementation techniques used for it like Linear probing, open hashing, etc. We will understand and implement the basic Open hashing technique also called separate chaining. In this technique, a linked list is used for the chaining of values. Every entry in the hash table is a linked list. So, when the new entry needs to be done, the index is computed using the key and table size. Once computed, it is inserted in the list corresponding to that index. 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 example,

2  —>  12  —–>22 —->32

Where,

2 is the index of the hash table retrieved using the hash function

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

Examples of C++ Hash Table

Let 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 table
inttable_size;
// Pointer to an array containing the keys
list<int> *table;
public:
// creating constructor of the above class containing all the methods
HashMapTable(int key);
// hash function to compute the index using table_size and key
inthashFunction(int key) {
return (key % table_size);
}
// inserting the key in the hash table
void insertElement(int key);
// deleting the key in the hash table
void deleteElement(int key);
// displaying the full hash table
void displayHashTable();
};
//creating the hash table with the given table size
HashMapTable::HashMapTable(intts)
{
this->table_size = ts;
table = new list<int>[table_size];
}
// insert function to push the keys in hash table
void HashMapTable::insertElement(int key)
{
int index = hashFunction(key);
table[index].push_back(key);
}
// delete function to delete the element from the hash table
void HashMapTable::deleteElement(int key)
{
int index = hashFunction(key);
// finding the key at the computed index
list <int> :: iterator i;
for (i = table[index].begin(); i != table[index].end(); i++)
{
if (*i == key)
break;
}
// removing the key from hash table if found
if (i != table[index].end())
table[index].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/ current index
for (auto j : table[i])
cout<< " ==> " << j;
cout<<endl;
}
}
// Main function
intmain()
{
// array of all the keys to be inserted in hash table
intarr[] = {20, 34, 56, 54, 76, 87};
int n = sizeof(arr)/sizeof(arr[0]);
// table_size of hash table as 6
HashMapTableht(6);
for (inti = 0; i< n; i++)
ht.insertElement(arr[i]);
// deleting element 34 from the hash table
ht.deleteElement(34);
// displaying the final data of hash table
ht.displayHashTable();
return 0;
}

Output:

C++ Hash Table-1.1

Explanation: In the above code, an array is created for all the keys that need to be inserted in the has table. Class and constructors are created for hashMapTable to calculate the hash function using the formula mentioned above. The list is created as the pointer to the array of key values. Specific functions are created for the insertion, deletion, and display of the hash table and called from the main method. While insertion, if 2 or more elements have the same index, they are inserted using the list one after the other.

Conclusion

The above description clearly explains what a hash table in C++ and how it is used in programs to store the key value pairs. Hash tables are used as they are very fast to access and process the data. There are many chances of collisions while calculating the index using a hash function. We should always look for the methods that will help in preventing the collision. So one needs to be very careful while implementing it in the program.

Recommended Articles

This is a guide to C++ Hash Table. Here we also discuss the definition and algorithm of a hash table in c++ along with different examples and its code implementation. You may also have a look at the following articles to learn more –

  1. C++ Static
  2. C++ static_cast
  3. C++ find_if()
  4. C++ fstream

C++ Training (4 Courses, 5 Projects, 4 Quizzes)

4 Online Courses

5 Hands-on Projects

37+ Hours

Verifiable Certificate of Completion

Lifetime Access

4 Quizzes with Solutions

Learn More

0 Shares
Share
Tweet
Share
Primary Sidebar
C plus plus Programming Tutorial
  • Advanced
    • C++ namespace
    • Encapsulation in C++
    • Access Modifiers in C++
    • Abstract Class in C++
    • C++ Class and Object
    • What is Template Class in C++?
    • C++ Algorithm
    • Data Structures and Algorithms C++
    • C++ Garbage Collection
    • Virtual Keyword in C++
    • Access Specifiers in C++
    • Storage Class in C++
    • Call by Value in C++
    • Multimap in C++
    • C++ Multiset
    • C++ Lambda Expressions
    • Stack in C++
    • C++ Static
    • C++ static_cast
    • Deque in C++
    • C++ Vector Functions
    • C++ 2D Vector
    • C++ List
    • C++ Mutable
    • Enum in C++
    • Abstraction in C++
    • Signal in C++
    • C++ Queue
    • Priority Queue in C++
    • Regular Expressions in C++
    • C++ Hash Table
    • C++ Expression
    • File Handling in C++
    • C++ Stream
    • ifstream in C++
    • C++ ofstream
    • C++ fstream
    • C++ Read File
    • C++ iomanip
    • Macros in C++
    • Templates in C++
    • C++ setprecision
    • C++ Int to String
    • C++ thread( )
    • C++ Thread Pool
    • C++ thread_local
  • Basic
    • Introduction To C++
    • What is C++
    • Features of C++
    • Applications of C++
    • Best C++ Compiler
    • C++ Data Types
    • C++ Double
    • C++ unsigned int
    • User Defined Data Types in C++
    • Variables in C++
    • C++ Keywords
    • Pointers in C++
    • C++ Void Pointer
    • Function Pointer in C++
    • Iterator in C++
    • C++ Commands
    • Object in C++
    • C++ Literals
    • C++ Reference
    • C++ Undefined Reference
    • String in C++
    • C++ Programming Language (Basics)
    • C++ Identifiers
    • C++ Header Files
    • Type Casting in C++
    • C++ Formatter
  • Operators
    • C++ Operators
    • Arithmetic Operators in C++
    • Assignment Operators in C++
    • Bitwise Operators in C++
    • Relational Operators in C++
    • Boolean Operators in C++
    • Unary Operators in C++
    • C++ Operator[]
    • Operator Precedence in C++
    • C++ operator=()
  • Control Statements
    • Control Statement in C++
    • if else Statement in C++
    • Else If in C++
    • Nested if in C++
    • Continue Statement in C++
    • Break Statement in C++
    • Switch Statement in C++
    • goto Statement in C++
    • C++ Struct
    • Loops in C++
    • Do While Loop in C++
    • Nested Loop in C++
  • Functions
    • C++ getline()
    • C++ String Functions
    • Math Functions in C++
    • Friend Function in C++
    • Recursive Function in C++
    • Virtual Functions in C++
    • strcat() in C++
    • swap() in C++
    • strcmp() in C++
    • ceil function in C++
    • C++ begin()
    • size() in C++
    • C++ test()
    • C++ any()
    • C++ Bitset
    • C++ find()
    • C++?Aggregation
    • C++?String append
    • C++ String Copy
    • C++ end()
    • C++ endl
    • C++ push_back
    • C++ shuffle()
    • malloc() in C++
    • C++ reserve()
    • C++ unique()
    • C++ sort()
    • C++ find_if()
    • Reflection in C++
    • C++ replace()
    • C++ search()
    • C++ Memset
    • C++ size_t
    • C++ Substring
    • C++ Max
    • C++ absolute value
    • C++ memcpy
    • C++ wchar_t
    • C++ free()
    • C++ pair
    • C++ this
    • C++ sizeof()
    • C++ Move Semantics
  • Array
    • Arrays in C++
    • 2D Arrays in C++
    • 3D Arrays in C++
    • Multi-Dimensional Arrays in C++
    • C++ Array Functions
    • String Array in C++
    • C++ Length of Array
    • C++ arraylist
  • Constuctor and Destructor
    • Constructor and Destructor in C++
    • Constructor in C++
    • Destructor in C++
    • Copy Constructor in C++
    • Parameterized Constructor in C++
  • Overloading and overriding
    • Overloading and Overriding in C++
    • Overloading in C++
    • Overriding in C++
    • Function Overloading in C++
    • Function Overriding in C++
    • Method Overloading in C++
  • Inhertiance
    • Types of Inheritance in C++
    • Single Inheritance in C++
    • Multiple Inheritance in C++
    • Hierarchical Inheritance in C++
    • Multilevel Inheritance in C++
    • Hybrid Inheritance in C++
  • Sorting
    • Sorting in C++ 
    • Heap Sort in C++
    • C++ Vector Sort
    • Insertion Sort in C++
    • Selection Sort in C++
    • C++ QuickSort
    • Sort string C++
  • Programs
    • Patterns in C++
    • Star Patterns In c++
    • Swapping in C++
    • Reverse Number in C++
    • Palindrome Program in C++
    • Palindrome in C++
    • Factorial Program in C++
    • Fibonacci Series in C++
    • Square Root in C++
    • Random Number Generator in C++
    • Prime Number in C++
    • Leap Year Program in C++
    • Anagram in C++
    • Armstrong Number in C++
    • Reverse String in C++
    • Socket Programming in C++
    • Matrix Multiplication in C++
    • C++ using vs typedef
    • C++ vector vs list
    • C++ vector vs array
  • Interview question
    • C++ Interview Questions
    • Multithreading Interview Questions C++

Related Courses

C++ Training Course

Java Training Course

C Programming Course

Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Java Tutorials
  • Python Tutorials
  • All Tutorials
Certification Courses
  • All Courses
  • Software Development Course - All in One Bundle
  • Become a Python Developer
  • Java Course
  • Become a Selenium Automation Tester
  • Become an IoT Developer
  • ASP.NET Course
  • VB.NET Course
  • PHP Course

© 2020 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA Login

Forgot Password?

EDUCBA
Free Software Development Course

Web development, programming languages, Software testing & others

*Please provide your correct email id. Login details for this Free course will be emailed to you
Book Your One Instructor : One Learner Free Class

Let’s Get Started

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA
Free Software Development Course

Web development, programming languages, Software testing & others

*Please provide your correct email id. Login details for this Free course will be emailed to you

Special Offer - C++ Training (4 Courses, 5 Projects, 4 Quizzes) Learn More