Double hashing

3.Double  hashing: 

              Double  hashing  is  technique  in  which  a  second  hash  function  is  applied  when  collision is  occurred .By  applying  the  second  hash  function  we  will  get  the  number of  positions  from  the  point  of  collision to  insert.

There   are  two  important  rules  to  be  followed  for  the   second  function:

Ø  It must  never  evaluate  to  zero

Ø  It  must  make  sure that cells  can be  probed.

	The   formula  to  be  used  for  double  hashing  is                         H1(key)=key mod  table size                         H2(key)=M-(key mod M)

 

Where  M is a  prime  number  smaller   than  the  size  of  the   table.

The  following  algorithm  denotes  the insertion  of  a  value  and  searching  of  value  from the table:

Algorithm:

  1.set i=h(key)

  2.set c= increament (key)

  3.Last =(i+(m-1)*c)%m

  4.Loop while  (i!=last &&!empty (r[i])&& !deleted(r[i])&&r[i].k!=key)

  5.set i=(i+c)%m

  6.check  whether  (empty (r[i])|| deleted (r[i])) then

  a)set  r[i].key=key

  b)set n=n+1

7. Else  write “table  full or  key  already in table”

8.End

Algorithm: Search(key ,r)

1.set i=h(key)

2.set c=increament(key)

3.Last=(i+(n-1)*c)%m

4.Loop  while  (i!=last&& !empty (r[i].k!=key)

5.set i=(i+c)%m

6.check whether r[i].key==key then

  return

7.else return(-1)

8.End

Example:

Consider  the following  elements  to  be  placed  in the  hash table  of  size 10

    37,90,45,22,17,49,55

·         Initially  insert  the  elements  37,90,45,22,49 there will be  no  collisions  .So using  the  formula  for  H₁(key)=key mod size

       H₁(37)=37%10=7

       H₁(90)=90%10=0

          H₁(45)=45%10=5

          H₁(22)=22%10=2

          H₁(49)=49%10=9

There are no  collisions  in the above elements.

   [0]         [1]            [2]         [3]          [4]          [5]          [6]            [7]        [8]           [9]

90

22

45

37

49

·         Now insert 17,collision occurs .so calculate second  hash function. Here  M   is  prime  number  smaller  than  the  size  of  the table.prime  number  smaller  than  the  table  size  10 is 7.

      H₁(17)=17%10=7(collision)

      H₂(key )=M-(key %M)

      H₂(17)=7-(17%7)

                 =7-3

                 =4

That means  we  have the  element 17 at  4^th place  from  37.In short  we  have  to  take  4  jumps. Therefore   17  will be  placed at  the index  1.

    [0]         [1]           [2]         [3]         [4]           [5]        [6]           [7]         [8]         [9]

90

17

22

45

37

49

  

H₁(55)=55%10=5(collision)

H₂(key)=M-(key %M)

H₂(55)=7-(55%7)

            =7-6

            =1

That  means  we  have  to  insert  the  element  55  at  1 place from  45.In  short  we   have  to  take  one  jump.Therefore  the 55  will be  placed  at  index  6.

    [0]         [1]          [2]         [3]          [4]         [5]          [6]          [7]           [8]       [9]

90

17

22

45

55

37

49

Probe   Sequence