1,105,406 Community Members

Quadratic Probing

Member Avatar
FUTURECompEng
Junior Poster in Training
50 posts since Feb 2011
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Review for a final and I had a question...

You are give a hash function h(x) = x%11 and the size of the hash table is 11. The inputs are 4371,1323,6173,4199,4344,9679,1989. What would the resulting hash table be using quadratic probing.

Would I start with 4371 and then do the following

(h(x)+i^2)%size = location ?

h(x) = 4371mod11 = 4
size = 11
i = ???

Not sure thanks for any help (the book is confusing me even more ).

Member Avatar
Taywin
Posting Maven
2,632 posts since Apr 2010
Reputation Points: 134 [?]
Q&As Helped to Solve: 378 [?]
Skill Endorsements: 17 [?]
 
0
 

Think about it as an array index (with 0-index).

/*
There are 11 indices in your hash locations. Each index is determined by the result after mod.
Hashing 4371
i = 4371 % 11 = 4
    +---+
    | 0 |
    +---+
    | 1 |
    +---+
    | 2 |
    +---+
    | 3 |
    +---+
    | 4 |  => 4371
    +---+
    | 5 |
    +---+
    | 6 |
    +---+
    | 7 |
    +---+
    | 8 |
    +---+
    | 9 |
    +---+
    | 10|
    +---+

Hashing 1323
i = 1323 % 11 = 3
    +---+
    | 0 |
    +---+
    | 1 |
    +---+
    | 2 |
    +---+
    | 3 |  => 1323
    +---+
    | 4 |  => 4371
    +---+
    | 5 |
    +---+
    | 6 |
    +---+
    | 7 |
    +---+
    | 8 |
    +---+
    | 9 |
    +---+
    | 10|
    +---+

 and so on...
*/

PS: You will have to deal with collision as well (when the hash location value is the same for 2 or more numbers). There are rules for collision.

Member Avatar
JamesCherrill
... trying to help
10,388 posts since Apr 2008
Reputation Points: 2,081 [?]
Q&As Helped to Solve: 1,752 [?]
Skill Endorsements: 47 [?]
Moderator
Featured
 
0
 

The wikipedia article on quadratic probing starts with a really clear and simple explanation...

Member Avatar
FUTURECompEng
Junior Poster in Training
50 posts since Feb 2011
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Thanks!

Question Answered as of 1 Year Ago by JamesCherrill and Taywin
You
This question has already been solved: Start a new discussion instead
Post:
Start New Discussion
View similar articles that have also been tagged: