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

cells that are gray. The only real concern in this implementation is detecting when the iteration
ends—that is, when the method hasNext should return false. The occurrence of a gray cell and the
size of the hash table are not the proper criteria for this determination. Instead, you simply count
backward from currentSize each time the method next returns the next search key.

FIGURE 22-6

A hash table containing dictionary entries, removed entries, and
null values

Blue current entry
Light gray removed entry

Dark gray null

The implementation of KeyIterator follows. A class that defines an iteration of values would
have a similar implementation.

private class KeyIterator implements Iterator<K>
{

private int currentIndex; // current position in hash table
private int numberLeft; // number of entries left in iteration

private KeyIterator()
{

currentIndex = 0;
numberLeft = numberOfEntries;
} // end default constructor
public boolean hasNext()
{

return numberLeft > 0;
} // end hasNext
public K next()
{

K result = null ;
if (hasNext())
{

// find index of next entry
while ( (hashTable[currentIndex] == null ) ||
hashTable[currentIndex].isRemoved() )

{

currentIndex++;
} // end while
result = hashTable[currentIndex].getKey();
numberLeft--;
currentIndex++;

}
else
throw new NoSuchElementException();
return result;
} // end next