Solve hash table example using division method, mid square method, folding method.

1. Division Method:

This is the most simple and easiest method to generate a hash value. The hash function divides the value k by M and then uses the remainder obtained.

Formula:

h(K) = k mod M

Here,
k is the key value, and 
M is the size of the hash table.

It is best suited that M is a prime number as that can make sure the keys are more uniformly distributed. The hash function is dependent upon the remainder of a division. 

Example:

k = 12345
M = 95
h(12345) = 12345 mod 95 
               = 90

k = 1276
M = 11
h(1276) = 1276 mod 11 
             = 0

2. Mid Square Method:

The mid-square method is a very good hashing method. It involves two steps to compute the hash value-

  1. Square the value of the key k i.e. k2
  2. Extract the middle r digits as the hash value.

Formula:

h(K) = h(k x k)

Here,
k is the key value. 

The value of r can be decided based on the size of the table.

Example:

Suppose the hash table has 100 memory locations. So r = 2 because two digits are required to map the key to the memory location.

k = 60
k x k = 60 x 60
        = 3600
h(60) = 60

The hash value obtained is 60

3. Digit Folding Method:

This method involves two steps:

  1. Divide the key-value k into a number of parts i.e. k1, k2, k3,….,kn, where each part has the same number of digits except for the last part that can have lesser digits than the other parts.
  2. Add the individual parts. The hash value is obtained by ignoring the last carry if any.

Formula:

k = k1, k2, k3, k4, ….., kn
s = k1+ k2 + k3 + k4 +….+ kn
h(K)= s

Here,
s is obtained by adding the parts of the key k

Example:

k = 12345
k1 = 12, k2 = 34, k3 = 5
s = k1 + k2 + k3
  = 12 + 34 + 5
  = 51 

h(K) = 51