What is a Hash Table?

Hashing #

Until now, the overall time complexity accomplished by most of the data structures in insertion, deletion, and the search was up to O(logn), which is pretty good. But for a significantly large amount of data, this complexity starts to affect the efficiency of an algorithm adversely.

The ideal data structure is one that takes a constant amount of time to perform all three operations. And that is where hashing steps into the spotlight!

Hashing is a process used to store an object according to a unique key. This means that hashing always creates a key-value pair. A collection of such pairs forms a dictionary where every object or value can be looked up according to its key. Hence, the search operation can be performed in O(1).

The concept of hashing has given birth to several new data structures, but the most prominent one is the hash table.

Hash Tables #

If your algorithm prioritizes search operations, then a hash table is the best data structure for you. In C++, hash tables are generally implemented using arrays as they provide access to elements in constant time. Look at the figure below to see how key and data pairs are stored in a hash table.