Почему XOR является стандартным способом объединения хэшей?
Скажем, у вас есть два хэша H(A) а также H(B) и вы хотите объединить их. Я читал, что хороший способ объединить два хэша XOR их, например XOR( H(A), H(B) ),
Лучшее объяснение, которое я нашел, кратко затронуто здесь по следующим рекомендациям:
XOR двух чисел с примерно случайным распределением приводит к другому числу, все еще с примерно случайным распределением *, но которое теперь зависит от двух значений.
...
* В каждом бите двух чисел для объединения выводится 0, если два бита равны, иначе - 1. Другими словами, в 50% комбинаций будет выводиться 1. Таким образом, если каждый из двух входных битов имеет примерно 50-50 шанс быть равным 0 или 1, то и выходной бит тоже будет.
Можете ли вы объяснить интуицию и / или математику, почему XOR должен быть операцией по умолчанию для объединения хеш-функций (а не ИЛИ или И т. Д.)?
8 ответов
При условии равномерно случайных (1-битных) входов распределение вероятности выхода функции AND составляет 75%. 0 и 25% 1, И наоборот, ИЛИ 25% 0 и 75% 1,
Функция XOR составляет 50% 0 и 50% 1следовательно, это хорошо для объединения равномерных распределений вероятностей.
Это можно увидеть написав таблицы истинности:
a | b | a AND b
---+---+--------
0 | 0 | 0
0 | 1 | 0
1 | 0 | 0
1 | 1 | 1
a | b | a OR b
---+---+--------
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 1
a | b | a XOR b
---+---+--------
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
Упражнение: сколько логических функций двух 1-битных входов a а также b есть это равномерное распределение выхода? Почему XOR наиболее подходит для цели, указанной в вашем вопросе?
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с и 1s - в частности, это инверсия золотого отношения (32-битная дробь с фиксированной точкой) с некоторым добавлением и xor. Это нарушает симметрию и вносит некоторый "шум", если входящие хэшированные значения плохие (т. Е. Представьте, что каждый компонент хеширует до 0 - вышеизложенный хорошо с этим справляется, генерируя мазок 1 а также 0с после каждого комбайна. Мой просто выводит 0).
Для тех, кто не знаком с C/C++, size_t это целое число без знака, которое достаточно велико, чтобы описать размер любого объекта в памяти. В 64-разрядной системе обычно это 64-разрядное целое число без знака. В 32-разрядной системе 32-разрядное целое число без знака.
Несмотря на удобные свойства смешивания битов, XOR не является хорошим способом объединения хэшей из-за своей коммутативности. Подумайте, что произойдет, если вы сохранили перестановки {1, 2, …, 10} в хэш-таблице из 10 кортежей.
Гораздо лучший выбор m * H(A) + H(B)где m большое нечетное число.
Кредит: вышеупомянутый объединитель был подсказкой от Боба Дженкинса.
Xor может быть способом по умолчанию для объединения хэшей, но ответ Грега Хьюгилла также показывает, почему у него есть свои подводные камни: xor двух идентичных значений хэша равен нулю. В реальной жизни идентичные хэши встречаются чаще, чем можно было ожидать. Затем вы можете обнаружить, что в этих (не очень редких) угловых случаях результирующие комбинированные хэши всегда одинаковы (ноль). Хеш-коллизии будут намного, намного чаще, чем вы ожидаете.
В надуманном примере вы можете комбинировать хешированные пароли пользователей с разных веб-сайтов, которыми вы управляете. К сожалению, большое количество пользователей повторно использует свои пароли, и удивительная доля получаемых хэшей равна нулю!
Есть кое-что, что я хочу явно указать для тех, кто находит эту страницу. И и ИЛИ ограничивают вывод, как BlueRaja - Дэнни Пфлугхо пытается указать, но может быть лучше определен:
Сначала я хочу определить две простые функции, которые я буду использовать для объяснения этого: Min() и Max ().
Min (A, B) вернет меньшее значение между A и B, например: Min(1, 5) возвращает 1.
Max (A, B) вернет значение, большее между A и B, например: Max(1, 5) возвращает 5.
Если вам дают: C = A AND B
Тогда вы можете найти, что C <= Min(A, B) Мы знаем это, потому что нет ничего, что вы можете И с 0 битами A или B сделать их 1 с. Таким образом, каждый нулевой бит остается нулевым, и каждый бит имеет шанс стать нулевым (и, следовательно, меньшим значением).
С: C = A OR B
Обратное верно: C >= Max(A, B) При этом мы видим следствие функции AND. Любой бит, который уже равен единице, не может быть преобразован в ноль, поэтому он остается равным единице, но каждый нулевой бит имеет шанс стать единицей и, следовательно, большим числом.
Это подразумевает, что состояние ввода накладывает ограничения на вывод. Если вы И что-нибудь с 90, вы знаете, что выход будет равен или меньше 90, независимо от того, что другое значение.
Для XOR нет подразумеваемых ограничений на основе входных данных. Есть особые случаи, когда вы можете обнаружить, что если вы XOR байта с 255, то вы получите обратный, но любой возможный байт может быть выведен из этого. Каждый бит имеет возможность изменить состояние в зависимости от того же бита в другом операнде.
Если ты XOR случайный вход с предвзятым входом, выход случайный. То же самое не верно для AND или же OR, Пример:
00101001 XOR 00000000 = 00101001 00101001 И 00000000 = 00000000 00101001 ИЛИ 11111111 = 11111111
Как упоминает @Greg Hewgill, даже если оба входа являются случайными, используя AND или же OR приведет к смещенному выводу.
Причина, по которой мы используем XOR что-то более сложное, ну, в этом нет необходимости: XOR работает отлично, и это чертовски быстро-быстро.
Покройте 2 левых столбца и попытайтесь выяснить, какие входные данные используют только выходные данные.
a | b | a AND b
---+---+--------
0 | 0 | 0
0 | 1 | 0
1 | 0 | 0
1 | 1 | 1
Когда вы увидели 1-битный, вы должны были понять, что оба входа были 1.
Теперь сделайте то же самое для XOR
a | b | a XOR b
---+---+--------
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
XOR ничего не дает по этому поводу.
XOR не игнорирует некоторые входные данные, такие как OR и AND.
Если вы возьмете , к примеру, AND(X, Y) и зададите для входа X значение false, тогда вход Y не имеет значения... и, возможно, вы захотите, чтобы значение ввода имело значение при объединении хэшей.
Если вы возьмете XOR(X, Y), тогда ОБА входы ВСЕГДА имеют значение. Там не будет никакого значения X, где Y не имеет значения. Если изменяется X или Y, то результат будет отражать это.
Исходный код для различных версий hashCode() в java.util.Arrays является отличным справочником для надежных алгоритмов хеширования общего назначения. Их легко понять и перевести на другие языки программирования.
Грубо говоря, большинство мульти-атрибут hashCode() реализации следуют этому шаблону:
public static int hashCode(Object a[]) {
if (a == null)
return 0;
int result = 1;
for (Object element : a)
result = 31 * result + (element == null ? 0 : element.hashCode());
return result;
}
Вы можете искать другие вопросы и ответы Stackru для получения дополнительной информации о магии позади 31и почему код Java использует его так часто. Он несовершенен, но имеет очень хорошие общие характеристики.