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

In contrast, the field numberOfEntries counts the number of entries currently in the dictionary.
Thus, it is incremented when an entry is added to the dictionary but decremented when an
entry is removed.
Each constructor allocates an array for the hash table. The second constructor lets the client
specify a minimum size for the hash table. To ensure that the table's size is prime and at least as big
as the client wants, this constructor calls the private method getNextPrime to find the first prime
number that is greater than or equal to a given integer. The default constructor invokes the second
constructor, giving it a predetermined size.

Note: To implement getNextPrime(anInteger) , first see whether anInteger is even. If it
is, it cannot be prime, so add 1 to make it odd. Then use a private method isPrime to find the
first prime number among the parameter anInteger and subsequent odd integers.
To implement isPrime , note that 2 and 3 are prime but 1 and even integers are not. An odd
integer 5 or greater is prime if it is not divisible by every odd integer up to its square root.

The Methods getValue , remove , and add
We now consider next the major operations of the dictionary: getValue , remove , and add . The
note at the end of Segment 21.17 in the previous chapter summarized just what these operations
need to do.

22.11

The method getValue . We begin with an algorithm for the retrieval method getValue :
Algorithm getValue(key)
// Returns the value associated with the given search key, if it is in the dictionary.
// Otherwise, returns null .

index = getHashIndex(key)
Search the probe sequence that begins at hashTable[index] for key
if (key is found )
return value in found entry
else
return null

In addition to the private method getHashIndex , which you saw in Segment 21.11, this algo-
rithm suggests another private method that searches the probe sequence. We name this method
locate and specify it informally as follows:

locate(index, key)
Follows the probe sequence that begins at index ( key 's hash index) and returns either the index
of the entry containing key or - 1, if no such entry exists.

We'll implement locate in Segment 22.13.
The method getValue then has the following implementation:

public V getValue(K key)
{

V result = null ;
int index = getHashIndex(key);
index = locate(index, key);
if (index != -1)
result = hashTable[index].getValue(); // key found; get value