remove() 无法正常运行

Question

在下面的 Main 方法中，为什么最后一个词 (clapping) 没有被删除？

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

输出为

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

clapping 未删除。为什么？

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

除了修饰符，代码还有什么问题吗？可能使用哈希函数或者 insert() 或 remove()?

Answer 1

问题很可能是 remove() 方法中循环的终止条件。

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

它在找到的第一个 null 值处终止。

插入时，如果位置已被占用，则更新hash1，因此单词的最终位置取决于现有插入的单词，即占用的位置。

然而，当您已经删除了一些值时，remove() 中的循环可能会更快地找到空位置（null 值），并在实际到达 word原来是插在.

remove() 无法正常运行

remove() not functioning correctly

java

arrays

hash

hashtable

double-hashing