I need to implement a hash table with open addressing and double hashing for school project. I can add up to 56 entries, but when it tries to add 57th and rehashes it, it says that the word exist (from addWord() method) while it shouldn't.
for (int k = 0; k < 57; ++k) {
word = "s" + k;
h.addWord(word);
System.out.println("Word = " + word + " KEY = " + h.hash(word));
}
output:
Word = s0 KEY = 0
...
Rehashing the table!
Word = s4 KEY = 11
...
Rehashing the table!
Word = s7 KEY = 14
...
...
...
Word = s55 KEY = 45
Rehashing the table!
F28DA_CW1.WException: Word exist!
at F28DA_CW1.HTableWords.addWord(HTableWords.java:124)
at F28DA_CW1.HTableWords.rehash(HTableWords.java:178)
at F28DA_CW1.HTableWords.addWord(HTableWords.java:96)
at F28DA_CW1.test.main(test.java:17)
Here is my code:
import java.util.Arrays;
public class test {
main method class(everything was breaking since main method wanted every function static)
public class test {
public static void main(String[] args) {
test t = new test((float) 0.5);
String word = "";
for (int k = 0; k < 2000; ++k) {
word = "s" + k;
try {
t.addWord(word);
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
}
The error seems to be in tempTable[j] = hTable[i]; line (166). I cannot figure it out what is wrong with it. Any help would be greatly appreciated. I have been stuck with it for 2 days.
Edit: So the problem is now at doubleHash() method which is giving me a negative number -27 after 100 entries. Can someone please verify if the formula is right?
Now all you need to do is replace the % operations with a custom mod that will avoid the negative results. When I do that, I no longer see anything suspicious in the output.
public static int mod2(int p, int q) {
int m = p%q;
if (m<0) return m+q;
return m;
}