Hash Function in Data Structure

Hash Function:

A hash function can be defined as a function that takes a key (k) as input and provides a bucket index as output.

H(k)=L

Where H is a hash function.
K is a set of keys.
L is a bucket index.

There are three types of hash functions are given below:
1. Division Method
2. Middle Square Method
3. Folding Method

Division Method:

It is the simplest of all the methods of hashing a key k is to divide k by M and then use the remainder as the bucket index. This is called the Division Method. In this case, the function is:

H(k)=k mod M

Algorithm for Division Method:

Algorithm fnDivision(k, M)
{
L=k%M;
return L;
} // End of Algorithm

Middle Square Method:

In the Middle Square Method, the key k is squared and then some particulars bits from the middle of k² are extracted to get the desired key. The positions of these particular bits are the same for all the keys.

H(k)=some bits of k²

Algorithm for Middle Square Method:

Algorithm fnMidSquare(k, m1, m2)
{
k1=k*k/10^(m1-1);
L=k1%10^(m2-m1+1);
return L;
} // End of Algorithm

Folding Method:

In Folding Method, the key k is partitioned into a number of parts k1, k2, k3,…kr where each part except possibly the last has the same number of digits as the required address. Then the parts are added together ignoring the last carry. Therefore the hash function is:

H(k)=k1 + k2 + k3 +…+kr
where the carry is ignored.

Algorithm for Folding Method:

Algorithm fnFolding(k)
{
q=1;
p=0;
L=0;
while(k!=0)
{
p=p+10q*(k%10);
k=k/10;
q=q+1;
if(q=size of each partition)
{
L=L+p;
p=0;
q=0;
}
}
if(length of L > size of each partition)
Discard the MSB from L;
return L;
}