Rehashing

Rehashing:  

        Rehashing   is  a technique  in which  the   table  size  is  resized  i.e  the  size  of  table  is  doubled  by  creating  a  new  table  .It  is  preferable   if  the  total   size   of  table  is  a  prime  number.

There  are  situations in which  rehashing  is  required:    

Ø  When  table  is  completely  full.

Ø  With  quadratic  probing  when  the   table   is  filled  half

Ø  When  insertion  fail  due  to  overflow.

In  such  situations  we  have   transfer  entries  from  the  old  table  to  the new  table    by  recombining   their  positions  using  suitable  hash  functions.

Example:

  Consider  the  elements  to  be  inserted  37,90,55,22,12,49  87.The  table  size  is  10.We  use  hash  function  H(key)=key  mod size

·         Insert  37,90,55,22,17  and 49  using    hash  function

     H(key)=key mod size

     H(37)=37%10=7

     H(90)=90%10=0

     H(55)=55%10=5

     H(22)=22%10=2

    H(17)=17%10=7(collision  solved by  linear probing)

    H(49) =49%10=9

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

90

22

55

37

17

49

·         While   inserting  87  collision  occurs .By linear  probing  we  cant  insert this  element  in the  hash  table  because   this  table  is  almost full  and  if  we  try  to  insret  more  elements  collision  will  occur   and  eventually  further  will  fail .Hence  we  will  rehash  by  doubling  the table  size.The old  table  is10  then  we  should  double    this  size   for  the  new  table. It becomes 20 .But  20  is  not  a  prime  number we  will prefer  make  the  table  size  as 23 .And  the  new  hash function will be

         

          H(key)=key  mod 23

          H(37)=37%23=14

          H(90)=90%23=21

          H(55)=55%23=9

          H(22)=22%23=22

          H(17)=17%23=17(collision solved  by  linear probing)

          H(49)=49%23=3

          H(87)=87%23=18

·         Now   the   hash  table  is  sufficiently   large  to   accommodates  new  insertion

               [0] [1] [2] [3]   [4] [5][6][7][8][9][10][11][12][13][14][15][16][17][18][19][20][21][22]

49

55

37

17

87

90

22

Advantages:

Ø  This  technique  provides   the  programmer  a  flexibility  to  enlarge the  table  size  if  required.

Ø  Only  the  space  gets  doubled  with  simple   hash function which  avoids  the  occurrence  of  collision.

Probe   Sequence