具有不同初始容量和负载因子的HashMap的性能
这是我的情况。 我使用两个java.util.HashMap将一些常用数据存储在Tomcat上运行的Java Web应用程序中。 我知道每个Hashmap的确切条目数。 键分别为字符串和整数。
我的问题是，设置初始容量和loadfactor的最佳方法是什么？
我应该将容量设置为等于它将具有的元素数量和负载容量为1.0吗？ 我想在不使用太多内存的情况下获得绝对最佳性能。 但是，我担心桌子不能最佳填充。 使用所需的确切大小的表，是否会发生键碰撞，导致（通常是短暂的）扫描找到正确的元素？
假设（并且这是一个延伸）哈希函数是整数键的简单mod 5，这并不意味着键5,10,15将击中相同的桶然后导致搜索填充旁边的桶他们？ 更大的初始容量会提高性能吗？
此外，如果有一个比hashmap更好的数据结构，我对此也完全开放。
如果您的数据没有完美的散列函数，并且假设这实际上不是真正无关紧要的微观优化，我会尝试以下方法：
假设在大多数情况下HashMap使用的默认负载容量（.75）是一个很好的值。 在这种情况下，您可以使用它，并根据您自己对将要保留的项目数量的知识设置HashMap的初始容量 – 将其设置为初始容量x .75 =项目数（向上舍入）。
如果它是一个更大的地图，在高速查找非常关键的情况下，我会建议使用某种特里而不是哈希映射。 对于长字符串，在大型映射中，通过使用更多面向字符串的数据结构（例如trie），可以节省空间，并且有时间。
假设你的哈希函数是“好的”，最好的做法是将初始大小设置为预期的元素数，假设你可以便宜地得到一个好的估计。 这样做是个好主意，因为当HashMapresize时，必须重新计算表中每个键的哈希值。
将负载系数保持在0.75 。 根据经验选择0.75的值作为哈希查找性能和主哈希数组的空间使用之间的良好折衷。 当您向上推动负载系数时，平均查找时间将显着增加。
如果你想深入研究哈希表行为的数学：Donald Knuth（1998）。 计算机程序设计的艺术。 3：排序和搜索（第2版）。 Addison-Wesley出版社。 第513-558页。 国际标准书号0-201-89685-0。
除非我真的需要，否则我发现最好不要乱用默认设置。
Hotspot非常适合为您进行优化。
在任何情况下; 我会使用分析器（Say Netbeans Profiler）来首先测量问题。
我们经常存储10000个元素的映射，如果你有一个好的equals和hashcode实现（和字符串和整数做！），这将比你可能做的任何负载变化更好。
假设（这是一个延伸）哈希函数是整数键的简单模5
不是。 来自HashMap.java：
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); }
我甚至不会假装我明白这一点，但它看起来像是为了处理这种情况。
另请注意，无论您要求的大小，桶的数量也始终为2的幂。
条目以类似随机的方式分配给存储桶。 因此，即使您有多个桶作为条目，一些桶也会发生冲突。
如果你有更多的桶，你会有更少的碰撞。 但是，更多的桶意味着在内存中扩散，因此更慢。 通常，0.7-0.8范围内的负载系数大致是最佳的，因此可能不值得改变。
与以往一样，在你对这些东西进行微调之前，它可能值得进行分析。