hashCode 可以在不同的运行之间 return 不同的值吗？

Question

我正在努力了解 hashCode 背后的全部故事。在大多数实现中，hashCode 是完全确定的，例如 StringUTF16 class:

public static int hashCode(byte[] value) {
    int h = 0;
    int length = value.length >> 1;
    for (int i = 0; i < length; i++) {
        h = 31 * h + getChar(value, i);
    }
    return h;
}

我认为这样的实现不是很好：构造具有相同 hashCode 的示例很容易。例如，系统的用户可以提交完全相同的 hashCode 的单词进行 DOS 攻击。它不适用于 String，因为它实现了 Comparable（并且 HashMap 是一个过度黑客攻击的混乱），但它对 classes 没有帮助'实施 Comparable.

更好的方法似乎是使用一个随机因子（而不是31），这样用户就不知道如何构造坏的例子（而且它也有一些理论性质），像这样：

class ImmutableArray{
    // Note static keyword. It guarantees that for the same run all objects use the same x.
    private static final int x = generateRandomPrime();

    int[] values;

    public int hashCode() {
        int res = 5;
        for (int v : values) {
            res = res * x + v;
        }
        return res;
    }

    ...

}

现在，我的问题是：这个实现有什么不好的地方吗？我能看到的唯一问题是程序的不同运行会 return 不同的 hashCode，但我无法想象会出现问题的具体场景。

Answer 1

除非您进入专门的序列化应用程序，否则我认为这不是什么大问题。在大多数情况下，就运行时而言，设置它的方式基本上等同于添加任意 31 值（该值不会改变）。

不过，通过反射 'trickery' 您可能会改变该值并使整个系统偏离轨道（想想 setAccessible 和修饰符标志）。

如果在对象被序列化并传输到不同环境时存在依赖于哈希码和一致性的设置，我认为出现问题的可能性更大。哈希码在两个独立环境之间进行比较的方式很可能在实际上不应该不同的情况下有所不同）。

Answer 2

不要求 hashCode 在不同的 JVM 中提供相同的值。例如，HashMap class 在序列化时不会保留地图键的 hashCode 值。相反，hashCode 值会在映射反序列化时重新计算。

我能看到的唯一潜在问题是在每次调用时重新计算 hashCode 效率很低。您可以通过延迟计算来解决这个问题（例如 String::hashCode 所做的）。

但是如果你实现惰性hashCode计算，你需要将存储它的字段声明为transient。否则，去持久化键实例中的 hashCode 值将不会 == 为键 "equal" 的另一个实例计算的 hashCode 值。（换句话说，hashcode / equals contract 被破坏了！）这将导致查找失败。

如果操作正确，HashMap 的序列化应该没有问题。例如，您可以遵循 String::hashCode 的方法并使用零作为缓存的 hashCode 值，这意味着 "the code needs to be calculated" 到 hashCode() 方法。

^{（如果您的键 class 没有字段来保存缓存的 hashCode 值，则不会出现保留该值的问题。）}

另一件需要注意的事情是修改密钥 class 以实现 Comparable 将是另一种防御基于 DOS 的攻击的方法。在您的示例 class 中，compareTo 方法的实现很简单。请注意，您实现的排序不需要在语义上有意义。它只需要稳定和一致。

hashCode 可以在不同的运行之间 return 不同的值吗？

Is it OK for hashCode to return different values between different runs?

java

hash

non-deterministic