在过去的几个小时里，我一直在阅读有关哈希码函数的文章，并积累了一些关于在自定义哈希码实现中使用素数作为乘数的问题。如果我能对以下问题有所了解，我将不胜感激：
-
在对@mattb的回答的评论中，@hstoer主张使用更大的素数(如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); }
如果prime是一个大数字，这不会导致返回的int溢出吗？
-
假设溢出不是问题(JVM执行自动强制转换)，那么执行位移而不是强制转换更好吗？
-
我想hashcode函数的性能会因hashcode的复杂性而有很大差异。素数乘数的大小不会影响性能吗？
-
在自定义哈希代码函数中使用多个素数而不是单个乘法器更好/更聪明/更快吗？如果没有，还有其他优势吗？请参阅以下来自@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)怎么样？这是我在这里的另一个问题上看到的，所以，但并没有真正解释为什么这样做是个好主意
提前为小说道歉。请随时提出建议或直接编辑--Chet
存在溢出，但没有异常。
危险不在于失去准确性，而在于失去射程。让我们使用一个荒谬的例子，其中"素数"是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位数字的哈希值范围(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，并且n的最低k位都是零，则乘积n * p的最低k位也将是全零。这很容易理解——如果你把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)
-
溢出不是问题。无论如何，哈希都被限制为一个狭窄的值集。
-
你发布的第一个散列函数不是很好。执行
return (prime * hash1) ^ hash2;`相反，在大多数情况下会减少碰撞次数。 -
与单个单词int相乘通常非常快，并且与不同数字相乘之间的差异可以忽略不计。此外，执行时间与任何时候中的其他功能相比都相形见绌
-
对每个部分使用不同的素数乘数可以降低碰撞的风险。