Java: "простое" число или "сила двух" в качестве размера HashMap?

Ответ 1

Использование мощности двух эффективно маскирует верхние биты хэш-кода. Таким образом, хэш-функция некачественного качества может особенно сильно пострадать в этом сценарии.

Java HashMap смягчает это, не доверяя реализации объекта hashCode() и применяя второй уровень хэширования к его результату:

Применяет дополнительную хэш-функцию к заданному хэш-коду, который защищает от хеш-функций низкого качества. Это важно, потому что HashMap использует хэш-таблицы с длиной в две строки, которые в противном случае сталкиваются с конфликтами для хэш-кодов, которые не отличаются в младших битах.

Если у вас хорошая хэш-функция или что-то похожее на то, что делает HashMap, не имеет значения, используете ли вы простые числа и т.д., как размер таблицы.

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

Ответ 2

Стандартная реализация HashMap имеет метод hash, который повторяет хэш-код объекта, чтобы избежать этой ошибки. Комментарий перед метод hash() гласит:

/**
 * Retrieve object hash code and applies a supplemental hash function to the
 * result hash, which defends against poor quality hash functions.  This is
 * critical because HashMap uses power-of-two length hash tables, that
 * otherwise encounter collisions for hashCodes that do not differ
 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
 */

Ответ 3

Единственный способ узнать, что лучше между простым и сильным двумя, - это сравнить его.

Много лет назад, когда я писал ассемблер, чья производительность сильно зависела от поиска символа talbe, я тестировал это, используя большой блок сгенерированных идентификаторов. Даже с наивным отображением я обнаружил, что мощность двух, как и ожидалось, имела менее равномерное распределение и более длинные цепочки, чем простое количество кодов с одинаковым размером. Он по-прежнему работает быстрее, из-за скорости выбора ковша с помощью маскировки бит.

Я сильно подозреваю, что разработчики java.util не прибегли бы к дополнительному хэшированию и силе двух, не сравнивая его с использованием простого количества ведер. Это очень очевидная вещь, когда нужно создавать хешированную структуру данных.

По этой причине я уверен, что размер rehash и power-of-two дает лучшую производительность для типичных хэш-карт Java, чем простое количество ковшей.

Ответ 4

С точки зрения производительности/расчета времени измерения мощности двух размеров могут быть рассчитаны с помощью только маскировки бит, которая быстрее, чем целочисленное деление, которое в противном случае потребовалось бы.

Ответ 5

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