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

Я просматривал исходный код 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;

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

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

Ответ 1

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

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

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

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

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

Ответ 2

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

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