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.

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

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 …``````

## All 3 Replies

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.

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

Thanks!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.