Введение в оптимизацию стратегии хеширования

обзор

Стратегия, используемая для хэширования ключей, может напрямую влиять на производительность хэшированных коллекций, таких как HashMap или HashSet.

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

Тестирование стратегии хеширования

В предыдущей статье я рассмотрел несколько способов тестирования стратегий хеширования и, в частности, рассмотрел стратегию хеширования, оптимизированную для «ортогональных битов», в которой проверялось, чтобы каждый результат хеширования был как можно более разным на основе только одного бита. меняется.

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

Минимизация столкновений

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

Мне просто нужны уникальные хэш-коды, не так ли?

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

Допустим, у вас есть набор ключей, и все они имеют уникальные 32-битные хэш-коды. Если у вас есть массив из 4 миллиардов сегментов, у каждого ключа будет свой сегмент, и коллизий не будет. Как правило, нежелательно иметь такие большие массивы для всех коллекций хэшей. На самом деле HashMap и HashSet ограничены наибольшей степенью 2, которую вы можете иметь для массива, равной 2 ^ 30 или чуть более одного миллиарда.

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

Давайте посмотрим на пример, ftse350.csv Если мы возьмем первый столбец в качестве ключа или элемента, мы получим 352 строки. Эти строки имеют уникальные String.hashCode (), но говорят, что мы берем младшие биты этого хеш-кода. Видим ли мы столкновения?

Размер HashMap для коэффициента загрузки 0,7 (по умолчанию) равен 512, который использует маску младших 9 бит. Как видите, около 30% ключей имеют коллизию, хотя мы начали с уникальных хеш-кодов.

• Код для HashTesterMain находится здесь.

Чтобы уменьшить влияние плохой стратегии хеширования, HashMap использует функцию перемешивания. В Java 8 это довольно просто.

Из источника для HashMap.hash Вы можете прочитать Javadoc для более подробной информации.

Это смешивает старшие биты хеш-кода с младшими битами, чтобы улучшить случайность младших битов. Для случая выше, где есть высокая частота столкновений, есть улучшение. Смотрите третий столбец.

Посмотрите на хэш-функцию для String

Код для String.hashCode ()

Примечание: реализация для String определена в Javadoc, поэтому у нас мало шансов изменить ее, но мы могли бы определить новую стратегию хеширования.

Компоненты стратегии хеширования.

В стратегии хеширования я рассматриваю две части.

• Магические числа. Вы можете попробовать разные цифры, чтобы найти лучший результат.
• Структура кода. Вы хотите структуру, в которой вы получите хороший результат для любого разумного выбора магического числа.

Хотя магические числа имеют значение, причина, по которой вы не хотите, чтобы они были слишком важны, заключается в том, что всегда существует вероятность того, что выбранный вами магический номер был неправильным для данного варианта использования. Вот почему вам также нужна структура кода, которая имеет худший результат в худшем случае даже для плохо выбранного магического числа.

Давайте попробуем несколько различных множителей вместо 31.

Вы можете видеть, что выбор магического числа имеет значение, но также есть много чисел, которые можно попробовать. Нам нужно написать тест, чтобы попробовать хороший случайный выбор. Источник для HashSearchMain

Код ключа, на который стоит посмотреть

Как вы можете видеть, повторное умножение каждого хэша и следующего символа является разумным, если вы предоставите хороший множитель или множитель, который хорошо работает с вашим набором ключей. Если вы сравните 130795 как множитель вместо 31, вы получите только 81 коллизию вместо 103 коллизий для протестированного набора ключей.

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

Но что произойдет, когда мы добавим новые ключи в коллекцию хэшей, будет ли наше магическое число по-прежнему полезным для нас? Вот где я смотрю на худшие частоты столкновений, чтобы определить, какая структура может дать хорошие результаты для более широкого диапазона возможных входных данных. Худший случай для hash () — 250 коллизий, то есть 70% коллизий ключей, что довольно плохо. Функция перемешивания немного улучшает это, однако она все еще не велика. Примечание: если мы добавим смещенное значение вместо того, чтобы записать его, мы получим худший результат в этом случае.

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

Что если мы добавим вместо хора в хеш-функцию?

В функции перемешивания использование xor было, возможно, лучше, чем использование add. Что произойдет, если мы изменим это

с участием

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

Почему мы выбрали нечетные множители?

Когда вы умножаете на нечетное число, младший бит результата имеет равную вероятность быть 0 или 1. Это потому, что 0 * 1 = 0 и 1 * 1 = 1. Однако, если вы умножаете на четное число, младший бит всегда равен 0. т. е. больше не является случайным. Скажем, мы повторяем предыдущий тест, но только с использованием четных чисел, как это выглядит?

Если вам повезло и у вас есть правильный ввод для вашего магического числа, результаты такие же хорошие, как и для нечетных чисел, однако, если вам не повезло, результаты могут быть довольно плохими. 325 столкновений означает, что используются только 27 из 512 ведер.

Чем отличаются более продвинутые стратегии хеширования?

Для стратегий хеширования мы используем на основе City, Murmur, XXHash и Vanilla Hash (наши собственные)

• Стратегия хеширования читает 64-битные за раз, что быстрее, чем чтение байтов за байтом.
• Расчетное рабочее значение — это два 64-битных значения.
• Рабочее значение уменьшается до 64-битной длины.
• В результате используются более множители.
• Функция агитации является более сложной.

Мы используем длинные хэш-коды в нашей реализации как;

• оптимизируем под 64-битные процессоры,
• самый длинный примитивный тип данных в Java — 64-битный, и
• Если у вас есть большие коллекции хешей (то есть миллионы), 32-битные хэши вряд ли будут уникальными.

В итоге

Изучая, как мы генерируем хеш-код, мы нашли способы уменьшить количество коллизий для 352 ключей с 103 до 68 коллизий, но также имеем некоторую уверенность в том, что при изменении набора ключей мы сократили влияние, которое это могло бы оказать ,

Это без использования большего объема памяти или даже большей вычислительной мощности.
У нас еще есть возможность использовать больше памяти.

Для сравнения вы можете увидеть, что удвоение размера массива может улучшить лучший случай, но у вас все еще есть проблема, что несоответствие между набором ключей и магическим числом все еще может иметь высокую частоту столкновений.

Вывод

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