Java Reference
In-Depth Information
The method used to convert a key to a table location is called the
hash function
(
H
, say). Any calculation that
produces a valid table location (array subscript) can be used, but, as we shall see, some functions give better results
than others.
For example, we could use
H1(key) = key % 10 + 1
. In other words, we add 1 to the last digit of the key. Thus,
52
would hash to
3
. Note that
H1
produces locations between 1 and 10 only. If the table had 100 locations, say, the
function would be valid, but it may not be a good function to use.
Note also that
H(key) = key % 10
would not be a proper hash function here since, for instance,
50
would hash
to
0
and there is no table location
0
. Of course, if locations started from subscript
0
, then
key % 10
would be valid,
provided there were at least ten locations.
Another function is
H2(key) = key % 12 + 1
. The expression
key % 12
produces a value between
0
and
11
;
adding
1
gives values between
1
and
12
. In general,
key % n + 1
produces values between
1
and
n
, inclusive. We will
use this function in our example.
H2(52)
=
52 % 12 + 1
=
5
. We say, “
52
hashes to location
5
.” Since
num[5]
is empty, we place
52
in
num[5]
.
Suppose, later, we are searching for
52
. We first apply the hash function, and we get
5
. We compare
num[5]
with
52
; they match, so we find
52
with just one comparison.
Now suppose the following keys come in the order given:
52 33 84 43 16 59 31 23 61
•
52
is placed in num[5].
•
33
hashes to
10
;
num[10]
is empty, so
33
is placed in
num[10]
.
•
84
hashes to
1
;
num[1]
is empty, so
84
is placed in
num[1]
.
43
hashes to
8
;
num[8]
is empty, so
43
is placed in
num[8]
.
At this stage,
num
can be pictured like this:
•
num
84
52
43
33
1
2
3
4
5
6
7
8
9
10
11
12
•
16
hashes to
5
;
num[5]
is occupied and not by
16
—we have a collision. To resolve the collision,
we must find another location in which to put
16
. One obvious choice is to try the very next
location,
6
;
num[6]
is empty, so
16
is placed in
num[6]
.
•
59
hashes to
12
;
num[12]
is empty, so
59
is placed in
num[12]
.
31
hashes to
8
;
num[8]
is occupied and not by
31
—we have a collision. We try the next location,
9
;
num[9]
is empty, so
31
is placed in
num[9]
.
At this stage,
num
looks like this:
•
num
84
52
16
43
31
33
59
1
2
3
4
5
6
7
8
9
10
11
12
23
hashes to
12
;
num[12]
is occupied and not by
23
—we have a collision. We must try the next
location, but what is the next location here? We pretend that the table is “circular” so that
location
1
follows location
12
. However,
num[1]
is occupied and not by
23
. So, we try
num[2]
;
num[2]
is empty, so
23
is placed in
num[2]
.
•
61
hashes to
2
;
num[2]
is occupied and not by
61
—we have a collision. We try the next
location,
3
;
num[3]
is empty, so
61
is placed in
num[3]
.
•
Finally,
Search WWH ::
Custom Search