Java Reference
In-Depth Information
HASH
TABLE
OVERFLOW
0
1000
1057
1
9530
2
3013
3
4
5
6
2007
9877
7
8
9879
9
Figure9.5
An variant of bucket hashing for seven numbers stored in a 10-slot
hash table using the hash function h(K) = K mod 10. Each bucket contains two
slots. The numbers are inserted in the order 9877, 2007, 1000, 9530, 3013, 9879,
and 1057. Value 9877 first hashes to slot 7, so when value 2007 attempts to do
likewise, it is placed in the other slot associated with that bucket which is slot 6.
When value 1057 is inserted, there is no longer room in the bucket and it is placed
into overflow. The other collision occurs after value 1000 is inserted to slot 0,
causing 9530 to be moved to slot 1.
assume that buckets contain eight records, with the first bucket consisting of slots 0
through 7. If a record is hashed to slot 5, the collision resolution process will
attempt to insert the record into the table in the order 5, 6, 7, 0, 1, 2, 3, and finally 4.
If all slots in this bucket are full, then the record is assigned to the overflow bucket.
The advantage of this approach is that initial collisions are reduced, Because any
slot can be a home position rather than just the first slot in the bucket. Figure 9.5
shows another example for this form of bucket hashing.
Bucket methods are good for implementing hash tables stored on disk, because
the bucket size can be set to the size of a disk block. Whenever search or insertion
occurs, the entire bucket is read into memory. Because the entire bucket is then
in memory, processing an insert or search operation requires only one disk access,
unless the bucket is full. If the bucket is full, then the overflow bucket must be
retrieved from disk as well. Naturally, overflow should be kept small to minimize
unnecessary disk accesses.
