Data Structures and Algorithms - Old Questions

10. What are Hashing and collision? Write about any three hashing algorithms.

Hashing is a well-known technique to search any particular element among several elements. It minimizes the number of comparisons while performing the search. 

In hashing, an array data structure called as Hash table is used to store the data items. Hash table is a data structure used for storing and retrieving data very quickly. Insertion of data in the hash table is based on the key value. Hence every entry in the hash table is associated with some key. Using the hash key the required piece of data can be searched in the hash table by few or more key comparisons.

    Fig: Hashing Mechanism

Hash function is a function which is used to put the data in the hash table. Hence one can use the same hash function to retrieve the data from the hash table. Thus hash function is used to implement the hash table. The integer returned by the hash function is called hash key.

Collision

The situation in which the hash function returns the same hash key for more than one record is called collision. For e.g.

Consider a hash function:

H(key) = recordkey%10 having the hash table size of 10

The record keys to be placed are: 131, 44, 43, 78, 19, 36, 57 and 77

131%10= 1

44%10=4

43%10=3

78%10=8

19%10=9

36%10=6

57%10=7

77%10=7

Now if we try to place 77 in the hash table then we get the hash key to be 7 and at index 7 already the record key 57 is placed. This situation is called collision. 

Hashing algorithms/ Functions

1. Division Hash Function:

The division hash function depends upon the remainder of division. Typically the divisor is table length. For e.g. If the record 54, 72, 89, 37 is placed in the hash table and if the table size is 10 then the hash function is:

h(key) = record % table size

and key obtained by hash function is called hash key.

54%10=4 

72%10=2 

89%10=9 

37%10=7

2. Mid Square Hash Function:

In the mid square method, the key is squared and the middle or mid part of the result is used as the index. If the key is a string, it has to be preprocessed to produce a number.

Consider that if we want to place a record 3111 then

3111² = 9678321

for the hash table of size 1000

H(3111) = 783  (the middle 3 digits)

3. Multiplicative Hash Function:

The given record is multiplied by some constant value. The formula for computing the hash key is

H(key) = floor(p *(fractional part of key*A))   where p is integer constant and A is constant real number.

Donald Knuth suggested to use constant A = 0.61803398987

If key 107 and p=50 then

H(key) = floor(50*(107*0.61803398987))

     = floor(3306.4818458045)

     = 3306

At 3306 location in the hash table the record 107 will be placed