What is a Hash Table?

Hashing

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

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 Python, hash tables are generally implemented using lists as they provide access to elements in constant time.

In Python, we have several in-built types such as set and dict which can provide us the hash table functionality.