# What is a Hash Table?

A brief introduction on Hash Tables and the use of the Hash function, along with some strategies to build it.

## 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)

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.