Doubling hashing, infinite loop?
I am trying to implement a hash table, using the methods of double hashing. It seems that I am running an infinite loop. Any suggestions on how I can fix this? Thanks.
private int find(Object key)
// Calculate the starting index.
int index = key.hashCode() % table.length;
if (index < 0)
index += table.length; // Make it positive.
// Increment index until an empty slot is reached
// or the key is found.
while ( (table[index] != null)&& (!key.equals(table[index].key)))
index= 1 + (Math.abs(key.hashCode())%(table.length-2));
// Check for wraparound.
if (index >= table.length)
index = (index+1)%table.length; // Wrap around.
Re: Doubling hashing, infinite loop?
The problem with Double Hashing is that you can get a zero increment. You can read Wikipedia's description of Double Hashing for a way to try and solve this issue. You may also want to check to see if the item is not in the hash table. The last issue you can encounter with hashing is that you'll end up with "skipped" spots.
Say you had a hash table of size 10, and the double hashing happens to have an increment of 2. Then, all of the odd values would never get checked.
The solution to the last problem is to only have hash tables of sizes which are prime numbers.