Java Reference
In-Depth Information
bucket, much as we did with open addressing. To find a value, you hash the search key, locate the
bucket, and look through the key-value pairs in it. In all likelihood, the bucket contains few values,
so this mini-search will be fast. When you remove an entry, you find it in its bucket and delete it.
Thus, the entry no longer exists in the hash table.
What can you use to represent a bucket? A list, a sorted list, a chain of linked nodes, an
array, or a vector are some possibilities with which you are familiar. Anything that involves an
array or vector will cause a substantial memory overhead, since each location in the hash table
will have a fixed amount of memory allocated to it. Much of this memory will be unused. Either
a linked implementation of a list or a chain of linked nodes is a reasonable choice for a bucket,
since memory is allocated to the bucket only as needed. Figure 21-9 illustrates a hash table with
linked chains as buckets. In this arrangement, each location in the hash table is a head reference
to a chain of linked nodes that make up the bucket. Each node contains references to a search
key, to the key's associated value, and to the next node in the chain. Notice that a node must ref-
erence the search key so that you can locate it later when you search the chain. Resolving colli-
sions by using buckets that are linked chains is called separate chaining .
FIGURE 21-9
A hash table for use with separate chaining; each bucket is a
chain of linked nodes
Node
Key
Value
Hash table
21.24
If your dictionary allows duplicate search keys, adding a new entry to the beginning of the appro-
priate chain is fastest, as Figure 21-10a indicates. However, if you want distinct search keys, adding
a new entry requires you to search a chain for the search key. If you do not find it, you will be at the
end of the chain, where you can add the new entry. Figure 21-10b illustrates this case. But since
you have to search the chain anyway, you could maintain the chain in sorted order by search key, as
Figure 21-10c shows. Subsequent searches would then be a little faster. As you will see, however,
typical chains are short, so this refinement might not be worth the effort.
Question 7 Consider search keys that are distinct integers. If the hash function is
h ( key ) = key modulo 5
and separate chaining resolves collisions, where in the hash table do the following search keys
appear after being added? 4, 6, 20, 14, 31, 29
 
Search WWH ::




Custom Search