0

在以下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()or remove()？

4

1 回答 1

1

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

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

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

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

但是，当您已经删除了一些值时，循环 in可能会更快地remove()找到空位置（值），并在实际到达最初插入的位置之前终止。nullword

于 2021-02-18T07:34:19.373 回答