 ### Different types of Hash function

Different types of hash function:

1.       Division Method

The hash function depends upon the  remainder of divisor.

Typically divisor is table size.

If the record  43,  65 ,  77 ,  90 are to be inserted in a table of size 10

Then the  hash function= record % table-size,

H(43)  =  43 % 10  = 3

H(65)  =  65 % 10  =  5

H(77)  =  77 %10  = 7

H(90)  =  90 %10  =  0

0            1          2            3          4            5         6             7          8            9

 90 43 65 77

(hash-table)

Multiplicative hash function

Step-1 The multiplicative hash function works in following way

Multiply the key (say k) by a constant  'A' where 0<A<1,

then extract the fraction part of kA

Step-2  Multiply this fraction part by m and tak the  floor.

The above steps can be formulated as

H(k) = [m {kA}].

Donald Knuth suggested to take  A=0.61803398987.

Lets see one example

Key= 107  suppose   m=50 and A=0.61803398987.

H(k) = [50 { 107 * 0.61803398987 }]

=   [50 * { 66.12 } ]

=   [50*0.12]

=   6

That means, 107 will be placed at position  6 .

Extraction

In this method some digit are extracted from the key to form address location in the hash table.

For example suppose  876902 is to be placed in hash table of size 1000.

And hash function says extract  second, third and fifth digit from left

Then the address location is 760.

Mid  square

This method works in following steps

Square the key

Extract middle part of the square. This will indicate he location of key in hash table.

Let key = 2119

(2119)2 =  44,90,161

For hash table of size 1000

H(key)=  901.

Folding

There are 2 folding technique

i)     Fold shift

ii)    Fold boundary

Fold shift :  In this method , the key is divided into separate part whose size matches with the hash

table size. Then the left part and right part are shift with the middle part

For example : key= 345987132 is to hashed in table size 1000

345          |             987               |           132

Left                       middle                        right

H(key) =       345

+   987

+    132

______________

1  464

1 will be discarded and the H(key) = 464

Fold Boundary :  in  this method , the key is divided into separate part whose size matches with the
hash table size. Then the left part and right part are reversed and shifted
with the
middle part

For example : key= 345987132 is to hashed in table size 1000

345          |             987               |           132

Left                       middle                           right

H(key) =       543   (reversed)

+   987

+    231    (reversed)

______________

1  761

1 will be discarded and the H(key) = 761. 