Quadratic Probing

[FUTURECompEng]

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

[Taywin]

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.

[JamesCherrill]

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

[FUTURECompEng]

Thanks!