如何在hashCode()中将长整型映射为整数?

53

我有一系列的对象,它们拥有一个long字段,该字段的值可以在整个系统中唯一标识特定的对象,类似于GUID。我已经重写了Object.equals()方法来使用这个ID进行比较,因为我希望它适用于对象的副本。现在我也想重写Object.hashCode()方法,这基本上意味着将我的long映射到某个int返回值。

如果我正确理解hashCode的作用,它主要用于哈希表,因此希望具有均匀分布。这意味着,简单地返回id % 2^32就足够了。是这样吗?还是我需要注意其他什么问题?


顺带一提,即使您只想保留低32位,也不需要进行模运算。将其转换为“int”即可:int hashCode = (int) id - Grodriguez
@Grodriguez 抱歉,但这个答案很糟糕!它会导致许多对象具有相同的哈希码,从而创建各种哈希冲突。您总是希望哈希码均匀分布。此外,自Java 8以来,已经引入了更好的解决方案,因此接受的答案不是最佳解决方案。请参考“Nathan”给出的答案,因为Long.hashcode(long)不会在堆栈上创建新对象。 - Neuron
3
任何将64位值映射为32位的哈希函数都会导致许多对象具有相同的哈希码,这是不可避免的。此外,并没有保证(this.longValue()^(this.longValue()>>>32))能产生比仅保留该值的低32位更均匀分布的哈希码。 - Grodriguez
@Grodriguez,是的,再次道歉。你是对的。我没有意识到将long强制转换为int会包装int而不是停留在Integer.MAX_VALUEMIN_VALUE,这正是我所期望的强制转换实际上要做的事情。 - Neuron
6个回答

94

从Java 8开始,您可以使用

Long.hashCode(guid);

对于较旧版本的Java,您可以使用以下内容:

Long.valueOf(guid).hashCode();
请注意,此解决方案为堆栈创建一个新对象,而第一个解决方案则没有(尽管Java很可能会优化对象创建..)。
查看文档后,两种方式都只使用以下算法:
(int)(this.longValue()^(this.longValue()>>>32))

这些方案很不错,因为它们利用了Java库——总是更好地利用已经经过测试的东西。


