在重写hashCode()时使用较大的素数作为乘数

Question

我已经阅读了过去几个小时的哈希码函数,并且在自定义哈希码实现中使用素数作为乘数已经积累了一些问题.如果我能对以下问题有所了解,我将不胜感激:

• 在对@ mattb的答案的评论中,@ hstoerr主张使用更大的素数(例如524287)而不是公共素数31.我的问题是,给定一对或元素的哈希码函数的以下实现:

  @Override
  public int hashCode() {
      final int prime = 31;
      int hash1 = (pg1 == null) ? 0 : pg1.hashCode();
      int hash2 = (pg2 == null) ? 0 : pg2.hashCode();
      return prime * (hash1 ^ hash2);
  }
  

这不会导致返回的溢出,int如果prime是大数？

• 假设溢出是没有问题的(JVM做一个自动施法)是它更好地做一个位位移,而不是一个演员？

• 我认为哈希码函数的性能根据哈希码的复杂性而有很大差异.主乘数的大小是否不影响性能？

• 在自定义哈希码函数中使用多个素数而不是单个乘法器更好/更智能/更快？如果没有,还有其他一些优势吗？请参阅@ jinguy对相关问题的回答中的示例:

  public int hashCode() {
      return a * 13 + b.hashCode() * 23 + (c? 31: 7);
  }
  

其中a是一个int,b是一个String和c是boolean.

• 如何像long lhash = prime * (hash1 ^ hash2);然后用(int)((lhash >> 32) ^ lhash)？这是我在另一个问题上看到的东西,但是并没有真正解释为什么这样做是个好主意.

Answer 1

为小说提前道歉.随意提出建议或直接编辑.--Chet

有溢出,但也不例外.

危险不是来自失去准确性,而是失去范围.让我们使用一个荒谬的例子,其中"prime"是2的大功率,而8位无符号数字是为了简洁.并假设(hash1 ^ hash2)是255:

        "prime": 1000 0000
(hash1 ^ hash2): 1111 1111

在括号中显示截断的数字,我们的结果是:

        product: [0111 1111] 1000 0000

但乘以128与左转7个位置相同.所以我们知道无论价值如何(hash1 ^ hash2),产品中最不重要的地方都会有七个零.因此,如果(hash1 ^ hash2)是奇数(最低有效位= 1),那么乘以128的结果将始终为128(在截断较高数字之后).如果(hash1 ^ hash2)是偶数(LSB为0,则产品将始终为零.

这扩展到更大的位大小.一般的观点是,如果" prime" 的低位为零,则表示您正在执行移位(或多次移位+求和)操作,这将使您在低位中为零.并且乘法乘积的范围将受到影响.

但是让我们尝试制作" prime奇数",这样最低有效位总是为1.考虑将其分解为移位/添加操作.未移位的值(hash1 ^ hash2)将始终是其中一个加数.现在,至少prime根据原始(hash1 ^ hash2)值的位来设置被偶数" "乘数转换为保证无用的最低有效位.

现在,让我们考虑一个prime实际上是素数的值.如果它超过2,那么我们知道它很奇怪.所以较低的位没有转变为无用.通过选择足够大的素数,您可以在输出值范围内获得比使用较小素数时更好的分布.

尝试使用8443(0010 0000 1111 1011)和59(0000 0000 0011 1011)进行16位乘法运算.它们都是素数,59的低位与65531的低位匹配.例如,如果hash1和hash2都是ASCII字符值(0 ... 255),则所有结果(hash1 ^ hash2)*59将<= 15045.这意味着16位数的大约1/4的散列值范围(0..65535)未被使用.

但是(hash1 ^ hash2) * 8443到处都是地图.如果(hash1 ^ hash2)低至8则溢出.即使对于非常小的输入数字,它也使用全部16位.即使输入数字在相对较小的范围内,整个范围内的散列值聚类也要少得多.

假设溢出是没有问题的(JVM做一个自动施法)是它更好地做一个位位移,而不是一个演员？

很可能不是.无论如何,JVM应该转化为主处理器上的有效实现.整数乘法应该在硬件中实现.如果没有,JVM负责将操作转换为适合CPU的操作.整数乘法的情况很可能已经高度优化.如果在给定的CPU上作为shift-and-add更快地完成整数乘法,那么JVM应该以这种方式实现它.但是编写JVM的人不太可能关注多个移位和添加操作可以组合成单个整数乘法的情况.

我认为哈希码函数的性能根据哈希码的复杂性而有很大差异.主乘数的大小是否不影响性能？

不会.无论大小,设置的位数等等,在硬件中完成的操作都是相同的.它可能是几个时钟周期.它会根据特定的CPU而有所不同,但无论输入值如何,都应该是恒定时间操作.

在自定义哈希码函数中使用多个素数而不是单个乘法器更好/更智能/更快？如果没有,还有其他一些优势吗？

只有当它减少了碰撞的可能性时,这取决于你正在使用的数字.如果您的哈希码依赖于A并且B它们在相同的范围内,您可以考虑使用不同的素数或移位其中一个输入值以减少这些位之间的重叠.由于您依赖于它们各自的哈希码,而不是它们的直接值,因此可以合理地假设它们的哈希码提供了良好的分布等.

考虑到您是否希望哈希码(x, y)与之不同的一个因素(y, x).如果您的哈希函数对待A,并B以同样的方式,然后hash(x, y) = hash(y, x).如果这是你想要的,那么一定要使用相同的乘数.不是,使用不同的乘数是有道理的.

如何像long lhash = prime * (hash1 ^ hash2);然后用(int)((lhash >> 32) ^ lhash)？这是我在另一个问题上看到的东西,但是并没有真正解释为什么这样做是个好主意.

有趣的问题.在Java中,long是64位,而int是32位.因此,这会根据需要使用两倍的位生成散列,然后从高位和低位组合得到结果.

如果将数字乘以n素数p,并且最低k位n全部为零,则产品的最低k位n * p也将全为零.这是很容易看到-如果你相乘,也就是说,n = 0011 0000和p = 0011 1011,那么该产品可以表示成两个移位操作的总和.要么,

00110000 * p = 00100000 * p + 00010000 * p
             = p << 5 + p << 4

采用p = 59和使用无符号8位整数和16位长整数,这里有一些例子.

 64: 0011 1011 * 0100 0000 = [ 0000 1110 ] 1100 0000 (192)
128: 0011 1011 * 1000 0000 = [ 0001 1101 ] 1000 0000 (128)
192: 0011 1011 * 1100 0000 = [ 0010 1100 ] 0100 0000 (64)

通过仅丢弃结果的高位,当非素数被乘数的低位全为零时,得到的散列值的范围受到限制.这是否是特定上下文中的问题,特定于上下文.但是对于一般的散列函数,即使输入数字中存在模式,也应避免限制输出值的范围.在安全应用程序中,避免任何可能让某人根据输出中的模式推断原始值更为重要.只取低位就会显示一些原始位的确切值.如果我们假设操作涉及将输入数乘以一个大素数,那么我们就知道原始数字在右边有与哈希输出一样多的零(因为素数最右边的位是1).

通过使用低位对高位进行异或,输出的一致性较低.更重要的是,根据这些信息对输入值进行猜测要困难得多.根据XOR的工作原理,可能意味着原始低位为0,高位为1,或原始低位为1,高位为0.

 64: 0011 1011 * 0100 0000 = 0000 1110 1100 0000 => 1100 1110 (206)
128: 0011 1011 * 1000 0000 = 0001 1101 1000 0000 => 1001 1101 (157)
192: 0011 1011 * 1100 0000 = 0010 1100 0100 0000 => 0110 1100 (204)