Hashing as a Dictionary Implementation - Data Structures and Abstractions with Java - page 558

The methods probe and locate are so similar that you can omit locate and use probe instead.
To do so, you must change the implementations of remove and getValue slightly. The following
question asks you to make this change.

Question 4 What changes to the methods remove and getValue are necessary so they can
call probe instead of locate ?

22.16

The private method rehash . Recall that the method rehash expands the hash table to a size that is
both prime and at least double its current size. Since the hash function depends on the size of the
table, you cannot copy entries from the old array and put them into the same positions in the new
array. You need to apply the revised hash function to each entry to determine its proper position in
the new table. But doing so can lead to collisions that need to be resolved. Thus, you should use the
method add to add the existing entries to the new and larger hash table. Since add increments the
data field numberOfEntries , you must remember to set this field to zero before adding the entries.
The method has the following implementation:

private void rehash()
{

TableEntry<K, V>[] oldTable = hashTable;
int oldSize = hashTable.length;
int newSize = getNextPrime(oldSize + oldSize);
hashTable = new TableEntry[newSize]; // increase size of array
numberOfEntries = 0; // reset number of dictionary entries, since
// it will be incremented by add during rehash

locationsUsed = 0;
// rehash dictionary entries from old array to the new and bigger
// array; skip both null locations and removed entries
for ( int index = 0; index < oldSize; index++)
{

if ( (oldTable[index] != null ) && oldTable[index].isIn() )
add(oldTable[index].getKey(), oldTable[index].getValue());
} // end for
} // end rehash

As we traverse the old hash table, notice that we skip both the null locations and the entries that
have been removed from the dictionary but are still in the hash table.
This method does not retain the instances of TableEntry that were in the old hash table.
Instead, it uses an entry's key and value to create a new entry. You can avoid this reallocation of
entries; Exercise 4 at the end of this chapter asks you to investigate this possibility.

Question 5 When the method add calls rehash , rehash calls add . But when rehash calls
add , does add call rehash ? Explain.

Iterators

22.17

Finally, we provide iterators for the dictionary, much as we did in Chapter 20. For example, we can
implement an internal class KeyIterator to define an iteration of the search keys. The iteration
must traverse the hash table, ignoring cells that either contain null or reference removed entries.
Figure 22-6 shows a sample hash table. Cells in blue reference the dictionary entries, light gray
cells reference removed entries, and dark gray cells contain null . As we traverse this table, we skip