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