Статьи

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

обзор

Хроника имеет ряд реализаций для хэширования, включая City и Murmur. У этого также есть свой собственный Хэш Ванили, но как это было проверено?

Что такое ванильный хэш?

Vanilla Hash спроектирован так, чтобы быть максимально простым и оптимизированным для теста на ортогональные биты (см. Ниже). Он сравнивался со стратегиями хеширования в City 1.1 и Murmur 3.

Это задержки в 99-м процентиле для заполнения 64-байтового / 256-байтового буфера новыми данными и генерации 64-битного хэша. JMH был использован для выполнения измерений. См.  Main64bytes  и  Main256bytes

Стратегия хеширования 64-байтовая 99% плитка 256 байт 99% плитки
ваниль 67 нс 112 нс
Город 1.1 90 нс 182 нс
Мурмур 3 104 нс 211 нс

Полный тест  результатов здесь.

Какие тесты вы можете сделать, чтобы проверить правильность стратегии хеширования?

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

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

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

В каждом тесте с использованием входных данных 8 192 бита или 1024 КБ переключается один бит за раз. Из этих входов генерируется 8 192 х 64-битных хэшей.

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

Маска хэша

В этом тесте каждый хэш имеет модуль 16,384 (удвоенное количество хэшей), и сообщается о количестве коллизий. Большинство стратегий хеширования хорошо для этого теста.

Лавина счет

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

Скорость в латентности

В этом тесте записывается время, необходимое для выполнения хэша, и сообщается худшая задержка в 1%.

Ортогональные биты

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

В этом тесте каждый хеш сравнивается с любым другим. Подсчитывается количество битов, которые отличаются. Если количество разных битов меньше 18, это дает штрафной балл 2 ^ (17-n). Чем меньше битов, тем больше штраф по экспоненциальной шкале. Если какой-либо из 8K-хэшей, сопоставленных с другими 8K-хэшами, отличается менее чем на 5 битов, это сбой, даже если все остальные пары в порядке.

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

Из всех тестов этот показывает наибольшую разницу между String.hashCode () с HashMap.hash (int) и другими стратегиями хеширования.

Тестирование String.hashCode ()

String.hashCode () — очень плохой хэш, особенно для  младших  битов. Это стандарт и не может быть изменено или нарушить обратную совместимость. Однако это не должно быть проблемой, так как HashMap использует функцию агитации, которая сбрасывает некоторые старшие биты, чтобы рандомизировать младшие биты.

int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

Полученные результаты

Класс  CheckMain  запускает набор тестов для каждой стратегии хеширования.

VANILLA Ортогональные биты: 99% оценки плитки: 6066 Скорость: 99% плитки для задержки составляли 0,223 мкс. Лавина: 99% плитки дрейфа из 50% составляли 0,55% Маска хэша: 99% столкновений плитки: 1815

CITY_1_1 Ортогональные биты: 99% оценки тайла: 7395 Скорость: 99% тайла для задержки составляли 0,267 мкс. Лавина: 99% тайла дрейфа из 50% составляли 0,55% Маска хэша: 99% столкновений тайла: 1817

MURMUR_3 Ортогональные биты: 99% оценки плитки: 7524 Скорость: 99% плитки для задержки составляли 0,378 мкс. Лавина: 99% плитки дрейфа из 50% составляли 0,54% Маска хэша: 99% столкновений плитки: 1815

STRING32 Ортогональные биты: 99% оценки плитки:  295906433 Скорость: 99% плитки для задержки составляли  1,580 миль.  Лавина: 99% плитки дрейфа из 50% составляли  1,02% Маска хэша: 99% столкновений плитки: 1814

STRING64 Ортогональные биты: 99% оценки плитки:  1939167 Скорость: 99% плитки для задержки составляли  1,520  мкс. Лавина: 99% плитки дрейфа из 50% составляли 0,61% Маска хэша: 99% столкновений плитки: 1816

STRING32_WITHOUT_AGITATE Ортогональные биты: оценка тайла 99%:  879390386 Скорость: 99% тайла за задержку составили  1.573 миль.  Лавина: 99% тайла дрейфа из 50% составили  3.53% Маска хэша: 99% столкновений тайлов:  6593

СЛУЧАЙНЫЕ Ортогональные биты: 99% оценки плитки: 7444 Скорость: 99% плитки для задержки составили  0,058 миль.  Лавина: 99% плитки дрейфа от 50% были 0,53% Маска хэша: 99% столкновений плитки: 1817

SECURE_RANDOM Ортогональные биты: 99% оценки плитки: 7449 Скорость: 99% плитки для задержки составляли  0,861 миль.  Лавина: 99% плитки дрейфа из 50% составляли 0,54% Маска хэша: 99% столкновений плитки: 1816

SEEDED_VANILLA

Ортогональные биты: 99% плитки: 6000

Скорость: 99% тайла за задержку составили 0,219 мкс.

Лавина: 99% плитки дрейфа с 50% были 0,55%

Маска Хэша: 99% столкновений плитки: 1814

SEEDED_CITY_1_1

Ортогональные биты: 99% плитки: 7313

Скорость: 99% тайла за задержку составили 0,270 мкс

Лавина: 99% плитки дрейфа с 50% были 0,54%

Маска Хэша: 99% столкновений плитки: 1813

SEEDED_MURMUR_3

Ортогональные биты: 99% плитки: 7404

Скорость: 99% тайла для задержки составляли 0,359 мкс.

Лавина: 99% плитки дрейфа с 50% были 0,53%

Маска Хэша: 99% столкновений плитки: 1810

Примечание: Сеянный ванильный хэш является частью  Chronicle Enterprise

Выводы

Хэши Vanilla, City и Murmur были самыми быстрыми.  

Хотя String.hashCode () прост, операция умножения на символьную основу обходится дорого. Для сравнения, все остальные обрабатывают 8 байтов за раз, используя long. См. STRINGS32_WITHOUT_AGITATE по сравнению со STRING32. HashMap использует позже.

32-битный String hashCode () даже с агитой плохо показал себя в тесте Лавина. В SMHasher, где этот тест приходит с оценкой более 1%, считался неудачей.

Тесты Mask of Hash, хотя и просты, во всех случаях, похоже, хорошо выполняются. Исключением является String.hashCode (), который, как уже упоминалось, не имеет очень случайных младших битов.

Что мне показалось интересным, так это то, насколько отличались результаты теста на ортогональность. Первые три стратегии хэша были снова последовательно низкими. Даже 64-битная версия String.hashCode () имеет большие изменения при создании хэшей с разницей менее чем в 18 бит, фактически многие биты одинаковы.

отказ

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