索引列表时的最佳 HashMap 初始容量

Question

我有一个列表（ 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);
}

原文由 Italo Borssatto 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

如果您希望避免重新 HashMap ，并且您知道不会将其他元素放入 HashMap ，那么您必须考虑负载因子和初始容量. a HashMap 的加载因子默认为 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);
}

原文由 rgettman 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

根据定义，“capacity”关键字是不正确的，并且未按通常预期的方式使用。

默认情况下，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);

原文由 Jack Hopner 发布，翻译遵循 CC BY-SA 3.0 许可协议