为什么HashMap初始容量没有被库正确处理？ [英] Why HashMap initial capacity is not properly handled by the library?

问题描述

要为N个元素创建HashMap / HashSet，我们通常会执行 new HashMap（（int）（N / 0.75F）+1）这令人讨厌。

为什么库首先没有考虑到这一点，并允许初始化像 new HashMap（N） （不应该rehash到N个元素）照顾这个计算（int）（N / 0.75F）+1 ？

解决方案

更新

更新以反映已更改的问题。不，没有这样的标准API，但似乎有一种方法 Maps.newHashMapWithExpectedSize（int） 在 guava ：

创建一个 HashMap 实例，它具有足够高的初始容量，它应该保存 expectedSize 元素没有增长。

---

我必须初始化它to（int）（N / 0.75F）+1

不，你不知道。如果您从其他 Map 创建新的 HashMap ，则 HashMap 会计算首先默认情况下容量为：

  public HashMap（Map <？extends K，？extends V> m）{
 this （Math.max（（int）（m.size（）/ DEFAULT_LOAD_FACTOR）+ 1，
 DEFAULT_INITIAL_CAPACITY），DEFAULT_LOAD_FACTOR）; 
 putAllForCreate（m）; 
 
 $ / code> 

如果您逐个添加元素，也会发生相同的过程： / p>



  void addEntry（int hash，K key，V value，int bucketIndex）{
 if（（size> =阈值）&&（null！= table [bucketIndex]））{
 resize（2 * table.length）; 
 // ... 
} 
 
 createEntry（hash，key，value，bucketIndex）; 
 
 
 
 $ b 
使用 HashMap（int initialCapacity， float loadFactor）构造函数是从一开始就知道要存储在 HashMap 中的元素的数量，从而避免以后调整大小和重新哈希地图从一开始就有正确的大小）。
 
 
一个有趣的实现细节是初始容量被调整到最接近的两个幂（参见：）：
  //找到2的幂> = initialCapacity 
 int capacity = 1; 
 while（容量容量<= 1; 
  
因此，如果您希望您的 HashMap 具有确切的容量，只需使用两个幂。
 
 
 
选择不同的 loadFactor 较小的值意味着更多的内存，但更少的冲突。
 
To create HashMap/HashSet for N elements, we generally donew HashMap((int)(N/0.75F)+1) which is annoying.  

Why the library has not taken care of this in the first place and allows initialization like new HashMap(N)(should not rehash till N elements) taking care of this calculation (int)(N/0.75F)+1?
解决方案
Update

Updating to reflect changed question. No, there is no such standard API but it seems there is a method Maps.newHashMapWithExpectedSize(int) in guava:

  
Creates a HashMap instance, with a high enough "initial capacity" that it should hold expectedSize elements without growth.





  
i have to initialize it to (int)(N/0.75F)+1
No you don't. If you create new HashMap from other Map, HashMap calculates capacity first by default:
public HashMap(Map<? extends K, ? extends V> m) {
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                  DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    putAllForCreate(m);
}
If you add elements one by one, the same process happens as well:
void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        //...
    }

    createEntry(hash, key, value, bucketIndex);
}
The only reason to use HashMap(int initialCapacity, float loadFactor) constructor is when you know from the very beginning how many elements you want to store in the HashMap, thus avoiding resizing and rehashing later (map has correct size from the very beginning).

One interesting implementation detail is that initial capacity is trimmed to the nearest power of two (see: Why ArrayList grows at a rate of 1.5, but for Hashmap it's 2?):
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
    capacity <<= 1;
So if you want your HashMap to have exact capacity as defined, just use powers of two.

Choosing different loadFactor allows you to trade space for performance - smaller value means more memory, but less collisions.

                        
这篇关于为什么HashMap初始容量没有被库正确处理？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！