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

обзор

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

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

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

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

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

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

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

В каждом случае выполняется несколько тестов с разными случайными начальными точками. Оценка берется за 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);
}