What is a Hash Table?

Hashing

Until now, the overall time complexity accomplished in cases of insertion, deletion, and searching approach O(nLogn), or at O(Logn) at minimum in balanced Binary Trees, which is pretty good. But what to do if we want the results in constant time!?

🔍 Hashing, How and Why?

Hashing is a process used to uniquely identify objects and store each object at some pre-calculated unique index called its key. So the object is stored in the form of a key-value pair, and the collection of such items is called “Dictionary”. Each object can be searched using that key in O(1).

For a significantly large amount of data, even O(nLogn) becomes significantly large which might affect the efficiency of an algorithm. Ideally, a data structure is required that takes a constant amount of time to perform all three operations to manage a large number of records, and that is where Hashing comes in handy!

It can make searching a bit complex, but now fetching time is substantially reduced. There are different data structures based on Hashing, but the most commonly used data structure is a Hash Table.

Hash Tables

The major target of Hash Tables is to minimize the searching time of any sort of data that needs to be fetched.

The Working

Hash Tables are generally implemented using Arrays, as they are the only data structures that provide access to elements in constant O(1) time.

Let us explain how!

Key-Value Pair

So the idea of data retrieval in O(1) is executed by using a key to map the data on an array (there are many ways to compute this key). In the case of arrays, you can directly use the key as an index to store data. If you pass the key to the array, the value is retrieved; alternatively (in the most naive form),

$$value = arr[key]$$

Here’s an illustration of how a Hash Table is mapped to the indices (1,2,3,…,5) in an array, with the index of this array calculated through a Hash function. (Hash function will be discussed later)