Hashing

Hashing is a searching technique based on hash table and the application of a function to the key value that result in mapping the range of possible key values into smaller range of relative address.

Type of hashing function

1) Direct Hashing:-The direct hashing is a no algorithm and not collision (Minimum no. of collision).
                               Limited and It is not suitable for large key values.

2) Modulo-Division Hashing:-

      - Middle of square
      - Key is squared and the address is selected from the middle of the square no.
      - Problem-Non - Uniform distribution of the key.

         
    

K²= (9452)²

K   =   9452

    =     89   3403   04

H(K) = 3403

Folding Hashing

            Fold-shift hashing :-

                     Key value is divides into parts where size matches the size of the required address.

      

                                  K = 123456789                             { 3 }

                                 K = 123   456   789                      ( 123 + 456 + 789 )

                              H(K) = 368                         

           

             Fold-boundary hashing:-

                          Left and Right no. are folded on a fixed boundary between them and the center no

                                                     K = 123  456  789

                                                                     ( 321 + 456 + 987 )

                                      

                                                     H(7) = 764.   

Pseudo Random Hashing :-

     Y = ax + c

    x=key

      a  =  choose coefficient  

     c = constant

      n = list size

H(K) = Y mod n

      Y = random no.

       a = 121267

        x = 17

         c = 7

     Y = 2061546        

    H(K) = 2061546  mod n

        

                  collision Resolution

Subtraction Hashing :-

      Subtract a fixed no from key

     H(K)  = K - c

  

   c is a fixed no.

- Like direct hashing

- No collision

- Suitable for small lists