Java Reference
In-Depth Information
we add another data field to the class of entry objects. This field is a boolean flag; it is true if the
entry is in the dictionary or false if it has been removed. Figure 22-5 illustrates the hash table and
one dictionary entry.
FIGURE 22-5
A hash table and one of its entry objects
Hash table
Flag
Instance of
TableEntry
Search key
Value
Thus, we create the private class
TableEntry
and make it internal to the dictionary class.
TableEntry
begins as follows:
private class
TableEntry<S, T>
{
private
S key;
private
T value;
private
boolean
inTable;
// true if entry is in hash table
private
TableEntry(S searchKey, T dataValue)
{
key = searchKey;
value = dataValue;
inTable =
true
;
}
// end constructor
. . .
In addition to the methods
getKey
,
getValue
, and
setValue
, this class has the methods
isIn
,
isRemoved
,
setToIn
, and
setToRemoved
to either interrogate or set the value of the boolean
flag
inTable
.
Note:
A location in the hash table in the available state contains an entry in the removed state.
If you do not use a perfect hash function, you must expect collisions. All open addressing methods
for resolving collisions become less efficient as the hash table fills, so you need to increase the size
of the table. As Segment 21.22 mentioned, increasing the size of the table can also ensure that it
will contain a
null
entry—a necessity for ending the search of a probe sequence. Since our hash
table is an array, we expand it and rehash the dictionary entries, as described in Segment 22.7.
However, we modify the definition of the load factor
λ
by replacing the number of dictionary
