hashCode复杂度要求

Question

我正在研究不可变 Board class，它表示 15 益智游戏的 N×N 棋盘 （如果是 N×N，它将是 N^2 - 1 个益智游戏）。我已经覆盖了 equals() （如下所示） 并因此覆盖了 hashCode() 方法以保留 Object contract，但是 hashCode我要实现的方法需要二次时间（它应该检查所有 N^2 - 1 个条目）。

所以我的问题是：如果 hashCode 不占用固定时间，它是否被认为是一种不好的做法，因为它可能会损害 HashMap / HashTree 的性能（我不打算使用它反正）？我是否应该选择更简单的方法，例如每次都返回相同的质数，即使它会增加碰撞？

示例 3×3 板（取自 toString() 方法）

1  2  3 
4  5  6 
7  0  8

两个 Boards 被视为相等，前提是所有条目都匹配。

Board class 中的代码片段：

public class Board {

    private final int[][] tilesCopy;    // tiles
    private final int N;                // size of the board

... code...


@Override
    public boolean equals(Object y) {
        if (!(y instanceof Board)) return false;
        Board that = (Board) y;
        if (this.size() != that.size()) return false;

        for (int i = 0; i < this.size(); i++) {
            for (int j = 0; j < this.size(); j++) {
                if (this.tileAt(i, j) != that.tileAt(i, j)) return false;
            }
        }
        return true;
    }

@Override 
public int hashCode() {
    ...code...
    }

Answer 1

根据您提到的原因，一个好的做法是尽可能快。但是更重要的是hashCode要有辨别力。

很明显，当您有 N*N 个元素时，哈希应该考虑所有元素。当你试图忽略某些东西时，它会导致更多的冲突，这 - 对于 HashMaps 等会导致更多的 equals 调用，这会更加昂贵（即使你可以快速 return false 当你发现不匹配，equals 的数量将逐渐大于 hashCode 调用。

当 hashCode 将在一个实例上被调用更多次并且计算成本很高时，您应该只评估一次，然后 将其缓存 进一步的调用（当然，你的对象必须是不可变的，否则你将不得不在对象突变时使缓存的哈希码无效）。

更新： 作为灵感，Java 集合（Lists、Sets 等）哈希码计算包括遍历所有元素也。即使仅使用集合的大小作为哈希码也是可以的（从 API 合同的角度来看）。

更新 2：如果您不打算使用任何 hash 集合，您实际上可以实现 return 0 哈希码，因为它无论如何都不会被使用。但是，如果您与其他人共享此实现，则应实现它，因为他们可能希望将其放入此类集合中。

Answer 2

不考虑"bad practice"。真的没有好的或坏的做法。

你真正需要考虑的是它是否是最好的解决方案。有没有办法计算不是 O(N^2) 的哈希码？您是否打算经常计算这些哈希码以使 O(N^2) 变得重要总体？你能避免（重新）计算相同状态的哈希码吗？

跳出框框思考一下，让我们假设您的棋盘状态实际上是相互关联的，其中一个状态代表相对于前一个状态的增量变化（移动）。（这就是游戏规则通常的运作方式......）如果您适当地选择了哈希算法，您可以利用游戏的增量性质从先前状态的哈希码计算新状态的哈希码。

比如异或函数有属性表示它是可逆的；即，如果 A XOR B 是 C，则 C XOR B 是 A。因此，如果棋盘状态的哈希码由元素哈希的 XOR 组成，则可以从 hashcode(state S) 到 hashcode(state S + 1)通过仅对已更改的状态元素的哈希码进行异或运算。

当然，您需要在表示棋盘状态的对象中缓存哈希码。但是如果你这样做，你应该能够在 O(1) 而不是 O(N^2).

中计算哈希码

hashCode复杂度要求

hashCode complexity requirement

java

hashcode