Hey all,
I have an assignment over thanksgiving break to implement quadratic probing on a given hash table.
From my notes, the way this thing works is that to search for the next item, I do:
key % table size
And if that position is taken, try
(key % table size) + 1^2
(key % table size) - 1^2
(key % table size) + 2^2
(key % table size) - 2^2 ///... and so forth
The issue I have is with wrapping around the table. If I'm doing key% table size + n^2 and this exceeds the length of the table, I can just use the modulus operator again and wrap around.
However, what do I do when I'm subtracting? E.g. (key%table size) - n^2 is a negative number? How do I go up and around the table?
The solution I tried implementing was:
table size - (negative_key + (key%table_size))
Essentially, from the top of the table I subtract the sum of the new negative key + (key%table size) the old original key....
This does not seem to work.
any ideas?
Edited by: Kal-ElofKrypton on Nov 22, 2009 10:30 AM