Source of 22.18.java


  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