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

// else key not found; return null
return result;
} // end getValue

22.12

The method remove . Removing an entry from the hash table, like retrieving an entry, involves
locating the search key. If found, the entry is flagged as removed. The following pseudocode
describes the necessary steps for this operation:
Algorithm remove(key)
// Removes a specific entry from the dictionary, given its search key.
// Returns either the value that was associated with the search key or null if no such object
// exists.

index = getHashIndex(key)
Search the probe sequence that begins at hashTable[index] for key
if (key is found )
{

Flag entry as removed
numberOfEntries--
return value in removed entry

}
else
return null
As the following implementation shows, you call the private method locate to locate the
desired entry. If you find it, you change its state to removed and return its value. Otherwise, you
return null .
public V remove(K key)
{

V removedValue = null ;
int index = getHashIndex(key);
index = locate(index, key);
if (index != -1)
{ // key found; flag entry as removed and return its value
removedValue = hashTable[index].getValue();
hashTable[index].setToRemoved();
numberOfEntries--;
} // end if
// else key not found; return null
return removedValue;
} // end remove

22.13

The private method locate . Before we look at add , let's implement the method locate that both
getValue and remove invoke. The method looks for the given search key along the probe sequence
that begins at hashTable[index] , where index is the key's hash index. Recall that the search must
ignore entries that are in the removed state. The search continues until it locates either key or null .
To follow the probe sequence, locate must implement a particular open addressing scheme to
resolve collisions. For simplicity, we will implement linear probing. The following algorithm sum-
marizes our approach:
Algorithm locate(index, key)
// Returns either the index of the entry containing key or -1 if no such entry is found.

while (key is not found and hashTable[index] is not null)
{