1: // Precondition: checkInitialization has been called.
2: private int probe(int index, K key)
3: {
4: boolean found = false;
5: int removedStateIndex = -1; // Index of first location in removed state
6:
7: while ( !found && (hashTable[index] != null) )
8: {
9: if (hashTable[index].isIn())
10: {
11: if (key.equals(hashTable[index].getKey()))
12: found = true; // Key found
13: else // Follow probe sequence
14: index = (index + 1) % hashTable.length; // Linear probing
15: }
16: else // Skip entries that were removed
17: {
18: // Save index of first location in removed state
19: if (removedStateIndex == -1)
20: removedStateIndex = index;
21:
22: index = (index + 1) % hashTable.length; // Linear probing
23: } // end if
24: } // end while
25: // Assertion: Either key or null is found at hashTable[index]
26:
27: if (found || (removedStateIndex == -1) )
28: return index; // Index of either key or null
29: else
30: return removedStateIndex; // Index of an available location
31: } // end probe
32: // Version 4.0