2

文档HashSet.add说

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

由于我下面的代码将返回 false for e.equals(e2)，我希望它可以让我添加两次相同的实例。但是该集合仅包含我的实例一次。有人可以解释为什么吗？

package com.sandbox;

import java.util.HashSet;
import java.util.Set;

public class Sandbox {

    public static void main(String[] args) {
        Set<A> as = new HashSet<A>();
        A oneInstance = new A();
        System.out.println(oneInstance.equals(oneInstance));    //this prints false
        as.add(oneInstance);
        as.add(oneInstance);
        System.out.println(as.size());  //this prints 1, I'd expect it to print 2 since the System.out printed false
    }

    private static class A {
        private Integer key;

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof A)) {
                return false;
            }

            A a = (A) o;

            if (this.key == null || a.key == null) {
                return false;   //the key is null, it should return false
            }

            if (key != null ? !key.equals(a.key) : a.key != null) {
                return false;
            }

            return true;
        }

        @Override
        public int hashCode() {
            return key != null ? key.hashCode() : 0;
        }
    }

}
4

4 回答 4

11

HashSet（实际上是 HashMap 底层）有一个“优化”，它在调用equals()方法之前检查对象引用是否相等。由于您将相同的实例放入两次，因此即使equals()方法不同意，它们也被认为是相等的。

来自 HashMap.put() 的相关行：

        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
于 2013-05-02T17:17:02.937 回答
3

您违反了 的合同Object.equals(Object)，该合同的开头是：

equals 方法在非空对象引用上实现等价关系：

  • 它是自反的：对于任何非空引用值 x，x.equals(x)都应该返回 true。

正如您的示例代码所说：

System.out.println(oneInstance.equals(oneInstance)); //this prints false

似乎HashSet<E>（完全合理地）假设自反性，并且当它发现完全相同的对象已经在集合中时不检查相等性，作为一种优化。因此它甚至不会调用你的equals方法——它认为对象已经在集合中，所以不添加第二个副本。

特别是，如果x.equals(x)为假，那么任何遏制检查也将毫无用处。

我会这样实现equals：

public boolean equals(Object o) {
    // Normal reflexive optimization
    if (this == o) {
        return true;
    }

    // "Correct type" check
    if (!(o instanceof A)) {
        return false;
    }
    
    A a = (A) o;

    // If both keys are null, the objects are equal. This is the most normal
    // approach; you *could* make non-identical objects with null keys non-equal,
    // but that would be odd.
    if (this.key == null && a.key == null) {
        return true;
    }

    // If exactly *one* key is null, the objects are not equal.
    if (this.key == null || a.key == null) {
        return false;
    }

    // By now we know that both keys are non-null; use normal equality.
    return this.key.equals(a.key);
}

或者，如果您使用的是 Java 7：

public boolean equals(Object o) {
    // Normal reflexive optimization
    if (this == o) {
        return true;
    }

    // "Correct type" check
    if (!(o instanceof A)) {
        return false;
    }
    
    A a = (A) o;
    return Objects.equals(this.key, a.key);
}
于 2013-05-02T17:19:44.790 回答
2

哈希映射/表的工作原理是获取一个对象并使用“哈希”函数对其进行“哈希”处理，以生成一个伪随机均匀分布的唯一 ID，该 ID表示该对象，其中该 ID 可用作可索引结构（如数组）的键。理想情况下，您将拥有一个完美的散列，其中每个唯一项目都会产生一个唯一的可索引 ID。

显然，您的数组的大小是固定的（您可以增加数组，但这会极大地影响运行时性能）所以在某些时候，如果您继续向哈希映射/表添加元素，您最终将获得 2 个具有相同哈希码和那么你就会发生碰撞；这就是 equals 发挥作用的地方。

当这种情况发生时，相等性用于通过迭代（通常通过将 LinkedList 存储在索引位置而不仅仅是元素）可用对象并检查 equals 方法来消除您正在寻找的键/值的歧义。

因此，您的情况的问题很简单：如果您的哈希实现错误，那么 HashSet（由 HashMap 支持）无法在其表中找到您的对象，因此从不费心调用 equals（看看 HashMap.get()看看他们的实施）。

如果你想让它工作，你在 equals 中使用的任何东西都必须在 hashCode() 中使用，反之亦然。如果你实现了equals()，那么实现hashCode() 是个好主意。如果你实现 hashCode() 那么你必须实现 equals 才能使散列真正起作用。

于 2013-05-02T17:24:17.493 回答
0

我不知道具体原因，但我不得不指出，当你实现 equals 时，你应该坚持的 equals 方法的一部分约定是它是自反的，这意味着同一个对象等于它自己。所以你的equals应该返回true。

我对您的问题的回答是，当您仅将同一实例的两个项目添加到 HashSet 时，不会调用 .equals() 方法。到目前为止，可能只调用了 hashCode 。由于 hashCode 返回键，它每次都会返回相同的键，并且该项目只是被哈希到同一个地方两次，在集合中只留下一个项目。

于 2013-05-02T17:12:08.420 回答