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

Question

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

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

//The default initial capacity - MUST be a power of two.

static final int DEFAULT_INITIAL_CAPACITY = 16;

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

int capacity = 1;

while (capacity < initialCapacity)

  capacity <<= 1;

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

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

674 2

java hash hashmap hashtable

2 ответов:

Comments

Ничего не найдено.

Jon Skeet · Accepted Answer · 2011-12-02 08:10:38

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

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

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

M Platvoet · Accepted Answer · 2011-12-02 09:55:30

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

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