how to Compute the average probe length for success and failure - Linear probe (Hash Tables)

Posted by fang_dejavu on Stack Overflow See other posts from Stack Overflow or by fang_dejavu
Published on 2010-04-01T22:31:24Z Indexed on 2010/04/01 22:33 UTC
Read the original article Hit count: 294

Filed under:
|
|
|

hi everyone, I'm doing an assignment for my Data Structures class. we were asked to to study linear probing with load factors of .1, .2 , .3, ...., and .9. The formula for testing is: The average probe length using linear probing is roughly Success--> ( 1 + 1/(1-L)**2)/2 or Failure--> (1+1(1-L))/2. we are required to find the theoretical using the formula above which I did(just plug the load factor in the formula), then we have to calculate the empirical (which I not quite sure how to do). here is the rest of the requirements

**For each load factor, 10,000 randomly generated positive ints between 1 and 50000 (inclusive) will be inserted into a table of the "right" size, where "right" is strictly based upon the load factor you are testing. Repeats are allowed. Be sure that your formula for randomly generated ints is correct. There is a class called Random in java.util. USE it! After a table of the right (based upon L) size is loaded with 10,000 ints, do 100 searches of newly generated random ints from the range of 1 to 50000. Compute the average probe length for each of the two formulas and indicate the denominators used in each calculationSo, for example, each test for a .5 load would have a table of > > size approximately 20,000 (adjusted to be prime) and similarly each test for a .9 load would have a table of approximate size 10,000/.9 (again adjusted to be prime).

The program should run displaying the various load factors tested, the average probe for each search (the two denominators used to compute the averages will add to 100), and the theoretical answers using the formula above. .**

how do I calculate the empirical success?

© Stack Overflow or respective owner

Related posts about java

Related posts about hashtable