<分区>
看了JDK的源码，觉得HashMap的hash()函数很好玩。它的源代码是这样的:
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
参数h 是来自Objects 的hashCode 被放入HashMap。这种方法是如何工作的，为什么？为什么这种方法可以防御较差的hashCode函数？
最佳答案
Hashtable 使用质数的“经典”方法:要获取值的“索引”，您需要对键进行哈希运算，然后对大小进行取模。以素数作为大小，(通常)在索引上给出一个很好的分布(当然也取决于散列)。
HashMap 使用“2 的幂”方法，这意味着大小是 2 的幂。原因是它应该比素数计算更快。然而，由于 2 的幂不是素数，因此会有更多的冲突，尤其是哈希值具有相同的低位时。
为什么？为获得(桶/槽)索引而对大小执行的模数只需通过以下公式计算:hash & (size-1)(这正是 HashMap 中用于获取索引的内容!)。这基本上是“二次方”方法的问题:如果长度有限，例如16，HashMap 的默认值，仅使用最后一位，因此具有相同低位的哈希值将产生相同的(桶)索引。在16的情况下，只有最后4位用于计算索引。
这就是为什么要计算一个额外的散列，基本上它会移动较高的位值，并使用较低的位值对其进行操作。数字 20、12、7 和 4 的原因，我真的不知道。它们曾经是不同的(在 Java 1.5 左右，散列函数几乎没有什么不同)。我想有更高级的文献可用。您可能会在各种与算法相关的文献中找到更多关于他们为什么使用他们使用的数字的信息，例如
http://en.wikipedia.org/wiki/The_Art_of_Computer_Programming
http://mitpress.mit.edu/books/introduction-algorithms
http://burtleburtle.net/bob/hash/evahash.html#lookup根据长度使用不同的算法(这是有道理的)。
http://www.javaspecialists.eu/archive/Issue054.html可能也很有趣。查看文章底部附近 Joshua Bloch 的 react :“替换二级哈希函数(我在计算机的帮助下开发的)具有强大的统计特性，几乎可以保证良好的桶分布。”)所以，如果你问我，这些数字来自 Josh 本人进行的某种分析，可能由谁知道谁协助。
因此:2 的幂提供了更快的计算速度，但需要进行额外的哈希计算才能很好地分布在槽/桶上。
关于java - 谁能解释一下 java 是如何设计 HashMap 的 hash() 函数的？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14453163/
相关文章：
c++ - std::hash 和/或 boost::hash 的目的是什么？
Java:通过匹配 LinkedHashMap 中的相似键来复制值
java - 在哪里定义服务器端jar的类路径？ manifest.mf与CLI参数-cp
java - 黑客排名 : Illegal static declaration in inner class Solution. 结果
windows - Shlwapi.dll中的HashData是基于什么哈希算法？
python - 使用预计算针对特定用例优化 Python 算法
java - Spark Hbase : How to convert a dataframe to Hbase org. apache.hadoop.hbase.client.Result