22

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

我的问题是，设置初始容量和负载因子的最佳方法是什么？

我是否应该将容量设置为等于它将拥有的元素数量并将负载容量设置为 1.0？我希望在不使用太多内存的情况下获得绝对最佳的性能。但是，我担心该表不会以最佳方式填充。使用所需的确切大小的表，是否不会发生键冲突，导致（通常很短）扫描以找到正确的元素？

假设（这是一个延伸）散列函数是整数键的简单 mod 5，这是否意味着键 5、10、15 会命中同一个桶，然后导致寻找填充旁边的桶他们？更大的初始容量会提高性能吗？

此外，如果有比哈希图更好的数据结构，我也完全愿意接受。

4

5 回答 5

13

在您的数据没有完美的散列函数的情况下，并假设这真的不是对真正无关紧要的事情的微优化，我会尝试以下方法：

假设 HashMap 使用的默认负载容量 (.75) 在大多数情况下是一个不错的值。在这种情况下，您可以使用它，并根据您自己对它将容纳多少项目的了解来设置 HashMap 的初始容量 - 将其设置为初始容量 x .75 = 项目数（向上取整）。

如果它是一个更大的映射，在高速查找非常关键的情况下，我建议使用某种trie而不是哈希映射。对于长字符串，在大型地图中，您可以通过使用更面向字符串的数据结构（例如 trie）来节省空间和时间。

于 2009-08-24T19:28:24.790 回答
5

假设你的散列函数是“好”的，最好的办法是将初始大小设置为预期的元素数量，假设你可以廉价地得到一个好的估计。这样做是个好主意，因为当 HashMap 调整大小时，它必须重新计算表中每个键的哈希值。

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

如果您想深入研究哈希表行为的数学：Donald Knuth (1998)。计算机编程的艺术”。3：排序和搜索（第 2 版）。艾迪生-韦斯利。第 513-558 页。国际标准书号 0-201-89685-0。

于 2009-08-24T23:45:10.513 回答
3

我发现最好不要摆弄默认设置，除非我真的需要。

Hotspot 在为您进行优化方面做得很好。

任何状况之下; 我会先使用分析器（比如 Netbeans Profiler）来衡量问题。

我们通常会存储包含 10000 个元素的映射，如果你有一个好的 equals 和 hashcode 实现（字符串和整数都可以！）这将比你可能做出的任何加载更改要好。

于 2009-08-24T22:01:01.237 回答
2

假设（这是一个延伸）哈希函数是整数键的简单 mod 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 的幂。

于 2009-08-24T20:51:22.580 回答
1

条目以类似随机的方式分配给存储桶。因此，即使您的存储桶与条目一样多，一些存储桶也会发生冲突。

如果你有更多的桶，你就会有更少的碰撞。然而，更多的桶意味着在内存中分散，因此速度更慢。通常，0.7-0.8 范围内的负载因子大致是最佳的，因此可能不值得更改。

与以往一样，在您对这些东西进行微调之前，可能值得进行分析。

于 2009-08-24T19:28:24.387 回答