3.4.1 Rehashing Methods

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) + C₁i + C₂i²) mod m
3.: Double Hashing; h(x, i) = (h(x) + i $\displaystyle \underbrace{h'(x))}_{\begin{array}{l}{\rm another}\\{\rm hash }\\{\rm function}\end{array}}^{}\,$ mod m

A Comparison of Rehashing Methods

$\fbox{Linear Probing}$ m distinct probe Primary clustering

sequences

$\fbox{Quadratic Probing}$ m distinct probe No primary clustering;

sequences but secondary clustering

$\fbox{Double Hashing}$ m² distinct probe No primary clustering

sequences No secondary clustering

eEL,CSA_Dept,IISc,Bangalore

$\fbox{Linear Probing}$	m distinct probe	Primary clustering
	sequences

$\fbox{Quadratic Probing}$	m distinct probe	No primary clustering;
	sequences	but secondary clustering

$\fbox{Double Hashing}$	m² distinct probe	No primary clustering
	sequences	No secondary clustering