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

entries with the number of table locations in either the occupied or available state. This change
increases so that rehashing occurs before the table loses its last null entry. Thus, the class begins

as shown in Listing 22-1.

λ

LISTING 22-1

An outline of the class HashedDictionary

import java.util.Iterator;
import java.util.NoSuchElementException;

/**

A class that implements a dictionary by using hashing.
@author Frank M. Carrano

*/
public class HashedDictionary<K, V>
implements DictionaryInterface<K, V>

{

private TableEntry<K, V>[] hashTable; // dictionary entries
private int numberOfEntries;
private int locationsUsed; // number of table locations not null
private static final int DEFAULT_SIZE = 101; // must be prime
private static final double MAX_LOAD_FACTOR = 0.5; // fraction of
// hash table that can be filled

public HashedDictionary()
{

this (DEFAULT_SIZE); // call next constructor
} // end default constructor

public HashedDictionary( int tableSize)
{

int primeSize = getNextPrime(tableSize);

hashTable = new TableEntry[primeSize];
numberOfEntries = 0;
locationsUsed = 0;
} // end constructor

< Implementations of methods in DictionaryInterface >
. . .

< Implementations of private methods >
. . .

private class TableEntry<S, T>
{

< See Segment 22.9 >
} // end TableEntry
} // end HashedDictionary

The field locationsUsed counts the number of locations in the hash table that are in either
the occupied or available state and is incremented each time an entry is added to the dictionary.