我有一个非常直接的问题,但我无法弄清楚。问题是:
如果我们增加映射内数组的大小(即映射的容量),则会增加(put
和 get
方法的执行时间) ?
最佳答案
简短回答:不。
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);
}
关于java - HashMap 容量与时间权衡,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50291295/