# Hashing in data structure with its types

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.

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