2
这可能会很昂贵,因为它需要对象创建(因此有Guava替代方案)。至于算法本身,唯一危险的时候是当上下32位具有相关含义时。例如,对于一个在单个长整型中存储32位x和y坐标的“Point”类来说,这将是一个可怕的哈希码。 - Mark Peters
1
虚拟机完全可以优化掉对象的创建,但我不会想要依赖这点。 - TofuBeer
1
@TofuBeer:实际上,我猜虚拟机不可能优化掉它(尽管我想知道编译器是否可以合法地将其优化掉)。你有源代码/JLS/JVM规范链接吗?我对这个问题非常感兴趣。Java开发人员(包括我自己)通常会将优化问题委托给虚拟机,但事实上规范阻止了这些优化的发生。此外,我们经常依赖可能存在但在实践中不会发生的优化。 - Mark Peters
5
@Mark: 如果使用-XX:+DoEscapeAnalysis参数,最近的Sun/Oracle JVM将对此进行优化。JVM会注意到Long实例不需要存在于语句之外,因此可以在堆栈上创建。此外,它还可以内联代码(它会注意到我们谈论的是Long而不是另一个扩展Long的类)。基于堆栈的创建和内联允许JVM进行其所知道的全部主机进一步优化。 - Thomas Pornin
1
@james 不确定98.8%的统计数据(这取决于您进行了多少插入),但可以将其视为“生日悖论”问题(http://en.wikipedia.org/wiki/Birthday_problem)。在Mark的示例中仅有1024个可能的值,随机选择值进行38次哈希后就有50%的碰撞几率,仅经过98次后就有99%的几率。这就是为什么哈希如此困难的原因:对于性能敏感的哈希,您需要了解您的数据并相应地进行哈希,或者在通用库的情况下(更难),预测可能的用法并混合位。 - Cowan
显示剩余8条评论

9

如果你还没有使用Guava,那么这可能只是一个小问题,但是Guava可以很好地帮你完成这个任务

public int hashCode() {
  return Longs.hashCode(id);
}

这将给你相当于 Long.valueOf(id).hashCode() 的值:
return (int) (value ^ (value >>> 32));

此外,如果您有其他值或对象是哈希码的一部分,您可以直接编写以下代码:

return Objects.hashCode(longValue, somethingElse, ...);

long会被自动装箱成Long,因此您将获得正确的哈希码作为整体哈希码的一部分。


我不会为了这个而引入一个全新的库,但我以前从未听说过Guava,它似乎非常有帮助并值得从更一般的角度来看。谢谢! - Hanno Fietz
1
@Hanno:是的,仅为了这个小东西肯定不值得。但它是一个拥有大量有用功能的伟大库! - ColinD
过去几年里,我没有做太多的Java编程,但是Guava真是太棒了,它提供了许多有用的类来改进你的代码。 - David Harkness

6
您已经正确理解了hashCode的目的。是的,均匀分布是理想的(虽然不是实际要求)。
我建议使用((id >> 32) ^ id)
上述表达式:
- 使用原始值的所有位,不会提前丢弃任何信息。例如,根据您生成ID的方式,高位可能更频繁地更改(或相反)。 - 不会引入任何偏向于具有更多1(0)的值,如果两个半部分使用OR(AND)操作组合,则会出现这种情况。

+1. 这几乎是为 java.lang.Long 定义的 hashCode,尽管它使用 >>> 而不是 >>。我想知道 (new Long(id)).hashCode(); 或类似的代码是否能够得到优化。 - Steve Jessop
4
在这种情况下,>>>>>没有区别,因为移位期间引入的额外32位将被丢弃。 - Grodriguez
1
简单解释一下Grodriguez的回答(因为每个人都要从某个地方开始),负数用最高位的1表示。当数字为负数时,它是反向的,并且从0xffffffff开始倒数。>>是有符号位移,而>>>是无符号位移。有符号位移保留最高的1位,以保持负号,例如-0x10 >> 0x2得到-0x4,而-0x10 >>> 0x2得到0x3ffffffc。此外,-1 >>> 1得到0x7ffffffflongint宽两倍,因此将一半的位向下移动只影响前32位。 - Jack G

3

Java 8在JDK中添加了Long.hashCode(long)

以下代码可以提高性能。该代码将计算缩小到32位int,而不是使用64位long进行计算。这在32位及更小的架构上可能会有所不同。x86机器上的32位进程可以将其优化为一个简单的指令,即对2个寄存器执行XOR操作。

return (int)(value ^ (value >>> 32));

正如其他答案中所指出的那样,这种方法并不具有良好的雪崩效应,可能会导致碰撞。可以使用密码哈希函数来确保高雪崩效应。然而,还有其他算法,例如Murmur Hash(更多信息),它们具有非常好的雪崩效应,但不会消耗太多CPU时间。

1
int result = (int)((longVal >> 32) ^ longVal);

将会更加均匀分布,因为如果您的长整型数值只有上位比特发生变化,取模运算不会返回不同的值。


1

(l >> 32) ^ l 在大多数情况下是一个很好的哈希码;特别是当 long 具有均匀分布时。

由于它是被接受的答案,我在此发布这篇文章,以澄清我的一些评论,即在某些情况下,它不是一个很好的 long 类型的哈希码。

我给出的例子是一个像这样的 Point 类:

public class Point {
    private final long coords; //x in high-bits, y in low
    public int getX() {
        return (int)(coords >> 32);
    }
    public int getY() {
        return (int)coords;
    }
    public int hashCode() {
        return (int)((coords >> 32) ^ (coords));
    }
}

看起来有些牵强,但有时您会将多个“字段”打包到一个长字段中。

因此,coords字段表示32位x和32位y。那么这是个问题吗?如果每个x和y在各自的32位上均匀分布,那么就不是问题。但在实践中,这是不太可能的。更有可能的情况是X和Y受到某个数字的限制。假设为1024,因为它是2^10。这意味着最多设置每个X和Y的低10位:

00000000 00000000 000000XX XXXXXXXX 00000000 00000000 000000YY YYYYYYYY

有2^20(1024 * 1024)种可能的组合。但是hashCode方法在做什么呢?

  00000000 00000000 000000XX XXXXXXXX 
^ 00000000 00000000 000000YY YYYYYYYY
-------------------------------------
= 00000000 00000000 000000?? ????????

由于只有低10位可以是非零值,因此最多可能有2^10(1024)个hashCode值。哈希值与实际值的比率为1024:(1024*1024)1:1024。因此,一开始就有1/1024的概率两个数字具有相同的哈希值。

现在让我们通过应用birthday problem中的数学来计算碰撞的概率。设p(n)为n个值中至少会有一个碰撞的概率。我们知道p(1025+) = 1,因为只有1024个值。

p(n) = 1 - (n! * (1024 choose n))/1024^n

这可以转化为以下内容:

n: p(n)
1: 0.00000
2: 0.00098
3: 0.00293
4: 0.00585
5: 0.00973
6: 0.01457
...
38: 0.50096
...
79: 0.95444
...
148: 0.99999

仅有38个项目,很可能会发生碰撞。有148个项目时,至少有99.999%的概率会发生碰撞。在148个项目中,每个项目与另一个项目发生碰撞的概率为7%。通过正确的哈希函数,结合对领域的了解,这些数字可以轻松降至0。

换句话说,了解您的领域以及实践中发生的事情是制作高性能哈希的关键。库函数尝试尽可能做到不了解您的领域,并且为了性能通常依赖于在实践中不会出现的数据分布。


最终,我的回答与我最初的陈述无关,即使用x ^ y作为Point类的哈希是合理的。你在这里的论点是,如果x和y限制在最大1024,则不合理。这是一个有力的观点,但并不否认我的原始陈述。 - james
@james:我的意思是,这只是不必要的无知。在实践中,点集在其定义域上均匀分布的频率有多高?几乎从来没有。Bloch建议使用此类型的hashCode计算方法是有原因的:somePrime * getX() + getY()。虽然它并不完美,但质数的作用是尝试在不了解域的情况下“去相关化”数据。这也是实际的Point2D类的工作方式。 - Mark Peters
@james: 顺便说一句,这对于 x 和 y 被限制在 2^30 的情况同样适用,尽管对于 2^30,你可能会预期会有大量的碰撞;对此你无法做任何事情。选择 1024 只是因为它容易解释。 - Mark Peters

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接