Quadratic probing

2.Quadratic probing:

                             Quadratic probing is another method for resolving collisions in hash tables.It operates by taking the original hash value and adding successive values of a quadratic polynomial to the starting value. Quadratic probing avoids the clustering problem that occur with linear probing and may also result in probing the same setoff alternate cells.

                            In this method when a collision occurs at a location 1,probe bucket 1+1,1+4-----,1+9 where as in linear probing probes bucket at location 1+1,1+2,1+3---etc.

	In general  this method  probes buckets at location  using  formula                       h(x)=(h(x)+i2)mod n

 

 Where i=1,2,3,--------

                     h(x) is the starting value or key value

                     n is the size of the hash table or any prime number.

Ø  Quadratic probing may also result in probing the same set of alternative cells and this is known as secondary clustering, which occurs when hash table size is not a prime number.

Ø  If n is prime number then quadratic probing probes exactly half of the number of locations in the hash table.

The  following  algorithm   denotes  insertion on a  table   using   quadratic  probing: 

ALGORITHM:QINSERT(key,r)

     1.Set  i=h(key)

     2.Set c=0

     3.Loop while (c<m)and(not empty(r[i])))and(not deleted r[i])) and (r[i],k< >key)do

     4.Set i=(i+c+1)mod m

     5.Set c=c+2

     6.End loop

     7.Check whether  empty  (r[i]) or deleted(r[i])then

    8.Set r[i]_k=key

    9.Set n=n+1

   10.Else  write “table full,or key already  in  table”

   11.End

The  following  algorithm  denotes  insertion  on a table  using  quadratic   probing:

Algorithm:

    1.Set  i=h(key)

    2.c=increament (key)

    3.set last=(i+(n-1)*c)mod m

    4.loop  while (i<last) and (not empty (r[i]))and (r[i],k<key)do

    5.   set i=(i+c)mod n

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

    7.value =1

    8.   Else

    9.value=-1

    10. End

Example:

   Insert   the  following  elements  in the hash table  with  table  size 10.

                               37,90,55,22,11,17,49,87

Ø  While   inserting   37,90,55,22,11   there  will be   no  collisions

                h(x)=x  mod 10

                h(37)=37 mod 10=7

                h(90)=90 mod 10=0

                            h(55)=55 mod 10=5     

                            h(22)=22 mod  10=2

               h(11)=11 mod  10=1

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

90

11

22

55

37

     

Ø  Inserting  17  collision occurs  and  bucket  7  has  already  an  element  37.Hence  we  will  apply  quadratic  probing  to insert  this  record  in  the   hash  table.

              h(x)= x  mod  n

              h(17)=17 mod 10=7(collision)

using  quadratic  probing ,the next  free  location  will be  calculated  as

             h(x)=(h(x)+i² )mod n

                   =(17+0² ) mod 10  for i=0

                   =7(OCCUPIED state so  try  next  location)

Using  quadratic  probing   the  next  free  location   will  be  calculated  as

            h(x)=(h(x)+i² )mod  n

                   =(17+1² )mod 10  for  i=1

                   =8(EMPTY  state  so  insert 17 at  8^th location)

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

90

11

22

55

37

17

 

Ø  Insert   49   there  will  be  no  collision  because  9^th location  is  empty.

                      h(x)=x  mod  10

                     h(49)=49 mod  10=9(no  collision)

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

90

11

22

55

37

17

49

Ø  Insert  87  a  collision  occurs  and  bucket    7  has  already  an  element  37.Hence  we   will  apply  quadratic  probing  to  insert   this  record  in  the  hash  table.

                    h(x)=x  mod  10

                    h(87)=87 mod 10=7(collision)

using   quadratic  probing  the  next  free  location  will be  calculated  as

                   h(x)=(h(x)+i² ) mod  n

                            =(87+0²)mod 10  for  i=0

                            =7(OCCUPIED   state  so  try  next  location)

Using   quadratic  probing  the  next   location   will  be  calculated  as

                   h(x)=(h(x)+i² )mod  n

                          = (87+1² )mod  10

                          =8(OCCUPIED  state  so  try  next  location)

Using  quadratic  probing  the   next  free  location  will  be  calculated   as

                  h(x)=(h(x)+i² ) mod n

                          =(87+2² ) mod  10

                           =1(OCCUPIED  state  so  try  next  location)

Using  quadratic  probing   the  next  free  location   will  be  calculated  as

                  h(x)=(h(x)+i² ) mod  n

                          =(87+3² )  mod  10

                          =6(EMPTY state  so   insert 87 at 6^th location)

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

90

11

22

55

87

37

17

49

Ø  It  is   observed  that  if  we  want  to  place   all  the  necessary  elements  in the  hash  table  the  size  of  divisor  (n)  should be  twice  as  large  as  total  number  of  elements.

Probe   Sequence