![next](http://lcm.csa.iisc.ernet.in/dsa/next_motif.gif)
![up](http://lcm.csa.iisc.ernet.in/dsa/up_motif.gif)
Next:3.4.2
An Example:Up:3.4
Closed HashingPrevious:3.4
Closed Hashing
3.4.1 Rehashing Methods
Denote h(x, 0) by simply h(x).
-
1.
-
Linear probing
-
-
h(x, i) = (h(x) + i) mod
m
-
-
2.
-
Quadratic Probing
-
-
h(x, i) = (h(x) + C1i
+ C2i2) mod m
-
where C1 and C2 are constants.
-
3.
-
Double Hashing
-
h(x, i) = (h(x) + i
mod m
A Comparison of Rehashing Methods
![\fbox{Linear Probing}](img62.gif) |
m distinct probe |
Primary clustering |
|
sequences |
|
|
|
|
![\fbox{Quadratic Probing}](img63.gif) |
m distinct probe |
No primary clustering; |
|
sequences |
but secondary clustering |
|
|
|
![\fbox{Double Hashing}](img64.gif) |
m2 distinct probe |
No primary clustering |
|
sequences |
No secondary clustering |
eEL,CSA_Dept,IISc,Bangalore