13

在过去的几个小时里，我一直在阅读有关哈希码函数的内容，并且积累了一些关于在自定义哈希码实现中使用素数作为乘数的问题。如果我能对以下问题有所了解，我将不胜感激：

  • 在此处对@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)？这是我在另一个问题上看到的，但是并没有真正解释为什么这样做是个好主意。
4

2 回答 2

9

提前为小说道歉。随意提出建议或直接编辑。--切特

有溢出，但也不例外。

危险不是来自失去准确性，而是失去范围。让我们用一个荒谬的例子，其中“素数”是 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，那么我们知道它很奇怪。所以较低的位没有被转移到无用状态。通过选择一个足够大的素数，与使用较小的素数相比，您可以在输出值范围内获得更好的分布。

0010 0000 1111 1011尝试一些使用 8443 ( ) 和 59 ( )的 16 位乘法练习0000 0000 0011 1011。它们都是素数，59 的低位匹配 65531 的低位。例如，如果 hash1 和 hash2 都是 ASCII 字符值 (0 .. 255)，那么 (hash1 ^ hash2) * 59 将 <= 15045。这意味着 16 位数字的散列值范围 (0..65535) 的大约 1/4 未使用。

但是到处(hash1 ^ hash2) * 8443都是。(hash1 ^ hash2)如果低至 8，它就会溢出。即使对于非常小的输入数字，它也会使用所有 16 位。即使输入数字在相对较小的范围内，整个范围内的散列值聚类也少得多。

假设溢出不是问题（JVM 进行自动转换）是不是更好地进行位移而不是转换？

很可能不是。无论如何，JVM 都应该转化为主机处理器上的高效实现。整数乘法应该在硬件中实现。如果没有，JVM 负责将操作转换为对 CPU 来说合理的操作。整数乘法的情况很可能已经高度优化。如果整数乘法在给定的 CPU 上以移位加法的方式更快地完成，那么 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)

通过仅删除结果的高位，当非素数被乘数的低位全为零时，结果哈希值的范围受到限制。这是否是特定上下文中的问题是特定于上下文的。但是对于一般的散列函数，最好避免限制输出值的范围，即使输入数字中有模式也是如此。在安全应用程序中，避免任何会让人根据输出中的模式推断原始值的事情更为关键。仅取低位就可以揭示一些原始位的确切值。如果我们假设该操作涉及将输入数字与大素数相乘，那么我们知道原始数字在右侧的零与散列输出一样多（因为素数'

通过对高位与低位进行异或运算，输出的一致性会降低。更重要的是，根据这些信息猜测输入值要困难得多。根据 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)
于 2012-08-22T18:44:18.100 回答
4

  • 溢出不是问题。无论如何，哈希都被限制在一个狭窄的值集上。

  • 您发布的第一个哈希函数不是很好。在大多数情况下，使用`return (prime * hash1) ^ hash2; 会减少碰撞次数。

  • 乘以单个单词 int 一般是非常快的，乘以不同的数字之间的差异可以忽略不计。加上执行时间与函数anyay中的其他所有内容相比相形见绌

  • 对每个部分使用不同的素数乘数可以降低碰撞的风险。

于 2012-08-22T15:55:46.383 回答