Что происходит при достижении максимальной емкости HashMap или HashSet? - PullRequest
Новая
       29

Что происходит при достижении максимальной емкости HashMap или HashSet?

18 голосов
/ 20 декабря 2011

Всего несколько минут назад я ответил на вопрос о " Максимально возможном размере HashMap в Java ".Как я всегда читал, HashMap - это растущая структура данных.Его размер ограничен только объемом памяти JVM. Поэтому я подумал, что для его размера нет жесткого ограничения, и ответил соответственно.(То же самое применимо и к HashSet.)

Но кто-то исправил меня, сказав, что, поскольку метод HashMap size () возвращает int , там это ограничение на его размер.Совершенно правильная точка зрения.Я только что попытался проверить его на своем локальном компьютере, но не смог, мне нужно больше 8 ГБ памяти, чтобы вставить в HashMap более 2 147 483 647 целых чисел, которых у меня нет.

Мои вопросы были:

  • Что происходит, когда мы пытаемся вставить 2 147 483 647 + 1 элемент в HashMap / HashSet?
  • Есть ли ошибка?
  • Если да, то какая ошибка?Если нет, что происходит с HashMap / HashSet, его уже существующими элементами и новым элементом?

Если кто-то наделен доступом к машине с 16 ГБ памяти, вы можете попробовать ее на практике.:)

1 Ответ

18 голосов
/ 20 декабря 2011

Базовая емкость массива должна быть степенью 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);
}
...