Data Structures and Algorithms - Old Questions

10. What is hashing? Discuss rehashing with example.

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.

E.g. 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

Rehashing

Rehashing is a collision resolution technique.

Rehashing is a technique in which the table is resized, i.e., the size of table is doubled by creating a new table. It is preferable is the total size of table is a prime number. There are situations in which the rehashing is required.

•  When table is completely full

•  With quadratic probing when the table is filled half.

•  When insertions fail due to overflow.

In such situations, we have to transfer entries from old table to the new table by re computing their positions using hash functions.

Consider we have to insert the elements 37, 90, 55, 22, 17, 49, and 87. the table size is 10 and will use hash function:

H(key) = key mod tablesize

37 % 10 = 7

90 % 10= 0

55 % 10 = 5

22 % 10 = 2

17 % 10 = 7

49 % 10 = 9

Now this table is almost full and if we try to insert more elements collisions will occur and eventually further insertions will fail. Hence we will rehash by doubling the table size. The old table size is 10 then we should double this size for new table, that becomes 20. But 20 is not a prime number, we will prefer to make the table size as 23. And new hash function will be

H(key) key mod 23 

37 % 23 = 14 

90 % 23 = 21 

55 % 23 = 9 

22 % 23 = 22 

17 % 23 = 17 

49 % 23 = 3 

87 % 23 = 18

Now the hash table is sufficiently large to accommodate new insertions.