达到HashMap或HashSet最大容量时会发生什么？

Question

几分钟后,我回答了一个问题,询问" Java中HashMap的最大可能大小 ".正如我一直读到的,HashMap是一个可扩展的数据结构.它的大小仅受JVM内存大小的限制.因此,我认为它的大小没有硬性限制并相应地回答.(同样适用于HashSet.)

但有人纠正我说,既然大小() HashMap中的方法返回一个INT,还有就是它的大小有限制.一个完全正确的观点.我只是尝试在我的本地测试它但失败了,我需要超过8GB的内存来在HashMap中插入超过2,147,483,647个整数,我没有.

我的问题是:

• 当我们尝试在HashMap/HashSet中插入2,147,483,647 + 1个元素时会发生什么？
• 是否抛出错误？
• 如果是,哪个错误？如果不是HashMap/HashSet会发生什么,它已经存在的元素和新元素？

如果某人有幸拥有16GB内存的机器,那么你可以尝试一下.:)

Answer 1

阵列的底层容量必须是2的幂(限制为2 ^ 30).当达到此大小时,有效地忽略负载因子并且阵列停止增长.

此时,碰撞率增加.

鉴于hashCode()只有32位,在任何情况下都不会增长太大.

/**
 * Rehashes the contents of this map into a new array with a
 * larger capacity.  This method is called automatically when the
 * number of keys in this map reaches its threshold.
 *
 * If current capacity is MAXIMUM_CAPACITY, this method does not
 * resize the map, but sets threshold to Integer.MAX_VALUE.
 * This has the effect of preventing future calls.
 *
 * @param newCapacity the new capacity, MUST be a power of two;
 *        must be greater than current capacity unless current
 *        capacity is MAXIMUM_CAPACITY (in which case value
 *        is irrelevant).
 */
void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

当大小超过Integer.MAX_VALUE时,它会溢出.

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);
}