• Support PF! Buy your school textbooks, materials and every day products Here!

Hashing: Quadratic Probing sequence

  • Thread starter zak100
  • Start date
  • #1
zak100
Gold Member
433
10

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.
 

Answers and Replies

  • #2
zak100
Gold Member
433
10
I am editing this part. I cant 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 dont know how to get it.

Some body please guide me how to solve it.

Zulfi.[/QUOTE]
 
  • #3
33,270
4,975
I am editing this part. I cant 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 dont 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##.
 

Related Threads on Hashing: Quadratic Probing sequence

Replies
6
Views
3K
  • Last Post
Replies
3
Views
578
Replies
6
Views
2K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
0
Views
1K
Replies
6
Views
4K
  • Last Post
Replies
17
Views
984
  • Last Post
Replies
6
Views
2K
Top