Почему HashMap требует, чтобы начальная емкость была степенью двойки? - PullRequest
Новая
       12

Почему HashMap требует, чтобы начальная емкость была степенью двойки?

35 голосов
/ 02 декабря 2011

Я просматривал исходный код Java HashMap, когда увидел следующее 

//The default initial capacity - MUST be a power of two.
static final int DEFAULT_INITIAL_CAPACITY = 16;

Мой вопрос: почему это требование существует в первую очередь? Я также вижу, что конструктор, который позволяет создавать HashMap с пользовательской емкостью, преобразует его в степень двух: 

int capacity = 1;
while (capacity < initialCapacity)
  capacity <<= 1;

Почему емкость всегда должна быть степенью двойки?

Кроме того, когда происходит автоматическая перефразировка, что именно происходит? Хеш-функция тоже изменена?

Ответы [ 2 ]

43 голосов
/ 02 декабря 2011

Карта должна определить, какой индекс внутренней таблицы использовать для любого заданного ключа, сопоставляя любое значение int (может быть отрицательным) со значением в диапазоне [0, table.length).Когда table.length является степенью двойки, это можно сделать действительно дешево - и в indexFor: 

static int indexFor(int h, int length) {
    return h & (length-1);
}

При другой длине таблицы вам потребуетсявычислить остаток и убедиться, что он не отрицательный.Это определенно микрооптимизация, но, вероятно, действительная:)

Кроме того, когда происходит автоматическая перефразировка, что именно происходит?Хэш-функция тоже изменилась?

Мне не совсем понятно, что вы имеете в виду.Используются те же хеш-коды (потому что они просто вычисляются путем вызова hashCode для каждого ключа), но они будут по-разному распределены в таблице из-за изменения длины таблицы.Например, когда длина таблицы равна 16, хеш-коды 5 и 21 в итоге сохраняются в записи таблицы 5. Когда длина таблицы увеличивается до 32, они будут в разных записях.

4 голосов
/ 02 декабря 2011

Идеальная ситуация на самом деле заключается в использовании простых чисел для резервного массива HashMap. Таким образом, ваши ключи будут более естественно распределены по массиву. Однако это работает с разделением модов, и эта операция становилась все медленнее и медленнее с каждым выпуском Java. В некотором смысле, подход степени 2 - наихудший размер таблицы, который вы можете себе представить, потому что при плохих реализациях хеш-кода с большей вероятностью произойдет коллоидация ключей в массиве.

Для этого вы найдете еще один очень важный метод в реализации HashMap Java, который является hash(int), который компенсирует плохие хэш-коды.

...