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

if (hashTable[index] references an entry that is in the dictionary and contains key)
Exit loop
else
index = next probe index

}

if (key is found )
return index
else
return -1
The implementation of locate now follows from this pseudocode:
private int locate( int index, K key)
{

boolean found = false ;
while ( !found && (hashTable[index] != null ) )
{

if ( hashTable[index].isIn() &&
key.equals(hashTable[index].getKey()) )
found = true ; // key found
else // follow probe sequence
index = (index + 1) % hashTable.length; // linear probing
} // end while
// Assertion: either key or null is found at hashTable[index]
int result = -1;
if (found)
result = index;
return result;
} // end locate
You can change from linear probing to another open addressing scheme for collision resolution
by replacing the highlighted assignment statement in the previous method.

22.14

The method add . We begin with the algorithm for adding a new entry:
Algorithm add(key, value)
// Adds a new key-value entry to the dictionary. If key is already in the dictionary,
// returns its corresponding value and replaces it in the dictionary with value .

if ( hash table is too full )
rehash()

index = getHashIndex(key)
Check for collision and resolve it (this step can alter index )
if (key is not found )
{ // add entry to hash table
hashTable[index] = new TableEntry(key, value)
numberOfEntries++
locationsUsed++
return null

}
else // search key is in table; return and replace entry's value
{

oldValue = hashTable[index].getValue()
hashTable[index].setValue(value)
return oldValue

}