java - boolean 字段上的哈希码实现

Question

如果有两个 boolean 字段，我如何实现一个好的哈希码？通常人们只是将整数值添加到他们的哈希码值中。但是，如果我只是简单地将 1 或 0 添加到我的哈希码中，我认为这并不好。因为如果我有两个 A 类对象:

obj1.b = true，obj1.c = false。

obj2.b = 假，obj2.c = 真。

其他都是一样的。那么这两个不相等对象的哈希码是相同的。我知道这种情况没问题。但是想象一下，如果有 100 个 boolean 字段，那么碰撞会太多吗？我不希望这么多不同的对象落在同一个桶里。

我在下面所做的是将不同的数字分配给每个字段的不同真值，因此对象哈希码可以非常不同。

public class A {

    private final String a;
    private final boolean b;
    private final boolean c;

...

@Override public int hashCode(){
            int i,j;
            if(b) {
                    i = 10;
            }
            else {
                    i = 0;
            }
            if(c) {
                    j = 88;
            }
            else {
                    j = 3;
            }
            int result = 0;
            result = 31*result + i + j;
            result = 31*result + (a != null ? a.hashCode() : 0);
            return result;
    }
}

Answer 1

你有几个选择:

选项 1:位标记

保证 boolean 哈希值之间永远不会发生冲突的最佳方法是使用一种类似于 bit flagging 中使用的技术，从而让每个 boolean 值占用它自己的位。例如:

// `byte` can be replaced with `short`, `int`, or `long` to fit all of your variables.
byte = 0;
if(bool1) booleans += 1;  // 0001
if(bool2) booleans += 2;  // 0010
if(bool3) booleans += 4;  // 0100
if(bool4) booleans += 8;  // 1000
...

但是，对于大量 boolean 值，这种方法很快就会变得低效，并且高度依赖于目标数组的大小。例如，如果您有一个大小为 16 的目标数组，则只有前 4 个对哈希值有影响(因为最大索引是 1111)。

解决这个问题的两个方法是增加目标数组的大小(这可能不受您的控制)，或者确保您的 boolean 值的顺序从可变参数最多到最少。这些都不是最优的，因此这种方法既快速又简单，但在实践中不是很有效。

选项 2: rebase 哈希

Pham Trung shows in his answer 在选项 1 上扩展的设计，作为容纳多个字段的更简单方法。作为 Adrian Shum commented，this answer 提供了“通用哈希算法”的概述，该算法旨在独立于您尝试哈希的内容而有效。

基本思想是将每种类型的简化散列值乘以某个任意大的素数，以确保每个散列都是唯一的(尽管我无法证明这一点)。例如:

int result = 0;
result = 31*result + bool1 ? 1 : 0;
result = 31*result + bool2 ? 1 : 0;
...

对于更稀疏的散列分布，您可以将其与 Boolean.hashCode 结合使用，如其他答案所示:

int result = 0;
result += 31*result + bool1.hashCode();
result += 31*result + bool2.hashCode();
...

此解决方案的优点在于它可以应用于其他类型，就像您在示例代码中已有的那样:

...
result = 31*result + i;
result = 31*result + (a != null ? a.hashCode() : 0);
result = 31*result + my_complex_object.hashCode();

注意:在这些示例中，31 只是一些任意素数。您可以轻松地使用 37、113 或 23456789。但是，使用更大的被乘数需要权衡取舍，即您的哈希将更快地超过 Integer.MAX_VALUE 并使您的哈希无效。