具有不同初始容量和负载因子的HashMap的性能

Question

这是我的情况.我使用两个java.util.HashMap将一些常用数据存储在Tomcat上运行的Java Web应用程序中.我知道每个Hashmap的确切条目数.键分别为字符串和整数.

我的问题是,设置初始容量和loadfactor的最佳方法是什么？

我应该将容量设置为等于它将具有的元素数量和负载容量为1.0吗？我想在不使用太多内存的情况下获得绝对最佳性能.但是,我担心桌子不能最佳填充.使用所需的确切大小的表,是否会发生键冲突,导致(通常是短暂的)扫描找到正确的元素？

假设(并且这是一个延伸)哈希函数是整数键的简单模5,这并不意味着键5,10,15将击中相同的桶然后导致搜索填充旁边的桶他们？更大的初始容量是否会提高性能？

此外,如果有一个比hashmap更好的数据结构,我对此也完全开放.

Answer 1

在没有完美的数据哈希函数的情况下,并假设这实际上不是真正无关紧要的微优化,我会尝试以下方法:

假设在大多数情况下HashMap使用的默认负载容量(.75)是一个很好的值.在这种情况下,您可以使用它,并根据您自己对将要保留的项目数量的知识设置HashMap的初始容量 - 将其设置为初始容量x .75 =项目数(向上舍入).

如果它是一个更大的地图,在高速查找非常关键的情况下,我会建议使用某种特里而不是哈希映射.对于长字符串,在大型映射中,通过使用更多面向字符串的数据结构(例如trie),可以节省空间,并且有一段时间.

Answer 2

假设你的哈希函数是"好的",最好的做法是将初始大小设置为预期的元素数量,假设你可以便宜地得到一个好的估计.这样做是个好主意,因为当HashMap调整大小时,必须重新计算表中每个键的哈希值.

将负载系数保留为0.75.根据0.75经验选择值作为哈希查找性能和主哈希数组的空间使用之间的良好折衷.当您将负载系数提高时,平均查找时间将显着增加.

如果你想深入研究哈希表行为的数学:Donald Knuth(1998).计算机程序设计的艺术.3:排序和搜索(第2版).Addison-Wesley出版社.第513-558页.国际标准书号0-201-89685-0.