如果哈希码不同,为什么HashSet允许相等的项？

Question

该HashSet的类有一个附加(对象o)方法,这是不从另一个类继承的.该方法的Javadoc说明如下:

如果指定的元素尚不存在,则将其添加到此集合中.更正式地,将指定的元素e这套如果此集合不包含任何元素e2,使得(e==null ? e2==null : e.equals(e2)).如果此set已包含该元素,则调用将保持set不变并返回false.

换句话说,如果两个对象相等,则不会添加第二个对象,并且HashSet将保持不变.然而,我发现,这是不正确的,如果对象e和e2,有不同的哈希码尽管e.equals(e2).这是一个简单的例子:

import java.util.HashSet;
import java.util.Iterator;
import java.util.Random;

public class BadHashCodeClass {

    /**
     * A hashcode that will randomly return an integer, so it is unlikely to be the same
     */
    @Override
    public int hashCode(){
        return new Random().nextInt();
    }

    /**
     * An equal method that will always return true
     */
    @Override
    public boolean equals(Object o){
        return true;
    }

    public static void main(String... args){
        HashSet<BadHashCodeClass> hashSet = new HashSet<>();
        BadHashCodeClass instance = new BadHashCodeClass();
        System.out.println("Instance was added: " + hashSet.add(instance));
        System.out.println("Instance was added: " + hashSet.add(instance));
        System.out.println("Elements in hashSet: " + hashSet.size());

        Iterator<BadHashCodeClass> iterator = hashSet.iterator();
        BadHashCodeClass e = iterator.next();
        BadHashCodeClass e2 = iterator.next();
        System.out.println("Element contains e and e2 such that (e==null ? e2==null : e.equals(e2)): " + (e==null ? e2==null : e.equals(e2)));
    }

主要方法的结果是:

Instance was added: true
Instance was added: true
Elements in hashSet: 2
Element contains e and e2 such that (e==null ? e2==null : e.equals(e2)): true

如上面的例子清楚地显示,HashSet能够在其中添加两个元素e.equals(e2).

我将假设这不是 Java中的错误,实际上有一些完全合理的解释为什么会这样.但我无法弄清楚到底是什么.我错过了什么？

Answer 1

我想你真正要问的是:

"为什么HashSet添加具有不等哈希码的对象,即使它们声称是相等的？"

我的问题和你发布的问题之间的区别在于你假设这种行为是一个错误,因此你从这个角度来看它会让你感到悲伤.我认为其他海报已经完全解释了为什么这不是一个错误,但是他们没有解决潜在的问题.

我会在这里尝试这样做; 我建议改写你的问题,以消除Java中糟糕的文档/错误的指控,这样你就可以更直接地探究为什么你遇到了你所看到的行为.

该equals()单证状态(强调):

请注意,通常需要在重写此hashCode方法时覆盖该方法,以便维护该hashCode方法的常规协定,该协定声明相等的对象必须具有相等的哈希代码.

equals()和之间的契约hashCode()不仅仅是Java规范中令人讨厌的怪癖.它在算法优化方面提供了一些非常有价值的好处.由于能够假设,a.equals(b)意味着a.hashCode() == b.hashCode()我们可以做一些基本的等价测试,而无需调用equals()直接.特别是,上面的不变量可以被扭转 - a.hashCode() != b.hashCode()暗示a.equals(b)将是错误的.

如果你看一下HashMap(HashSet内部使用的)代码,你会注意到一个内部静态类Entry,定义如下:

static class Entry<K,V> implements Map.Entry<K,V> {
  final K key;
  V value;
  Entry<K,V> next;
  int hash;
  ...
}

HashMap存储密钥的哈希码以及密钥和值.由于哈希码在密钥存储在映射中的时间内不会发生变化(请参阅Map文档," 如果对象的值以影响等于比较的方式更改,则不会指定映射的行为.对象是地图中的一个键. ")可以安全HashMap地缓存此值.通过这样做,它只需要为hashCode()地图中的每个键调用一次,而不是每次检查键时.

现在让我们看看实现put(),我们看到这些缓存的哈希被利用,以及上面的不变量:

public V put(K key, V value) {
  ...
  int hash = hash(key);
  int i = indexFor(hash, table.length);
  for (Entry<K,V> e = table[i]; e != null; e = e.next) {
    Object k;
    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
      // Replace existing element and return
    }
  }
  // Insert new element
}

特别注意key.equals(k),由于短路评估,条件只调用哈希码相等且密钥不是完全相同的对象.通过这些方法的合同,HashMap跳过这个电话应该是安全的.如果您的对象被错误地实现,那么这些假设HashMap不再成立,您将得到不可用的结果,包括集合中的"重复".

请注意,您的声明" HashSet ...有一个add(Object o)方法,不是从另一个类继承的 "并不完全正确.虽然它的父类,AbstractSet不实现此方法,父接口,Set,不指定方法的合同.该Set接口并不关心哈希值,只有平等,因此它指定该方法在平等的条件下的行为(e==null ? e2==null : e.equals(e2)).只要您遵守合同,HashSet按照文件记录工作,但尽可能避免实际浪费的工作.但是,一旦违反规则,HashSet就不能期望以任何有用的方式行事.

还要考虑如果您尝试将对象存储在一个TreeSet实现不正确的对象中Comparator,您同样会看到无意义的结果.我记录了一些在另一个问题中TreeSet使用不值得信任时的行为示例Comparator:如何在Java中为StringBuffer类实现比较器以便在TreeSet中使用？

Answer 2

你违反了equals/ hashCode基本合同:

来自hashCode()文档:

如果两个对象根据equals(Object)方法相等,则对两个对象中的每一个调用hashCode方法必须生成相同的整数结果.

来自equals:

请注意,通常需要在重写此hashCode方法时覆盖该方法,以便维护该hashCode方法的常规协定,该协定声明相等的对象必须具有相等的哈希代码.

HashSet依赖equals并hashCode一致地实施 - Hash名称的一部分HashSet基本上暗示"此类hashCode用于效率目的." 如果两种方法没有一致地实施,那么所有的赌注都是关闭的.

这不应该在实际代码中发生,因为你不应该违反实际代码中的合同......