Analysing the average run-time complexity of double hashing

Discussion in 'Programming' started by SexyWoodenSpoon, Apr 18, 2008.

  1. #1
    Hey, can anybody help me with this?

    Analysing the average run-time complexity of double hashing

    Empirically test the formula for the average number of probes in the double
    hashing scheme: ‹pthe› = (ln q)/á, where á is the load factor and q = 1/(1-á). Use
    a table array with capacity m = 1009. Do the following for each n from 500 to
    1000:
    1. Form a data array of n random six-letter keys.
    2. Insert all n of these keys into the hash table.
    3. Select a random key from your data array and count the number of probes,
    pexp.
    4. Do step 3 1000 times and print the average count ‹pexp›.
    5. Plot the dependences ‹pexp› and ‹pthe› on n, and analyse the results.

    A java program that implements this (java not javascript) would be great too, pm me quick.
     
    SexyWoodenSpoon, Apr 18, 2008 IP
  2. starbugger

    starbugger Peon

    Messages:
    1
    Likes Received:
    0
    Best Answers:
    0
    Trophy Points:
    0
    As Seller:
    100% - 0
    As Buyer:
    100% - 0
    #2
    Don't cheat ya lazy so and so, its not that hard! :)

    J
     
    starbugger, Apr 20, 2008 IP