布尔字段上的哈希码实现

Question

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

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

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

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

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

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

当您有两个或更多布尔值时，哈希码算法已经处理好了。

再仔细看一点：

// Very simple example
public int hashCode() {
    int result = 31;

    for(boolean val : booleanList) {
        // This is the important part:
        result = 31 * result + Boolean.hashCode(val);
    }

    return result;
}

注意 for 循环的主要部分，在这种情况下，我们以不同的方式对待每个布尔值，因为我们总是在之前将结果乘以 31（或任何好的质数）将其添加到结果中。

如果我们将整个hashcode可视化为base 31的数字，那么我们可以理解每个布尔值的位置和值都在最终结果中被考虑在内.每个boolean都可以看做hashcode中的一个数字，所以对于case(true,false)和case(false,true)，它们会有两个不同的hashcode。

Answer 2

合并多个字段时，一个好的做法是从第一个字段 hashCode 开始，然后在添加每个字段 hashcode 之前将当前结果乘以质数：

@Override public int hashCode() {
  int result = 0;
  result = b1.hashCode();
  result = result * 37 + b2.hashCode();
  result = result * 37 + b3.hashCode();
  // ...
  // result = result * 37 + bn.hashCode();
  return result;
}

您可以在 code generated by Wire（Prococol Buffers 实现）中看到真实示例。

参考文献：

Best implementation for hashCode method（在 Whosebug）
Boolean.hashCode()（在 Whosebug）
Introducing Wire

Answer 3

您有两个选择：

选项 1：位标记

保证永远不会布尔哈希之间发生冲突的最佳方法是使用一种类似于bit flagging，由此您可以让每个布尔值占据自己的位。例如：

// `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
...

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

对此的两种解决方案是增加目标数组的大小（这可能不受您的控制），或者确保布尔值的顺序从可变参数最多到最少。这些都不是最优的，因此这种方法快速简便，但在实践中不是很有效。

选项 2：基础更改哈希

expands on Option 1 as an easier way to accomodate multiple fields. As , this answer 的设计提供了 "general hashing algorithm" 的概述，旨在独立于您尝试散列的内容而有效。

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

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 并使您的哈希无效。

布尔字段上的哈希码实现

hashcode implementation on boolean fields

java

hashcode

选项 1：位标记

选项 2：基础更改哈希