javahashtabledouble-hashing

Double hashed HashTable rehashing problem


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?


Solution

  • 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;
    }