обзор
Хроника имеет ряд реализаций для хэширования, включая 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. Это может означать, что это лучше всего подходит для теста на ортогональные биты.