Page Contents

Hashing is an approach to convert a larger key into a smaller integer value within a given limited range.

Here the key is a larger value that we need to store And the integer value is an address in the hash table where the key will be store.

To find integer address from key-value we have hashing function to calculate.

- Hashing technique is an efficient searching technique that minimizes the number of comparisons while performing the search.
- With the help of hashing, searching can be performed in a constant time O(1).
- It doesn’t depend upon the size of data, in all cases worst, best, and an average search performed in O(1).
- It is better than Linear search and binary search both where time complexity is O(n) and O(logn) respectively.

## What is hash function?

- A hash function maps key value to a small integer value.
- A hash function takes a key as an input and after applying some logic returns a small integer value which is known as the hash value.
- This hash value represents the original key value.
- This hash value of the key is used as an index to store the key into the hash table.

**Note:** Here Key is a value that is taken as input. This key can be a string or integer.

## What is hash value?

- Hash value is generated by the hash function.
- Hash value denotes where the key should store in the hash table.
- We can say that Hash value is the index value for the key.

## What is hash table?

- Hash table in data structure is a data structure that stores key-value pairs.
- Hash table uses a hash function to compute an index to store key-value pairs.
- Each index of the hash table is known as slots.

Let’s see an example to understand hashing and hash table.

- The above figure shows a hash table and the size of the above hash table is 10.
- It means this hash table has 10 slots which are denoted by {0, 1,2,3,4,5,6,7,8,9}.

Now we have to insert value **{12,56,33,65,71}** into hashtable. So to calculate slot/index value to store items we will use hashing concept.

Where hash function will calculate this index value which is also known as the hash value.

## Formula to calculate index / hash value

**index/hash value = Key value % size of array**

After computing hash values we can insert each value into the hash table.

Like if we have to **insert 12** then

**index/hash value = **12%10 = 2

So **12** will be inserted at **index 2** of the hash table shown above.

## Load factor

In the above example, only 5 slots are filled and the rest is empty in a hash table which is referred to as the **load factor**.

Load factor is denoted by lambda **๐**

Formula to calculate load factor (**๐**) is

load factor(**๐**) = No. of items/table size.

= 5/10

## Types of Hashing

- Open Hashing (Closed Addressing)
- Closed Hashing (Open Addressing)

This technique is used to minimize collision that occurs during hashing.

It is similar to collision resolution techniques.

Share On :