为什么 hashTable 包含冗余键

Question

我的哈希表有问题；它包含冗余键。我已经重新定义了equal和hashcode，但是同样的问题。下面是我的问题的一个例子。我真的需要帮助。提前谢谢你。

public class Payoff {
    public ArrayList<Cluster> coalitions = new ArrayList<Cluster>();

    @Override
    public boolean equals(Object t) {
        // Vérification de la référence
        if (t==this)
            return true;
        //Vérification du type du paramètre puis de ses attributs.
        if (t instanceof Payoff) {
            Payoff tbis = (Payoff)t;
            return this.coalitions.equals(tbis.coalitions);
        } else
            return false;
    }

    @Override
    public int hashCode() {
        return this.coalitions.hashCode(); 
    }
}

public class Cluster implements Cloneable {
    public ArrayList<Integer> dataArray = new ArrayList<Integer>();
    public double[] ch;
    public double coalitionPayoff;

    public Cluster() {
    }

    public Cluster(Cluster obj) {
        this.ch = obj.ch;
        this.dataArray = (ArrayList<Integer>)obj.dataArray.clone();
        this.coalitionPayoff = obj.coalitionPayoff;
    }

    public boolean equals(Object T)
{   // Vérification de la référence
    if (T==this)
        return true;
    //Vérification du type du paramètre puis de ses attributs.
    if (T instanceof Cluster)
    {
        Cluster Tbis = (Cluster) T;
        return this.DataArray.equals(Tbis. DataArray) && Arrays.equals(this.Ch,Tbis.Ch)
                 && (this.CoalitionPayoff ==Tbis.CoalitionPayoff);

    } else
        return false;
}

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((dataArray == null) ? 0 : dataArray.hashCode());
        //result = prime * result + (int) (coalitionPayoff ^ (coalitionPayoff >>> 32));
        result = prime * result + ((ch == null) ? 0 : ch.hashCode());
        return result;
    }

    public Cluster clone() {
        return new Cluster ();
    }
}

public static void main(String[] args) throws Exception {
    Hashtable<Payoff,Double> HashTab = new Hashtable<Payoff,Double>();
    Payoff Pay1 = new Payoff();
    Cluster Cluster1 = new Cluster();
    Cluster1.DataArray.addAll(java.util.Arrays.asList(1,2,3));
    double[] ary = {1.5};
    Cluster1.Ch=  ary;
    Pay1.Coalitions.add(Cluster1);
    Cluster1 = new Cluster();
    Cluster1.DataArray.addAll(java.util.Arrays.asList(4,5));
    double[] ary2 = {4.5};
    Cluster1.Ch=  ary2;
    Pay1.Coalitions.add(Cluster1);
    HashTab.put(Pay1, 0.5);

    Payoff Pay2 = new Payoff();
    Cluster Cluster2 = new Cluster();
    Cluster2.DataArray.addAll(java.util.Arrays.asList(1,2,3));
    double[] ary3 = {1.5};      Cluster2.Ch=  ary3;
    Pay2.Coalitions.add(Cluster2);
    Cluster2 = new Cluster();
    Cluster2.DataArray.addAll(java.util.Arrays.asList(4,5));
    double[] ary4 = {4.5};
    Cluster2.Ch=  ary4;
    Pay2.Coalitions.add(Cluster2);
   if(!HashTab.containsKey(Pay2)){
      HashTab.put(Pay2, 0.5);
    }
    System.out.println(HashTab.size());
}

Answer 1

equals 方法 Cluster return 是错误的，因为 this.ch.equals(tbis.ch) return 是错误的。

array1.equals(array2)等于array1 == array2，所以如果内容相同但实际数组实例不同，则该方法会return false。要检查数组的内容而不是数组实例，请使用 Arrays.equals(array1,array2)（或者在您的情况下：Arrays.equals(this.ch,tbis.ch)）。

Answer 2

这一行是问题所在：

result = prime * result + ((ch == null) ? 0 : ch.hashCode()

这是数组的哈希码，而不是数组内容的哈希码，因此当你说：

double[] ary = {1.5};
double[] ary3 = {1.5};

除了里面有相同的数据外，它是不同的。确保使用内容而不是对象引用作为哈希码。

当然 Java 有一个解决方案：

result = prime * result + ((ch == null) ? 0 : Arrays.hashCode(ch)

更新

这是我用来解决问题的测试代码。 JUnit 规则！

public class TestHashTable
{
    @Test
    public void testEmpty()
    {
        final Cluster c1 = new Cluster();
        final Cluster c2 = new Cluster();
        Assert.assertEquals(c1, c2);
        Assert.assertEquals(c1.hashCode(), c2.hashCode());
    }

    @Test
    public void testSame()
    {
        final Payoff pay1 = new Payoff();
        final Cluster cluster1 = new Cluster();
        cluster1.dataArray.addAll(java.util.Arrays.asList(1,2,3));
        pay1.coalitions.add(cluster1);

        Assert.assertEquals(pay1, pay1);
        Assert.assertEquals(pay1.hashCode(), pay1.hashCode());
    }   

    @Test
    public void testEquals()
    {
        final Payoff pay1 = new Payoff();
        final Cluster cluster1 = new Cluster();
        cluster1.dataArray.addAll(java.util.Arrays.asList(1,2,3));
        pay1.coalitions.add(cluster1);

        final Payoff pay2 = new Payoff();
        final Cluster cluster2 = new Cluster();
        cluster2.dataArray.addAll(java.util.Arrays.asList(1,2,3));
        pay2.coalitions.add(cluster2);

        Assert.assertEquals(cluster1, cluster2);
        Assert.assertEquals(pay1, pay2);

        Assert.assertEquals(cluster1.hashCode(), cluster2.hashCode());
        Assert.assertEquals(pay1.hashCode(), pay1.hashCode());
    }

    @Test
    public void testUseInMap()
    {
        final Payoff pay1 = new Payoff();
        final Cluster cluster1 = new Cluster();
        cluster1.dataArray.addAll(java.util.Arrays.asList(1,2,3));
        final double[] a1 = {1.5};
        cluster1.ch = a1;
        pay1.coalitions.add(cluster1);

        final Payoff pay2 = new Payoff();
        final Cluster cluster2 = new Cluster();
        final double[] a2 = {1.5};
        cluster2.ch = a2;
        cluster2.dataArray.addAll(java.util.Arrays.asList(1,2,3));
        pay2.coalitions.add(cluster2);

        final Map<Payoff, Double> map = new HashMap<Payoff, Double>();
        map.put(pay1, 1.0);
        map.put(pay2, 2.0);

        Assert.assertEquals(1, map.size());
        Assert.assertTrue(2.0 == map.get(pay1));
    }
}

为什么 hashTable 包含冗余键

Why hashTable contains redundant Keys

java

hashtable

containskey

更新