java - HashMap 容量与时间权衡

Question

我有一个非常直接的问题，但我无法弄清楚。问题是:

如果我们增加映射内数组的大小(即映射的容量)，则会增加(put 和 get 方法的执行时间) ？

Answer 1

简短回答:不。

Look the documentation ，唯一可以影响 put 和 get 时间的是 hashCode 实现。

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.

当您有 Hash Collision 时，就会产生影响。当两个不同对象具有相同的哈希代码时，就会发生这种情况。

<小时/>

HashMap会根据hashCode计算位置，如果你设置一个很小的initialCapacity和一个很大的loadFactor，就会发生哈希冲突，所以会创建某些职位的列表。这意味着 get 将遍历崩溃元素的列表，而不是所有列表。

假设您有一个包含 M 个元素的 N 个位置的数组。最坏的情况是O(max(1, M/N))。所以N应该大于M。

如果你看HashMap implementation ，如果大小变得太大(总容量的 75%)，它会调用调整大小操作。所以初始容量并不是最终容量，容量会随着 map 的增长而变大。

初始容量的唯一问题是在需要之前存储内存。这可能会导致内存泄漏!

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}