不同初始容量和负载因子的hashmap性能

如果您的数据没有一个完美的哈希函数,并且假设这实际上不是一个真正无关紧要的微观优化,我将尝试以下方法:

假设hashmap使用的默认负载能力(.75)在大多数情况下都是一个很好的值。在这种情况下,您可以使用它,并根据您自己对它将容纳多少个项目的了解来设置哈希图的初始容量-将其设置为初始容量x.75=项目数(四舍五入)。

如果是更大的地图,在高速查找非常关键的情况下,我建议使用某种 trie 而不是散列图。对于长字符串,在大型映射中,您可以使用更面向字符串的数据结构(如trie)来节省空间和一些时间。

假设散列函数是“好的”,那么最好的做法是将初始大小设置为预期的元素数,假设您可以以较低的成本获得一个好的估计值。这样做是一个好主意,因为当哈希映射调整大小时,它必须重新计算表中每个键的哈希值。

将负载系数保持在 0.75 .价值 零点七五 已根据经验选择作为哈希查找性能和主哈希数组的空间使用之间的良好折衷。当您向上推负载系数时,平均查找时间将显著增加。

如果你想深入研究哈希表行为的数学:DonaldKnuth(1998)。计算机程序设计艺术。3:分类和检索(第2版)。艾迪生·韦斯利。第513558页。国际标准书号0-201-89685-0。

我发现最好不要摆弄默认设置,除非我真的需要这样做。

Hotspot为您做了大量优化工作。

在任何情况下,我都会首先使用分析器(比如netbeans分析器)来测量问题。

我们通常存储包含10000个元素的映射,如果您有一个好的equals和hashcode实现(字符串和整数就是这样!)这比您可能进行的任何加载更改都要好。

假设(这是一个扩展),哈希函数是整数键的简单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的幂。

条目以类似随机的方式分配给bucket。因此,即使您的bucket和条目一样多,一些bucket也会发生冲突。

如果你有更多的桶,碰撞会更少。然而,更多的桶意味着在内存中展开,因此速度较慢。一般来说,在0.7-0.8范围内的负荷系数是大致最优的,因此可能不值得改变。

像以前一样,在你挂断微调优这些东西之前,它可能是值得分析的。