This question has already been solved: Start a new discussion instead

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

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.

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

Question Answered as of 1 Year Ago by
JamesCherrill
and Taywin

You