用作哈希键的 java 对象是否需要 'fully' 不可变？

Question

如果hashCode()计算使用不可变字段并且equals()使用所有字段会不会有问题当 class 用作哈希键时？例如

import java.util.Objects;

public class Car {
    protected final long vin;
    protected String state;
    protected String plateNumber;

    public Car( long v, String s, String p ) {
        vin = v; state = s; plateNumber = p;
    }


    public void move( String s, String p ) {
        state = s; plateNumber = p;
    }


    public int hashCode() {
        return (int)( vin % Integer.MAX_VALUE );
    }


    public boolean equals( Object other ) {
        if (this == other) return true;
        else if (!(other instanceof Car)) return false;
        Car otherCar = (Car) other;
        return vin == otherCar.vin
                && Objects.equals( state, otherCar.state )
                && Objects.equals( plateNumber, otherCar.plateNumber );
    }
}

并且 move() 在汽车对象被插入哈希集后被调用，这可能通过保存在别处的引用实现。

我不关心这里的性能问题。只有正确性。

我读过大蓝java hashCode contact, few answers on SO including this by venerable Jon Skeet and this。我觉得最后的 link 给出了最好的解释并暗示上面的代码是正确的。

编辑

结论：
class 满足 java 中对‘equals()’和‘hashCode()’的约束。然而，当它用作集合中的键时，它违反了对“equals()”的附加要求的限制，无论是否散列。
额外的要求是只要对象是键，'equals()' 就需要保持一致。
请参阅下面 Louis Wasserman 的反例和 Douglas 提供的参考资料。

几点说明：

A) 这个 class 满足 java 对象级约束：

( carA == carB ) 意味着 ( carA.hashCode() == carB.hashCode() )
( carA.hashCode() != carB.hashCode() ) 意味着 ( carA != carB )
equals() 需要自反、对称、传递。
hashCode() 需要保持一致。即在对象的生命周期内不能更改对象。
equals() 需要保持一致只要两个对象都没有被修改.

请注意，“1.”和“2.”的反转不是必需的。而上面的class满足所有条件
java 文档也提到 "equals() … implements the most discriminating possible equivalence relation on objects"，但不确定这是否是强制性的。

B) 至于性能，碰撞避免概率的增量随着我们组合的每个连续成员变量而减少。通常几个精心挑选的成员变量就足够了。

Answer 1

如果您从不在 Car 出现在地图中之后调用 move，那是正确的。否则就是错误的。 hashCode 和 equals 都必须在映射中有一个键后保持一致。

Answer 2

当您的 hashCode() 实现仅使用有限数量的字段（与 equals 相比）时，您会降低几乎所有使用散列的 algorithm/data 结构的性能：HashMap ，HashSet 等。您正在增加碰撞概率 - 这是两个不同对象（equals return false）具有相同哈希值的情况。

Answer 3

简短的回答是：否。

长答案：

不需要完全不变性。但是：

等于必须只依赖于不可变的值。哈希码必须依赖于不可变值，这些值可以是常量，也可以是 equals 中使用的值的子集，也可以是 equals 中使用的所有值。等号中未提及的值不得是哈希码的一部分。

如果你改变值等于和哈希码依赖，你很可能不会在基于哈希的数据结构中再次找到你的对象。看看这个：

public class Test {


    private static class TestObject {
        private String s;

        public TestObject(String s) {
            super();
            this.s = s;
        }

        public void setS(String s) {
            this.s = s;
        }

        @Override
        public boolean equals(Object obj) {
            boolean equals = false;
            if (obj instanceof TestObject) {
                TestObject that = (TestObject) obj;
                equals = this.s.equals(that.s);
            }
            return equals;
        }

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

    public static void main(String[] args) {

        TestObject a1 = new TestObject("A");
        TestObject a2 = new TestObject("A");

        System.out.println(a1.equals(a2)); // true

        HashMap<TestObject, Object> hashSet = new HashMap<>(); // hash based datastructure

        hashSet.put(a1, new Object());

        System.out.println(hashSet.containsKey(a1)); // true

        a1.setS("A*");

        System.out.println(hashSet.containsKey(a1)); // false !!! // Object is not found as the hashcode used initially before mutation was used to determine the hash bucket

        a2.setS("A*");

        System.out.println(hashSet.containsKey(a2)); // false !!! Because a1 is in wrong hash bucket ...

        System.out.println(a1.equals(a2)); // ... even if the objects are equals

    }

}

Answer 4

您可以随心所欲地改变关键候选项，在它们用作键之前或之后（不是期间）。在实践中，执行此规则非常困难。如果你改变对象，你就无法控制是否有人将它们用作键。

键的不变性更容易，消除了微妙的、难以发现的错误的来源，并且键的效果更好。

在你的情况下，我没有发现正确性问题。但是为什么你不在哈希码中包含所有字段呢？

Answer 5

当仅考虑 hashCode 和 equals 合同时，您认为此实现满足他们的要求是正确的。 hashCode 使用 equals 使用的字段的严格子集足以保证 a.equals(b) 按要求暗示 a.hashCode() == b.hashCode()。

但是，当您引入 Map 时，情况就会发生变化。来自Map javadoc、"The behavior of a map is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is a key in the map."

在作为 Map 中的键的 Car 上调用 move 后，Map 的行为现在未指定。在许多情况下，它实际上仍会按您希望的方式工作，但奇怪的事情可能会以难以预测的方式发生。虽然 Map 自发清空自身或将所有查找切换为使用随机数生成器在技术上是有效的，但更可能的情况可能是这样的：

Car car1 = ... Car car2 = ... // a copy of car1 Map<Car, String> map1 = ... map1.put(car1, "value"); assert map1.get(car2).equals("value"); // true car1.move(...); assert map1.get(car2).equals("value"); // NullPointerException on the equals call, car2 is no longer found

请注意，car2 和 Map 都没有以任何方式改变自身，但是 car2 的映射无论如何都改变了（或者更确切地说，消失了）。此行为未正式指定，但我猜想大多数 Map 实现都会这样做。

Answer 6

哈希通过将项目放入 "buckets" 来工作。每个桶由hashcode计算。找到桶后，搜索将继续使用 equals.

逐一比较每个项目

例如：

插入时：id为100的对象放入5号桶（hashcode计算为5）
在检索期间：您要求 hashmap 找到项目 100。如果哈希现在计算为 7，则算法将在存储桶 7 中搜索您的对象，但永远找不到您的对象，因为它位于存储桶 5 中。

总结：哈希码和实际密钥一起工作。前者用于知道该项目应该在哪个桶中。 equals 比较使用后者寻找实际项目 return。

Answer 7

简短回答：应该没问题，但要为奇怪的行为做好准备。

更长的答案：当您更改参与键上 equals() 的字段时，将不再找到该键键入的值。

更长的答案：这看起来像 X/Y 问题：你问的是 X，但你确实需要 X 来完成 Y。也许你应该问 Y？

您的汽车由 vin 唯一标识。一辆车等于它自己。但是，汽车可以在不同的州注册。也许答案是将注册对象（或其中的一些）附加到汽车上？然后您可以将 car.equals() 与 registration.equals() 分开。

用作哈希键的 java 对象是否需要 'fully' 不可变？

Do java objects used as hash keys need to be 'fully' immutable?

java

hashmap

hashcode