Почему 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), который компенсирует слабые хэш-коды.
