在重写hashCode（）时使用较大的素数作为乘数
我已经阅读了过去几个小时的哈希码函数，并且在自定义哈希码实现中使用素数作为乘数已经积累了一些问题。 如果我能对以下问题有所了解，我将不胜感激：
-
在@ 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); }
如果prime是一个大数字，这不会导致返回的int溢出？
-
假设溢出不是问题（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);类的东西怎么样long lhash = prime * (hash1 ^ hash2);然后用(int)((lhash >> 32) ^ lhash)？ 这是我在另一个问题上看到的东西，但是并没有真正解释为什么这样做是个好主意。
为小说提前道歉。 随意提出建议或直接编辑。 –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) ，产品中最不重要的位置都会有七个零。 因此，如果(hash1 ^ hash2)是奇数（最低有效位= 1），则乘以128的结果将始终为128（在截断较高位数之后）。 如果(hash1 ^ hash2)是偶数（LSB为0，则产品将始终为零）。
这扩展到更大的位大小。 一般的观点是，如果“ prime ”的低位为零，则表示您正在进行移位（或多次移位+求和）操作，这将使您在低位中为零。 并且乘法乘积的范围将受到影响。
但是让我们尝试将“ prime ”设为奇数，以便最低有效位始终为1.考虑将其分解为移位/添加操作。 (hash1 ^ hash2)的未移位值将始终是其中一个加数。 现在，至少根据原始(hash1 ^ hash2)值的位来设置被偶数“ prime ”乘数转换为保证无用的最低有效位。
现在，让我们考虑一个实际为素数的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);类的东西怎么样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通常非常快，并且乘以不同数字之间的差异可以忽略不计。 此外，执行时间与函数中的其他所有内容相比相形见绌
-
为每个部分使用不同的素数乘数可以降低碰撞的风险。