Java Reference
In-Depth Information
0
1
2
3
4
5
6
key: 44
For simplicity, only the keys are
shown and not the values. Here
N is 11 and index = key % N.
New element with
key 26 to be inserted
key: 4
key: 16
key: 28
Quadratic probe 2
times before finding
an empty cell
.
.
.
7
8
9
10
key: 21
F
IGURE
27.4
Quadratic probing increases the next index in the sequence by
j
2
for
j
=
1,2,3,....
Quadratic probing works in the same way as linear probing except for a change in the
search sequence. Quadratic probing avoids linear probing's clustering problem, but it has its
own clustering problem, called
secondary clustering
; that is, the entries that collide with an
occupied entry use the same probe sequence.
Linear probing guarantees that an available cell can be found for insertion as long as the
table is not full. However, there is no such guarantee for quadratic probing.
secondary clustering
Pedagogical NOTE
For an interactive GUI demo to see how quadratic probing works, go to
www.cs.armstrong.
edu/liang/animation/HashingQuadraticProbingAnimation.html
,
as shown in Figure 27.5.
quadratic probing animation
on Companion Website
27.4.3 Double Hashing
Another open addressing scheme that avoids the clustering problem is known as
double hash-
ing
. Starting from the initial index
k
, both linear probing and quadratic probing add an incre-
ment to
k
to define a search sequence. The increment is
1
for linear probing and
j
2
for quadratic
probing. These increments are independent of the keys. Double hashing uses a secondary hash
function
h
double hashing
(
key
) on the keys to determine the increments to avoid the clustering problem. Spe-
cifically, double hashing looks at the cells at indices (
k
′
+
j* h
′
(
key
))
% N
, for
j
Ú
0, that is,
k % N
,(
k
(
key
))
% N
, and so on.
For example, let the primary hash function
h
and secondary hash function
h'
on a hash
table of size
11
be defined as follows:
h(key) = key %
11
;
h'(key) =
7
- key %
7
;
+
h
′
(
key
))
% N
, (
k
+
2
*h
′
(
key
))
% N
, (
k
+
3
*h
′
For a search key of
12
, we have
h(
12
) =
12
%
11
=
1
;
h'(
12
) =
7
-
12
%
7
=
2
;
Suppose the elements with the keys
45
,
58
,
4
,
28
, and
21
are already placed in the hash table.
We now insert the element with key
12
. The probe sequence for key
12
starts at index
1
. Since
the cell at index
1
is already occupied, search the next cell at index
3 (1 + 1 * 2)
. Since
the cell at index
3
is already occupied, search the next cell at index
5 (1 + 2 * 2)
. Since the
cell at index
5
is empty, the element for key
12
is now inserted at this cell. The search process
is illustrated in Figure 27.6.
The indices of the probe sequence are as follows: 1, 3, 5, 7, 9, 0, 2, 4, 6, 8, 10. This sequence
reaches the entire table. You should design your functions to produce a probe sequence that
Search WWH ::
Custom Search