Different types of Hash function














































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. 


Comments