Java Reference
In-Depth Information
HASH
TABLE
OVERFLOW
0
1000
1057
9530
1
2
9877
2007
3
3013
4
9879
Figure9.4
An illustration of bucket hashing for seven numbers stored in a five-
bucket hash table using the hash function h(K) = K mod 5. Each bucket con-
tains two slots. The numbers are inserted in the order 9877, 2007, 1000, 9530,
3013, 9879, and 1057. Two of the values hash to bucket 0, three values hash to
bucket 2, one value hashes to bucket 3, and one value hashes to bucket 4. Because
bucket 2 cannot hold three values, the third one ends up in the overflow bucket.
of M=B slots. The hash function assigns each record to the first slot within one
of the buckets. If this slot is already occupied, then the bucket slots are searched
sequentially until an open slot is found. If a bucket is entirely full, then the record
is stored in an overflow bucket of infinite capacity at the end of the table. All
buckets share the same overflow bucket. A good implementation will use a hash
function that distributes the records evenly among the buckets so that as few records
as possible go into the overflow bucket. Figure 9.4 illustrates bucket hashing.
When searching for a record, the first step is to hash the key to determine which
bucket should contain the record. The records in this bucket are then searched. If
the desired key value is not found and the bucket still has free slots, then the search
is complete. If the bucket is full, then it is possible that the desired record is stored
in the overflow bucket. In this case, the overflow bucket must be searched until the
record is found or all records in the overflow bucket have been checked. If many
records are in the overflow bucket, this will be an expensive process.
A simple variation on bucket hashing is to hash a key value to some slot in
the hash table as though bucketing were not being used. If the home position is
full, then the collision resolution process is to move down through the table toward
the end of the bucket while searching for a free slot in which to store the record.
If the bottom of the bucket is reached, then the collision resolution routine wraps
around to the top of the bucket to continue the search for an open slot. For example,
