1: // @author Frank M. Carrano, Timothy M. Henry
2: // @version 5.0
3: // Precondition: checkIntegrity has been called.
4: private int linearProbe(int index, K key)
5: {
6: boolean found = false;
7: int availableStateIndex = −1; // Index of first element in available state
8: while ( !found && (hashTable[index] != null) )
9: {
10: if (hashTable[index] != AVAILABLE)
11: {
12: if (key.equals(hashTable[index].getKey()))
13: found = true; // Key found
14: else // Follow probe sequence
15: index = (index + 1) % hashTable.length; // Linear probing
16: }
17: else // Element in available state; skip it, but mark the first one encountered
18: {
19: // Save index of first element in available state
20: if (availableStateIndex == −1)
21: availableStateIndex = index;
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]
27: if (found || (availableStateIndex == −1) )
28: return index; // Index of either key or null
29: else
30: return availableStateIndex; // Index of an available element
31: } // end linearProbe