Thread: hash table probes

working on hash table assignment. searching the table for 100 different keys. trying to keep track of total # of probes (linear) for all successful searches and same for failures. also tracking total # of successful searches. my table has variables numberProbesSuccess, numberProbesFail, and totalSuccess.

my method "find" is not incrementing these proper

   public void find(int key)    // find item with key
      {
		int numberProbes = 0;
      int hashVal = hashFunc(key);  // hash the key
 
      while(hashArray[hashVal] != null)  // until empty cell,
         {                               // found the key?
			numberProbes++;
         if(hashArray[hashVal].getKey() == key)
				{
				numberProbesSuccess += numberProbes;  // update # of probes for success
				totalSuccess++;
//				System.out.println("Number of probes: " + numberProbes);
            return;   // yes, return item
				}
			else
				{
         	hashVal++;                 // go to next cell
         	hashVal %= arraySize;      // wraparound if necessary
         	}
			} // end while
		numberProbes++;
//		System.out.println("Number of probes: " + numberProbes);
		numberProbesFail += numberProbes;           // update # of probes for failure
      return;                  // can't find item
      }

unsuccesful if while loop finds null. numberProbes can be used for successul searches (if the "if" finds == key) in which case the method returns OR for unsuccessful in case null is found, then numberProbes is assigned to numberProbesFail.

also, numberProbes resets with each of the 100 calls to find()

OK nevermind - I figured it out. This test is being run using different load factors .1, .2, ... , .9

All of the empirical data matches up with the theoretical (avg # probes for searches), EXCEPT for the .9 load factor. It blows up big time (way more than the theoretical).