javaarrayshashhashtabledouble-hashing

remove() not functioning correctly


In the following Main method why isn't the last word (clapping) removed?

public class Main {
    public static void main(String[] args) {
        HT ht = new HT();

        ht.insert("airplane");
        ht.insert("distilling");
        ht.insert("speaks");
        ht.insert("knit");
        ht.insert("digitize");
        ht.insert("Media");
        ht.insert("canonicalized");
        ht.insert("libraries");
        ht.insert("clapping");
        ht.insert("residues");
        ht.insert("spoilers");
        System.out.println(Arrays.toString(ht.set));

        ht.remove("distilling");
        ht.remove("knit");
        ht.remove("canonicalized");
        ht.remove("libraries");
        ht.remove("clapping");
        System.out.println(Arrays.toString(ht.set));
    }
}

The output is

[Media, digitize, airplane, canonicalized, spoilers, distilling, clapping, knit, libraries, speaks, residues]
[Media, digitize, airplane, null, spoilers, null, clapping, null, null, speaks, residues]

clapping is not removed. Why?

HT.java

public class HT {
    public String[] set;
    public int size;

    public HT() {
        this.set = new String[11];
        this.size = 0;
    }

    public void insert(String word) {
        int hash1 = giveHash1( word );
        int hash2 = giveHash2( word );
        while (set[hash1] != null) {
            hash1 += hash2;
            hash1 %= set.length;
        }
        set[hash1] = word;
        size++;
    }

    public void remove(String word) {
        int hash1 = giveHash1(word);
        int hash2 = giveHash2(word);
        while (set[hash1] != null && !set[hash1].equals(word)) {
            hash1 += hash2;
            hash1 %= set.length;
        }
        set[hash1] = null;
        size--;
    }

    public int giveHashCode(String s) {
        int hash = 0, x = 31;
        for(int i=0;i<s.length();i++) {
            hash = x * hash + s.charAt(i);
        }
        return hash;
    }
    private int giveHash1(String s) {
        return  (giveHashCode(s) % set.length < 0)
                ? (giveHashCode(s) % set.length) + set.length
                : giveHashCode(s) % set.length;
    }
    private int giveHash2(String s) {
        return  3 - (((giveHashCode(s) % set.length < 0)
                ? (giveHashCode(s) % set.length) + set.length
                : giveHashCode(s) % set.length) % 3);
    }
}

Apart from the modifiers, is there anything wrong with the code? Probably with the hash functions or maybe with insert() or remove()?


Solution

  • The problem is most likely the terminating condition for the loop in the remove() method.

    while (set[hash1] != null && !set[hash1].equals(word)) {
    

    which terminates at the first null value it finds.

    When inserting, you're updating hash1 if the position is already occupied, so the final position of a word depends on the existing inserted words i.e. the occupied positions.

    However when you've already removed a few of the values, the loop in remove() may find empty positions (null values) much sooner, and terminate before actually reaching the position the word was originally inserted in.