防止哈希表调整大小为当前大小的两倍。

Question

我们有一个大小为一百万的HashMap。我们需要存储一百万零一百个对象，但我们不希望HashMap因为只有100个对象而增加到两倍大小（200万）。

编辑： 我想优化HashMap的调整大小。因为仅存储100个对象就需要分配1百万个对象的大小，这是浪费内存的。

我们如何解决这个问题？

- Ram Dutt Shukla

---

可能是在索引列表时最佳HashMap初始容量的重复问题。 - Danielson

@Danielson，实际上，这个问题与那个问题无关。 - Dmitry Ginzburg

这与初始大小有关，以及何时更新其分配。我应该链接到已接受的答案而不是问题。 - Danielson

@nafas：我想要优化哈希表的调整大小。因为对于字符串，我们只需要分配1百万个对象的大小来存储100个对象。这样就浪费了很多内存。 - Ram Dutt Shukla

https://dev59.com/-2Uo5IYBdhLWcg3wrhHj#15844186 - Danielson

Answer 1

HashMap 的容量是2的幂次方，如果2^20（1048576）不够用，你需要使用2^21（2097152）。

编辑：

实际上，你可以通过指定较高的负载因子来控制容量。

如果确切的最大条目数为1000100，则当条目数达到容量 * 负载因子时，HashMap 的容量将加倍。因此，如果容量为1048576，并且你不想将其扩展到2097152，则需要使用约为0.954或更高的负载因子。

因此，使用以下构造函数初始化实例即可：

 HashMap<String,Integer> map = new HashMap<> (1048576, 0.954);

相关代码（JDK 6）：

public HashMap(int initialCapacity, float loadFactor) {
    ...
    // Find a power of 2 >= initialCapacity
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;

    this.loadFactor = loadFactor;
    threshold = (int)(capacity * loadFactor);
    table = new Entry[capacity];
    ...
}

并且

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) // this is what you want to avoid
        resize(2 * table.length);
}

- Eran

Answer 2

分割密钥并拥有。

Map<Key1, Map<Key2, Value>

使用TreeMap实现一个Map。如果第二个Map也是TreeMap，则可以进行最优填充，如果主要的Map是HashMap，可能具有高负载因子（第二个构造函数参数），那么也应该可以正常工作。此外，碰撞处理也更好。您可以创建自己的Map实现来包装它。

- Joop Eggen