Hash Functions and Its Types

What is Hash Function?

In a hash table, a new index is processed using the keys. And, the element corresponding to that key is stored in the index. This process is called the hashing(hash function).

Types of a Hash Function In C

The types of hash functions are explained below:

1. Division method

In this method, the hash function is dependent upon the remainder of a division.

Example:- elements to be placed in a hash table are 42,78,89,64 and let’s take table size as 10.

Hash (key) = Elements % table size;

2 = 42 % 10;

8 = 78 % 10;

9 = 89 % 10;

4 = 64 % 10;

The table representation can be seen as below:

2. Mid Square Method

In this method, the middle part of the squared element is taken as the index.

Element to be placed in the hash table are 210, 350, 99, 890 and the size of the table be 100.

210* 210 = 44100, index = 1 as the middle part of the result (44100) is 1.

350* 350 = 122500, index = 25 as the middle part of the result (122500) is 25.

99* 99 = 9801, index = 80 as the middle part of the result (9801) is 80.

890* 890 = 792100, index = 21 as the middle part of the result (792100) is 21.

3. Digit Folding Method

In this method the element to be placed in the table uh is a sing hash key, which is obtained by dividing the elements into various parts and then combining the parts by performing some simple mathematical operations.

Elements to be placed are 23576623, 34687734.

hash (key) = 235+766+23 = 1024

hash key) = 34+68+77+34 = 213

In these types of hashing suppose we have numbers from 1- 100 and the size of hash table =10. Elements = 23, 12, 32

Hash (key) = 23 % 10 = 3;

Hash (key) = 12 % 10 = 2;

Hash (key) = 32 % 10 = 2;

From the above example notice that both elements 12 and 32 point to 2nd place in the table, where it is not possible to write both at the same place such a problem is known as a collision. To avoid this kind of problem there are some techniques of hash functions that can be used.

What is Hash Collision?

When the hash function generates the same index for multiple keys, there will be a conflict (what value to be stored in that index). This is called a hash collision.

We can resolve the hash collision using one of the following techniques.

• Collision resolution by chaining
• Open Addressing: Linear/Quadratic Probing and Double Hashing

1. Chaining

This method as the name suggests provides a chain of boxes for the record in the table having two entries of elements. So whenever such collisions occur then the boxes act as a linked list will be formed.

Example: 23, 12, 32 with table size 10.

Hash (key) = 23 % 10 = 3;

Hash (key) = 12 % 10 =2;

Hash (key) = 32 % 10 =2;

2. Open Addressing

Linear Probing:

This is another method for solving collision problems. As the name says whenever a collision occurs then two elements should be placed on the same entry in the table, but by this method, we can search for the next space or entry in the table and place the second element. This can again lead to another problem; if we do not find any empty entry in the table then it leads to clustering. Thus this is known as a clustering problem, which can be solved by the following method.

Example: 23, 12, 32 with table size 10

Hash (key) = 23 % 10 = 3;

Hash (key) = 12 % 10 =2;

Hash (key) = 32 % 10 =2;

In this diagram 12 and 32 can be placed in the same entry with index 2 but by this method, they are placed linearly.

Quadratic probing:

This method is a resolution for the clustering problem during linear probing. In this method the hash function with hash key is calculated as hash (key) = (hash (key) + x * x) % size of the table (where x =0, 1, 2 …).

Example: 23, 12, 32 with table size 10

Hash (key) = 23 % 10 = 3;

Hash (key) = 12 % 10 =2;

Hash (key) = 32 % 10 =2;

In this, we can see that 23 and 12 can be placed easily but 32 cannot as again 12 and 32 share the same entry with the same index in the table, as per this method hash (key) = (32 + 1*1) %, 10 = 3. But in this case table entry with index 3 is placed with 23 so we have to increment x value by 1. Hash (key) = (32 + 2 * 2) % 10 = 6. So we now can place 32 in the entry with index 6 in the table.

Double hashing:

In this method, we have to calculate 2 hash functions to resolve the collision problem. The first is calculated using a simple division method. The second has to satisfy two rules; it must not be equal to 0 and entries must be probed.

• 1 (key) = key % size of the table.
• 2 (key) = p – (key mod p), where p is prime numbers < size of the table.

Example: 23, 12, 32 with table size 10

Hash (key) = 23 % 10 = 3;

Hash (key) = 12 % 10 =2;

Hash (key) = 32 % 10 =2;

In this again the element 32 can be placed using hash2 (key) = 5 – (32 % 5) = 3. So 32 can be placed at index 5 in the table which is empty as we have to jump 3 entries to place it.

Conclusion

Hashing is one of the important techniques in terms of searching data provided with very efficient and quick methods using a hash function and hash tables. Each element can be searched and placed using different hashing methods. This technique is very faster than any other data structure in terms of time coefficient.