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

                                                   (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)² =  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.