Java Reference
In-Depth Information
0
1000
9530
1
2
3
3013
4
5
6
9877
2007
1057
7
8
9
9879
Figure9.3
An illustration of open hashing for seven numbers stored in a ten-slot
hash table using the hash function h(K) = K mod 10. The numbers are inserted
in the order 9877, 2007, 1000, 9530, 3013, 9879, and 1057. Two of the values
hash to slot 0, one value hashes to slot 2, three of the values hash to slot 7, and
one value hashes to slot 9.
the sum for the integer quantities will typically cause a 32-bit integer to
overflow (thus losing some of the high-order bits) because the resulting
values are so large. But this causes no problems when the goal is to compute
a hash function.
9.4.2
Open Hashing
While the goal of a hash function is to minimize collisions, some collisions are
unavoidable in practice. Thus, hashing implementations must include some form of
collision resolution policy. Collision resolution techniques can be broken into two
classes: open hashing (also called separate chaining) and closed hashing (also
called open addressing).
3
The difference between the two has to do with whether
collisions are stored outside the table (open hashing), or whether collisions result
in storing one of the records at another slot in the table (closed hashing).
Open
hashing is treated in this section, and closed hashing in Section 9.4.3.
The simplest form of open hashing defines each slot in the hash table to be
the head of a linked list. All records that hash to a particular slot are placed on
that slot's linked list. Figure 9.3 illustrates a hash table where each slot stores one
record and a link pointer to the rest of the list.
3
Yes, it is confusing when “open hashing” means the opposite of “open addressing,” but unfortu-
nately, that is the way it is.
