31

我有一个列表 ( List<T> list)，我想使用映射 ( HashMap<Integer, T> map) 通过它们的 id 来索引它的对象。我总是在构造函数中list.size()用作初始容量HashMap，如下面的代码所示。这是在这种情况下使用的最佳初始容量吗？

注意：我永远不会在地图上添加更多项目。

List<T> list = myList;
Map<Integer, T> map = new HashMap<Integer, T>(list.size());
for(T item : list) {
    map.put(item.getId(), item);
}
4

6 回答 6

27

如果您希望避免重新散列HashMap，并且您知道不会将其他元素放入 中HashMap，那么您必须考虑负载因子以及初始容量。aHashMap默认的负载因子为 0.75 。

put每当添加新条目（例如放置新键/值）时，都会进行确定是否需要重新散列的计算。因此，如果您指定初始容量为list.size()，负载因子为 1，那么它将在最后一个 之后重新散列put。因此，为防止重新散列，请使用负载因子 1 和容量list.size() + 1.

编辑

查看HashMap源代码，如果旧大小达到或超过阈值，它将重新散列，因此不会在最后一个重新散列put。所以看起来容量list.size()应该没问题。

HashMap<Integer, T> map = new HashMap<Integer, T>(list.size(), 1.0);

这是相关的HashMap源代码：

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}
于 2013-04-05T21:50:02.220 回答
20

“容量”关键字在定义上是不正确的，并且没有以通常预期的方式使用。

默认情况下，HashMap 的“负载因子”为 0.75，这意味着当 HashMap 中的条目数达到所提供容量的 75% 时，它将调整数组大小并重新散列。

例如，如果我这样做：

Map<Integer, Integer> map = new HashMap<>(100);

当我添加第 75 个条目时，映射会将条目表的大小调整为 2 * map.size()（或 2 * table.length）。所以我们可以做几件事：

  1. 更改负载因子 - 这可能会影响地图的性能
  2. 将初始容量设置为 list.size() / 0.75 + 1

最好的选择是两者中的后者，让我解释一下这里发生了什么：

list.size() / 0.75

这将返回 list.size() + list.size() 的 25%，例如，如果我的列表大小为 100，它将返回 133。然后，如果地图的大小为等于初始容量的 75%，所以如果我们有一个大小为 100 的列表，我们会将初始容量设置为 134，这意味着从列表中添加所有 100 个条目不会导致地图的任何大小调整。

最终结果：

Map<Integer, Integer> map = new HashMap<>(list.size() / 0.75 + 1);
于 2015-02-25T00:03:07.867 回答
15

GuavaMaps.newHashMapWithExpectedSize使用这个辅助方法来计算默认负载因子的初始容量0.75，基于一些预期的值数量：

/**
 * Returns a capacity that is sufficient to keep the map from being resized as
 * long as it grows no larger than expectedSize and the load factor is >= its
 * default (0.75).
 */
static int capacity(int expectedSize) {
    if (expectedSize < 3) {
        checkArgument(expectedSize >= 0);
        return expectedSize + 1;
    }
    if (expectedSize < Ints.MAX_POWER_OF_TWO) {
        return expectedSize + expectedSize / 3;
    }
    return Integer.MAX_VALUE; // any large value
}

参考：来源

从newHashMapWithExpectedSize文档中：

创建一个HashMap具有足够高的“初始容量”的实例，它应该可以容纳expectedSize没有增长的元素。这种行为不能得到广泛的保证，但对于 OpenJDK 1.6 来说确实如此。也不能保证该方法不会无意中过大返回的地图。

于 2013-04-05T21:46:14.713 回答
13

你在做什么很好。通过这种方式，您可以确定哈希映射至少有足够的容量用于初始值。如果您有更多关于哈希映射使用模式的信息（例如：它是否经常更新？是否经常添加许多新元素？），您可能希望设置更大的初始容量（例如，list.size() * 2），但永远不要降低。使用分析器确定初始容量是否过快不足。

更新

感谢@PaulBellora 建议将初始容量设置为(int)Math.ceil(list.size() / loadFactor)（通常，默认负载因子为 0.75）以避免初始调整大小。

于 2013-04-05T21:41:46.163 回答
4

根据java.util.HashMap 的参考文档：

在设置其初始容量时，应考虑映射中的预期条目数及其负载因子，以尽量减少重新哈希操作的次数。如果初始容量大于最大条目数除以负载因子，则不会发生重新哈希操作。

这意味着，如果您提前知道 HashMap 应该存储多少条目，则可以通过选择适当的初始容量和负载因子来防止重新散列。然而：

作为一般规则，默认负载因子 (.75) 在时间和空间成本之间提供了良好的折衷。较高的值会减少空间开销，但会增加查找成本（反映在 HashMap 类的大多数操作中，包括 get 和 put）。

于 2013-04-05T21:49:24.763 回答
1

如果您不知道负载系数/容量内部结构，则经验法则：

initialCapacityToUse = (Expected No. of elements in map / 0.75) + 1

使用这个初始容量值，存储给定的预期数量不会发生重新哈希。地图中的元素集。

于 2019-04-19T13:17:43.763 回答