许多书籍和教程都说哈希表的大小必须是素数才能将键均匀分布在所有桶中。但是Java的HashMap始终使用 2 的幂的大小。难道不应该使用素数吗？作为哈希表大小，“质数”或“2 的幂”哪个更好？
使用 2 的幂可以有效地屏蔽哈希码的最高位。因此，质量差的哈希函数在这种情况下可能表现得特别糟糕。
Java's HashMap通过不信任对象的hashCode()实施和对其结果应用第二级散列 http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashMap.java#256:
将补充哈希函数应用于给定的 hashCode，以防止质量较差的哈希函数。这一点很关键，因为 HashMap 使用二次方长度的哈希表，否则会遇到低位相同的 hashCode 的冲突。
如果你有一个好的哈希函数，或者做类似的事情HashMap确实如此，是否使用素数等作为表大小并不重要。
另一方面，如果哈希函数未知或质量较差，那么使用素数将是更安全的选择。然而，它会使动态大小的表实现起来更加困难，因为突然间您需要能够生成素数，而不是仅仅将大小乘以常数因子。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
