1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Hashing: Quadratic Probing sequence

  1. May 4, 2016 #1
    1. The problem statement, all variables and given/known data

    Hi,
    I want to generate probing sequence using quadratinc probing technique. If j =4 & table size = 19 & assuming h(K) = 9.
    2. Relevant equations
    h(K), h(K) + 1, h(k) -1, h(k) + 4, h(K) - 4, .... h(K) + (TSIZE -1)power 2 / 4, h(k) - (TSIZE -1) power 2 /4 all divided modulo TSize.

    3. The attempt at a solution
    The book shows following sequence:
    9, 10, 8, 13, 5, 18, 0, 6, 12, 15, 3, 7, 11, 1, 17, 16, 2, 14, 4

    I am able to find:
    h(k) = 9%19 = 9
    h(k) + 1 power 2 = 10 % 19 = 10
    h(k) - 1 power 2 = 8 % 19 = 8
    h(k) + 2 power 2 = 13 % 19 = 13
    h(k) - 2 power 2 = 5 % 19 = 5
    h(k) + 3 power 2 = 18 % 19 = 18
    h(k) - 3 power 2 = 0
    h(k) + 4 power 2 = 9 + 16 = 25 % 19 = 6
    h(k) - 4 power 2 = 9 -16 = -7 %19 = -7 9 which is wrong,

    Some body please guide me how to solve it.

    Zulfi.
     
  2. jcsd
  3. May 4, 2016 #2
    I am editing this part. I cant find the edit option

    3. The attempt at a solution
    The book shows following sequence:
    9, 10, 8, 13, 5, 18, 0, 6, 12, 15, 3, 7, 11, 1, 17, 16, 2, 14, 4

    I am able to find:
    h(k) = 9%19 = 9
    h(k) + 1 power 2 = 10 % 19 = 10
    h(k) - 1 power 2 = 8 % 19 = 8
    h(k) + 2 power 2 = 13 % 19 = 13
    h(k) - 2 power 2 = 5 % 19 = 5
    h(k) + 3 power 2 = 18 % 19 = 18
    h(k) - 3 power 2 = 0
    h(k) + 4 power 2 = 9 + 16 = 25 % 19 = 6
    h(k) - 4 power 2 = 9 -16 = -7 %19 = -7 which is wrong, it should be 12. I know 19 -7 = 12. But i dont know how to get it.

    Some body please guide me how to solve it.

    Zulfi.[/QUOTE]
     
  4. May 5, 2016 #3

    Mark44

    Staff: Mentor

    Have you seen this wikipedia article? https://en.wikipedia.org/wiki/Quadratic_probing
    What is the complete problem statement? Are the numbers in your list the values in the hash table, or are they the things for which hash values need to be found?

    Also, instead of writing "h(k) + 2 power 2" and so on, at the very least write this as h(k) + 2^2.

    Even better, use LaTeX to write ##h(k) + 2^2##. My script for this is ##h(k) + 2^2##.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Hashing: Quadratic Probing sequence
  1. Energy sequence (Replies: 0)

  2. Set theory hash-tables (Replies: 0)

Loading...