布尔字段的哈希码实现

如果有两个布尔字段,我如何实现一个好的哈希码？通常人们只是将整数值添加到其哈希码值中.但是,如果我只是在我的哈希码中添加1或0,我认为它不好.因为如果我有两个A类对象:

obj1.b = true,obj1.c = false.

obj2.b = false,obj2.c = true.

其他一切都是一样的.然后这两个不等对象的哈希码是相同的.我知道这种情况还可以.但想象一下,如果有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;
    }
}

Jon Egeland.. 9

你有几个选择:

选项1:位标记

最好的办法,以保证有可能永远不会为布尔的哈希值之间的碰撞是使用一个类似于中所使用的技术有点萎靡不振,因此你必须每个布尔占据自己的位.例如:

// `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:基础更改哈希

Pham Trung在他的回答中展示的设计扩展了选项1,作为容纳多个领域的简单方法.正如Adrian Shum所评论的那样,这个答案提供了一个"通用散列算法"的概述,它被设计为独立于你想要散列的内容而有效.

基本思想是将每种类型的简化哈希值乘以一些任意大的素数,以确保每个哈希值都是唯一的(尽管证明了这一点可以避免我).例如:

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你的哈希并使你的哈希值无效.

你有几个选择:

选项1:位标记

最好的办法,以保证有可能永远不会为布尔的哈希值之间的碰撞是使用一个类似于中所使用的技术有点萎靡不振,因此你必须每个布尔占据自己的位.例如:

// `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:基础更改哈希

Pham Trung在他的回答中展示的设计扩展了选项1,作为容纳多个领域的简单方法.正如Adrian Shum所评论的那样,这个答案提供了一个"通用散列算法"的概述,它被设计为独立于你想要散列的内容而有效.

基本思想是将每种类型的简化哈希值乘以一些任意大的素数,以确保每个哈希值都是唯一的(尽管证明了这一点可以避免我).例如:

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你的哈希并使你的哈希值无效.