7,154 views
3 votes
3 votes
I am unable to understand the meaning of probe sequence in context of no of slots , I have seen questions like no of probe sequences possible in quadratic or linear probing is m while in double hashing it is m^2 , so what is the significance of this probe sequence , is it that once collision occurs , so now to which index will the key would be next mapped on to ?

2 Answers

Best answer
4 votes
4 votes
Sequence of slots examined during a key search constitutes probe sequence.Probe sequence must be permutation of slot numbers.We examine every slot in the table if we have to.But no slot is examined more than once.
selected by
2 votes
2 votes

Mainly , a collision is resolved by Probing (a collision resolving strategy) in Hashing.

 Linear probing      -->  Rehash(key) = (n + 1) % table size .

Quadratic probing --> Rehash(key) = (n+k*k) % table size.   [ k needs to be increased till the  collision is resolved  like k = 1,2,3,.. ]

  Example - (Quadratic probing) --> table size = 11  &  --> function = (key) mod 11

       Keys   -->   31 , 19 , 2 , 13 , 25 .

    -->    31 mod 11 = 9          

     -->     19 mod 11 = 8

    -->     2 mod 11 = 2

    -->     13 mod 11 = 2  (already element  there so collision) .

          = (2 + 1*1) mod 11 = 3  (empty collision resolved) .

   -->      25 mod 11 = 3 ( element already there collision) .

          =  (3 + 1*1) mod 11 = 4  (empty collision resolved).

                                

0-->
1-->
2-->               2
3-->              13
4-->              25

5-->

6-->
7-->            
8-->             19
9-->             31
10-->

     

         -->   Others can be done in similar way .

edited by

Related questions

2 votes
2 votes
1 answer
1
2 votes
2 votes
1 answer
3
Meenakshi Sharma asked May 24, 2018
2,671 views
what is the meaning of $HOP , HOST , NODE, END$ in networking are they same or differentI mean $\text{host to host , hop to hop, end to end , node to node}$ how they d...