xor - опасная функция по умолчанию, используемая при хешировании.Это лучше чем и и или или, но это не говорит о многом.
xor является симметричным, поэтому порядок элементов теряется.Таким образом, "bad" будет хешировать то же самое, что и "dab".
xor отображает идентичные значения в ноль, и вам следует избегать отображения "общих" значений в ноль:
Так что (a,a) получаетсопоставляется с 0, а (b,b) также сопоставляется с 0. Поскольку такие пары встречаются чаще, чем можно предположить по случайности, вы в конечном итоге столкнетесь с большим количеством столкновений в нуле, чем следует.
С этими двумя проблемами,xor в конечном итоге становится хеш-сумматором, который выглядит наполовину прилично на поверхности, но не после дальнейшего осмотра.
На современном оборудовании добавление обычно происходит примерно так же быстро, как и xor (вероятно, он использует больше энергии для этого, по общему признанию)).Таблица истинности добавления похожа на xor для рассматриваемого бита, но она также отправляет бит на следующий бит, когда оба значения равны 1. Это стирает меньше информации.
Так что hash(a) + hash(b) лучше, еслиa==b, результат вместо hash(a)<<1 вместо 0.
Это остается симметричным.Мы можем нарушить эту симметрию за скромные затраты:
hash(a)<<1 + hash(a) + hash(b)
или hash(a)*3 + hash(b).(вычисление hash(a) один раз и сохранение рекомендуется, если вы используете сменное решение).Любая нечетная константа вместо 3 будет биективно отображать size_t (или k-битную беззнаковую константу) на себя, поскольку отображение на беззнаковые константы является математическим по модулю 2^k для некоторых k, а любая нечетная константа является относительно простойна 2^k.
Для еще более причудливой версии мы можем рассмотреть boost::hash_combine, то есть:
size_t hash_combine( size_t lhs, size_t rhs ) {
lhs^= rhs + 0x9e3779b9 + (lhs << 6) + (lhs >> 2);
return lhs;
}
здесь мы складываем несколько сдвинутых версий seed сконстанта (которая в основном случайная 0 с и 1 с - в частности, это инверсия золотого отношения как 32-битной дроби с фиксированной запятой) с некоторым добавлением и xor.Это нарушает симметрию и вносит некоторый «шум», если входящие значения хэширования являются плохими (т.е. представьте, что каждый компонент хеширует до 0 - вышеизложенный обрабатывает это хорошо, генерируя мазок 1 и 0 с после каждого объединения.Моя просто выводит 0).
Для тех, кто не знаком с C / C ++, size_t - это целочисленное значение без знака, которое достаточно велико, чтобы описать размер любого объекта в памяти.В 64-разрядной системе обычно это 64-разрядное целое число без знака.В 32-разрядной системе 32-разрядное целое число без знака.