Umesh Chandra

Hashing is a technique which is used to search for an element in the less time complexity. Already we have Linear search and Binary search which uses the O(n) and O(log n) time complexity. To reduce the time complexity than any other data structure hashing concept is introduced which has O(1) time in the average case and the worst case it will take O(n) time.

Hashing is a technique with faster access to elements that maps the given data with a lesser key for comparisons. In general, in this technique, the keys are traced using hash function into a table known as the hash table.

---

What is Hash Function?

The hash function is a function that uses the constant-time operation to store and retrieve the value from the hash table, which is applied on the keys as integers and this is used as the address for values in the hash table.

Types of Hashing Functions

We have 3 three different Hashing Functions in C language:

• Division Method or Mod Method
• Mid Square Method
• Digit Folding Method

---

Division Method or Mod Method

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

Hash(key) = Elements % SIZE

Example:

If the elements to be placed in the hash table are 11, 22, 33, 44, 55 and let’s take the table size as 10.

1 = 11%10

2 = 22%10

3 = 33%10

4 = 44%10

5 = 55%10

Now the hash table will look as

0
1	11
2	22
3	33
4	44
5	55
6
7
8
9

---

Mid Square Method

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

If elements to be placed in the hash table are 210, 350, 99, 890 and 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.

---

Digit Folding Method

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

If 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 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 points to 2nd place in the table, where it is not possible to write both at the same place such problem is known as a collision. To avoid this kind of problems there are some techniques of hash functions that can be used.