new HashMap(int) 和 guava Maps.newHashMapWithExpectedSize(int) 的区别

Question

15

在Java中，您可以像这样创建一个新的HashMap来保存特定数量的项：

Map m = new HashMap(100);

Guava 提供了一个 Maps.newHashMapWithExpectedSize(int) 方法，我本以为它只会调用 HashMap(int)。但实际上并非如此，它会计算自己的容量并使用。

为什么 newHashMapWithExpectedSize 会这样做，我该何时使用它而不是直接调用 new HashMap(int) 呢？

- thecoop

1

我的回答已经涵盖了这个问题，但是根本问题在于JDK API很糟糕，因为它不会像你期望的那样调整HashMap的大小以容纳特定数量的项。相反，它将其大小调整为指定数量的75％。 - ColinD

3个回答

3

HashMap构造函数的参数是map的容量，即桶的数量。

因此，如果将10作为参数传递，并在map中存储8个键，则会达到再散列阈值（默认为75％），并且map将重新散列。

另一方面，传递给newHashMapWithExpectedSize()的参数是map的预期大小。因此，如果传递了10，则Guava将创建一个具有足够桶的映射，以确保在插入10个元素时不会重新散列：至少14个桶。

- JB Nizet

2

HashMap 使用下一个二次幂作为其容量。因此，如果您将 initialCapacity 设置为 10，则实际容量将为 16。通过将其乘以 0.75，可以得到不调整大小的总共 12 个条目。 - Bubletan

1

@Bubletan：这是真的，但是A）这是API完全未指定的实现细节，B）这并不改变对于许多可能的initialCapacity值，表格将必须调整大小和重新散列以添加那么多条目的事实。 - ColinD

@ColinD同意，没有办法在不阅读代码的情况下从javadoc中知道实际的初始容量。在某些地方，它实际上是具有误导性的。 - Peter Tillemans

0

Guava只是将传递的大小乘以2（以安全的方式），然后调用常规哈希映射构造函数。这使它更稀疏，因此在哈希时发生冲突的次数更少。

容量计算的javadoc提到，它计算了一个容量值，使得哈希映射的填充率在25%到50%之间，远离触发重新调整大小的阈值。

标准库将预期大小四舍五入为最接近2的幂，并将其分配为大小，然后将重新调整大小的阈值设置为75%。如果我们随机请求大小，则标准库会在50%的情况下进行调整大小。

如果避免阈值是唯一的考虑因素，那么乘以1.34就足以有足够的空间来避免在填充预期元素大小时进行调整大小。

看起来这是典型的速度与空间权衡，Google工程师更注重速度，而Sun/Oracle工程师更注重空间。

- Peter Tillemans

1

不是的。如果你调用 new HashMap(n) 然后放入 n 个条目，哈希表会因为 JDK 的定义不够大而被重新调整大小；Guava 只是在补偿这一点。 - Louis Wasserman

是的，正如路易斯所说的那样，无论您使用哪种方法构建 Map，哈希表最终的大小都会差不多，因此不应该有任何显著的空间差异。唯一的区别在于在添加所有要添加的条目之前是否必须调整哈希表的大小。 - ColinD

是的，你说得对。它分配的大小会向上舍入到下一个2的幂，并设置正常的负载因子为75％，当填充它与大小项（如果大小足够接近向上舍入的数字，或约50％的情况下）时将触发。我曾错误地认为标准库会为此进行补偿。但数字2仍然相当任意，所以我仍然相信稀疏性在其中也起着作用。 - Peter Tillemans

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ColinD · Accepted Answer

你读过这个方法的Javadoc吗？

创建一个HashMap实例，初始容量足够大，可以在不扩容的情况下容纳expectedSize个元素。

请注意，new HashMap(int)构造函数的“初始大小”参数指定了存储条目的哈希表的初始大小，这基本上是您不必关心的实现细节。当哈希表超过地图的负载因子（默认为0.75）时，哈希表将调整大小，这意味着如果您指定了16的初始容量，然后向地图添加16个条目，则哈希表几乎肯定会被调整大小。

使用Guava的方法，如果您指定了16的预期大小，然后添加16个条目，则哈希表不应该调整大小。