索引列表时的最佳哈希映射初始容量

algorithm dictionary hashmap java

2022-09-01 10:16:05

我有一个列表（），我想使用map（）按其ID索引其对象。我总是在构造函数中使用初始容量，就像下面的代码一样。在这种情况下，这是要使用的最佳初始容量吗？List<T> listHashMap<Integer, T> maplist.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);
}

答案 1

如果您希望避免重述，并且您知道不会将其他元素放入中，则必须考虑负载因子以及初始容量。哈希映射的负载因子默认为 0.75。HashMapHashMap

每当添加新条目时，都会进行用于确定是否需要重新哈希的计算，例如放置一个新的键/值。因此，如果将初始容量指定为，并且负载因子为 1，则它将在最后一个之后重新哈希。因此，为了防止重新哈希，请使用负载因子 1 和容量。putlist.size()putlist.size() + 1

编辑

查看源代码，如果旧大小达到或超过阈值，它将重新哈希，因此它不会在最后一个 .所以看起来一个容量应该没问题。HashMapputlist.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);
}

答案 2

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

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

例如，如果我这样做：

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

当我添加第75个条目时，地图会将条目表的大小调整为2 * map.size（）（或2 * table.length）。所以我们可以做一些事情：

更改载波系数 - 这可能会影响地图的性能
将初始容量设置为 list.size（） / 0.75 + 1

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

list.size() / 0.75

这将返回list.size（） + list.size（）的25%，例如，如果我的列表的大小为100，它将返回133。然后，如果映射的大小等于初始容量的 75%，则向其添加 1，因为映射的大小将调整为 1，因此，如果我们的列表大小为 100，我们将初始容量设置为 134，这意味着从列表中添加所有 100 个条目不会对映射进行任何调整大小。

最终结果：

Map<Integer, Integer> map = new HashMap<>(list.size() / 0.75 + 1);