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

This algorithm suggests that you write several more private methods. We specify them infor-
mally as follows:

isHashTableTooFull()
Returns true if the hash table's load factor is greater than or equal to MAX_LOAD_FACTOR . Here we define
the load factor as the ratio of locationsUsed to hashTable.length .

rehash()
Expands the hash table to a size that is both prime and at least double its current size, and then adds
the current entries in the dictionary to the new hash table.

probe(index, key)
Detects whether key collides with hashTable[index] and resolves it by following a probe
sequence. Returns the index of either an available location along the probe sequence or the entry
containing key . This index is always legal, since the probe sequence stays within the hash table.

Using these private methods, we implement the method add as follows:
public V add(K key, V value)
{

V oldValue; // value to return
if (isHashTableTooFull())
rehash();
int index = getHashIndex(key);
index = probe(index, key); // check for and resolve collision
// Assertion: index is within legal range for hashTable
assert (index >= 0) && (index < hashTable.length);
if ( (hashTable[index] == null ) || hashTable[index].isRemoved())
{ // key not found, so insert new entry
hashTable[index] = new TableEntry<K,V>(key, value);
numberOfEntries++;
locationsUsed++;
oldValue = null ;

}
else
{ // key found; get old value for return and then replace it
oldValue = hashTable[index].getValue();
hashTable[index].setValue(value);
} // end if
return oldValue;
} // end add

22.15

The private method probe . The method probe(key, index) is similar to the method locate in
that it looks for key along the probe sequence that begins at hashTable[index] . The search ignores
entries that are in the removed state and continues until it locates either key or null . During this
search, the method records the index of the first location, if any, that references an entry that has
been removed from the table. This additional task is what distinguishes probe from locate . Thus,
probe returns the index of a table location that either references an entry containing key or is
available for an addition to the table.
Notice that probe returns the index of the removed entry that it first encounters along the probe
sequence. Since add will insert a new entry into this location, a subsequent search for this entry will
encounter it sooner than if add had inserted it in a location further along the probe sequence.