Class Notes (1,100,000)
CA (620,000)
Queen's (10,000)
CISC (500)
Lecture 13

CISC 235 Lecture Notes - Lecture 13: Quadratic Probing, Linear Probing, Hash Table


Department
Computing
Course Code
CISC 235
Professor
Robin W Dawes
Lecture
13

Page:
of 5
CISC 235 Lecture 13
Hashing Continued
Quadratic Probing
Quadratic probing is similar to linear probing except that instead of
f(i) = i, we use f(i) = c1*i + c2 * i^2 , where c1 and c2 are
constants
The algorithms we developed for linear probing (using "empty"
and "deleted" flag values) need only the new f(i) function to be
added.
Quadratic_Probing_Insert(k):
i = 0
v = h'(k)
a = v
while (i < m) and (T[a] not "empty") and (T[a]
not "deleted")
i += 1
a = (v + c1*i + c2*i^2) % m
if (T[a] is "empty") or (T[a] is "deleted")
T[a] = k
else
report "table full, insert failed"
Quadratic_Probing_Search(k):
i = 0
v = h'(k)
a = v
while (i < m) and (T[a] not "empty") and (T[a]
!= k)
i += 1
a = (v + c1*i + c2*i^2) % m
if T[a] == k
report "found it"
else
report "search failed
Quadratic_Probing_Delete(k):
i = 0
v = h'(k)
a = v
while (i < m) and (T[a] not "empty") and (T[a]
!= k)
i += 1
a = (v + c1*i + c2*i^2) % m
if T[a] == k
T[a] = "deleted"
else
report "search failed - could not
delete"
Quadratic probing greatly reduces the effect of primary
clustering. To illustrate this, consider a simple example: let c1 =
c2 = 1, and let m = 11. Let k1 and k2 be two keys. Suppose h'(k1)
= 0. Then k1's probe sequence is
i
h(k1,i)
0
0
1
2
2
6
3
1
4
9
...
...
Now suppose h'(k2) = 2. Then k2's probe sequence is
i
h(k2,i)
0
2
1
4
2
8
3
3
4
0
...
...
Even though the probe sequences both contain 2, they go off in
different directions after that. In general, two probe sequences
may hit the same address at any point, but then hit different
addresses after that.
Note that there is still a problem with what is called secondary
clustering: if h'(k1) == h'(k2), the probe sequences for k1 and k2
will be identical. Thus there are only m different probe sequences,
out of a possible m! sequences in which we could conceivably
search the table.
Quadratic probing has a potentially much bigger problem: unless
m, c1 and c2 are carefully chosen, a probe sequence may only
include a subset of the possible addresses. For example, let m =
16, c1 = 0 and c2 = 1. Suppose h'(k1) = 0. The probe sequence is
0, 1, 4, 9, 0, 9, 4, 1, 0, 1, 4, 9 etc. (taking 0, 1, 4, 9, 16, 25, 36, 49,
64, 81, 100, 121 etc all mod 16) ... we never examine any of the
other addresses.
Double Hashing
Double hashing attempts to combine the strong point of linear
probing (all addresses considered) with the strong point of
quadratic probing (reduced primary clustering). The technique is
simple: we include a second hash function h"(k), and define
h(k,i) = (h'(k) + i*h"(k)) mod m
Double hashing is effectively a generalization of linear probing,
except that instead of having a fixed "step size" that determines
how far we jump forward in the hash table on each iteration (in
linear probing, the step size is 1), we use the key itself to determine
the step size. Since the key is used to determine both the initial