Source of 22.15.java


  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