奇怪的HashSet contains()行为

Question

Java中的HashSet让我很困惑。当使用contains()方法时，它会查找hashcode()和equals()的结果吗？但是在某些情况下，它的行为并不正常。如果您将这种代码放入大型项目中，有时会出现问题。问题是为什么最后一条语句打印FALSE？contains()方法在底层做了什么？

class R
{
    int count;
    public R(int count)
    {
        this.count = count;
    }
    public String toString()
    {
        return "R(count attribution:" + count + ")";
    }
    public boolean equals(Object obj)
    {
        if (obj instanceof R)
        {
            R r = (R)obj;
            if (r.count == this.count)
            {
                return true;
            }
        }
        return false;
    }
    public int hashCode()
    {
        return this.count;
    }
}
public class TestHashSet2
{
    public static void main(String[] args) 
    {
        HashSet hs = new HashSet();
        hs.add(new R(5));
        hs.add(new R(-3));
        hs.add(new R(9));
        hs.add(new R(-2));

        System.out.println(hs);

        //change first element
        Iterator it = hs.iterator();
        R first = (R)it.next();
        first.count = -3;
        System.out.println(hs);
        //remove
        hs.remove(new R(-3));
        System.out.println(hs);

        R r1 = new R(-3);
        System.out.println(r1.hashCode());
        Iterator i = hs.iterator();
        R r2 = (R)i.next();
        System.out.println(r2.hashCode());   //same hashcode -3
        System.out.println(r1.equals(r2));   //equals true

        System.out.println("hs contains object which count=-3 ?" + hs.contains(new R(-3)));  //false
    }
}

- CodeFarmer

---

首先看一下 http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html 我认为你错过了 HashMap 的概念。 - niklas

Answer 1

将对象插入HashSet后更改其值，会破坏数据结构的完整性。此后，您不能依赖它完成其工作。

通常不建议使用可变对象作为任何映射的键或集合的值。幸运的是，最常用于此目的的类（String、Integer）是不可变的。

- Michael Borgwardt

Answer 2

这就是为什么你不应该在HashSet和HashMap中使用可变对象作为键。第一个迭代器返回具有hashCode 5的R对象。接下来，你更改了该对象的一个属性（count），但这并不会强制重新计算哈希值。因此，在HashSet看来，你将计数更改为-3的对象仍然位于相应于哈希码5的桶中。然后，你删除了对应于哈希码-3的桶中的对象，也就是最初的R(-3)对象。因此，在那个操作之后，哈希码-3的桶中没有任何对象，所以contains(new R(-3))返回false。

- Hari Menon

---

查看HashMap的实现，这正是发生的事情。 - assylias

Answer 3

HashSet将值存储在桶(bucket)中，当您向哈希集添加元素时，会计算桶索引。其中的思想是：现在可以在一个步骤中读取对象的哈希码并计算出所在的桶。换句话说：contains()是一个O(1)操作。

想象一个简单的哈希集：

bucket    object(hashcode)
#1        5
#2        -3
#3        6

使用哈希函数计算桶，例如：

f(hashcode) :=  |  5 -> 1
                | -3 -> 2
                |  6 -> 3

现在看一下你在例子中所做的事情：你删除了存储在bucket2中的对象（更改了函数），并更改了存储在bucket1中的对象的哈希码。

新的函数如下：

f(hashcode) :=  |  5 -> 1
                |  6 -> 3

f(-3)会返回null（contains()返回false），而你实际上的对象哈希码为-3，存储在应该有哈希码5的位置。

- Andreas Dolk

Answer 4

问题在于 R 对象的哈希码可能会改变。这违反了 hashCode() 方法应该遵守的契约。

---

要理解为什么这很重要，您需要了解哈希表的工作原理。一个Java HashSet内部有一个条目列表数组。当您把一个对象放入哈希表中时，它首先计算该对象的哈希码。然后通过计算将哈希码缩小到数组中的索引。

index = hashcode % array.length

然后它从array[index]开始搜索链表，如果对象不在列表中，则将其添加。

要测试HashSet是否包含一个对象，它执行相同的计算并搜索相同的哈希链。

但是，如果您对对象进行某些操作以导致其哈希码在表中更改，那么上述算法（通常）将在与最初添加到的链不同的链中查找对象。当然，它找不到。

结果是，如果在对象成为集合成员时违反哈希码约定，则HashSet的行为将异常。

---

以下是Java 7 javadoc的内容（请参见java.jang.Object#hashcode()）：

"hashCode的一般契约为：

• 在Java应用程序执行期间，每当同一对象被多次调用时，只要equals比较所使用的信息没有修改，则hashCode方法必须始终返回相同的整数。这个整数不需要在同一个应用程序的不同执行期间保持一致。

• ...

"provided no information ..."这个限制让我感到困惑。我认为它只有在还有一个规则的情况下才能起作用，即在哈希表中存储对象哈希码时不会导致其发生变化。不幸的是，在任何你期望找到它的地方都没有说明这个规则。文档错误？

---

也许我们应该把不改变哈希码的要求称为“口头合同”？:-)

- Stephen C

---

实际上，这并不违反hashCode()的契约（它只需要与equals()一致），而HashSet或HashMap的API文档似乎也没有提到这一点。 - Michael Borgwardt