Linear Probing in Hash Tables
I'm building a hash table for a project and I'm trying to get a probe length for the 10,001st random integer that is inserted into my table for each load factor .1-.9. Each load factor will have multiple tables built and ran on it according to the number specified in the command line so that an average probe length can be obtained for that last integer. . . the examples given to me were 10, 100, and 1000 times for each load factor. I'm having a problem though for two apparent reasons. One, the probe length for that last insertion really seems to vary alot according to the range of my random integers. Secondly, the probe length varies alot from run to run. . . the problem is that in the specs, the average probe length should be very close to the theoretical length which is (1 - 1 / (1 - L) ^ 2 ) / 2 where L is the load factor. So, I'm thinking that since my range of random numbers really isn't supposed to matter, then maybe I'm calculating that probe length incorrectly. In my hash table I have the following code for insertion:
public boolean insert(int data)
{
probeCount = 0;
boolean success = true;
int hVal = hashValue(data);
if (table[hVal] == -1)
table[hVal] = data;
else if(table[hVal] != -1)
{
while(table[hVal] != -1)
{
hVal = (hVal + 1) % wholeSize;
++probeCount;
}
table[hVal] = data;
}
else
success = false;
return success;
}
I'm assuming that what this will do is count how many times it collides with each index of the array until it finds an open index and then inserts. This should also be my probe length, correct? If so, then why when I have a range of 0-499 for integers, hash them, and insert 10,001 of them into the table is my last probe length 9,944? That's nowhere near the theoretical probe length with a load factor of .1. I'm really confused about how this is supposed to work and I'm hoping that someone knows more about these things than I do. Any help anyone can give me will be greatly appreciated!! Thanks!!
