Hashing: Quadratic Probing sequence

That is not as good as using LaTeX, but it is better than writing h(k) + 2 power 2.In summary, the conversation was about generating a probing sequence using the quadratic probing technique. The problem statement involved finding hash values for a given table size and a specific hashing function. The conversation also included a discussion on how to find the correct value for h(k) - 4 power 2, which should be 12 instead of -7. The suggestion was made to refer to a Wikipedia article for more information and to use LaTeX to write mathematical expressions.
  • #1
462
11

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.
 
Physics news on Phys.org
  • #2
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]
 
  • #3
zak100 said:
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##.
 

1. What is the purpose of Quadratic Probing sequence in hashing?

The purpose of Quadratic Probing sequence is to resolve hash collisions in a hashtable. It is an open addressing collision resolution technique in which the position of the next available slot is determined using a quadratic function.

2. How does Quadratic Probing sequence work?

Quadratic Probing sequence works by using a hash function to determine the initial position of the key in the hashtable. If a collision occurs, the next position is calculated using a quadratic function. If that position is also occupied, the process is repeated until an empty slot is found.

3. What are the advantages of using Quadratic Probing sequence?

One advantage of using Quadratic Probing sequence is that it is relatively easy to implement. It also has a lower clustering effect compared to other open addressing techniques, which can improve the efficiency of the hashtable.

4. What are the limitations of Quadratic Probing sequence?

One of the limitations of Quadratic Probing sequence is that it can lead to primary clustering, where keys that are mapped to nearby positions in the hashtable tend to collide repeatedly. This can cause a decrease in performance and efficiency. It also requires a larger hashtable size compared to other collision resolution techniques.

5. When is Quadratic Probing sequence a good choice for collision resolution?

Quadratic Probing sequence is a good choice for collision resolution when the hashtable is not expected to be filled to capacity. It is also a good choice for hash functions that are not well-distributed, as it can help reduce the effects of clustering. Additionally, it is useful for smaller datasets where the number of collisions is expected to be low.

Suggested for: Hashing: Quadratic Probing sequence

Back
Top