How to Implement Hash Tables in C++
Get a deeper understanding of how hash tables work under the hood by implementing them in C++.
Introduction
One of the most important data structures that is widely used is the Hash Table. All major programming languages come with hash table implementations that we can work with. Usually, we don’t need to implement it ourselves. For example, the C++ STL has std::unordered_map and std::unordered_set which implement hash tables under the hood.
This article explains how a Hash Table is implemented in C++ so you know why it behaves a certain way when debugging problems and also know how to improve its performance, and most importantly when to use it and when not to use it.
Hash Table Building Blocks
According to Wikipedia, a hash table — also called a hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values.
Most of us know it as a two-column, key and value table as shown below.
The table above is a hash table with both key and value are of type integer. Another form of hash table is when keys are also values, meaning there is only one column, this is what std::unordered_set implements. In this article, we implement a two-column…
