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