Hashing: Quadratic Probing sequence

[zak100]

Homework Statement

Hi,
I want to generate probing sequence using quadratinc probing technique. If j =4 & table size = 19 & assuming h(K) = 9.

Homework 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.

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.

 

[zak100]

I am editing this part. I can't find the edit option

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 don't know how to get it.

Some body please guide me how to solve it.

Zulfi.[/QUOTE]

 

[Mark44]

I am editing this part. I can't find the edit option

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 don't know how to get it.

Some body please guide me how to solve it.

Zulfi.

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$.