Почему XOR используется по умолчанию для объединения хэшей?

Скажем, у вас есть два хэша H(A) и H(B), и вы хотите их объединить. Я читал, что хороший способ объединить два хэша - это XOR их, например. XOR( H(A), H(B) ).

Самое лучшее объяснение, которое я нашел, кратко описано здесь в этих хеш-функциях:

XORing двух чисел с грубо случайным распределением приводит к еще одному числу, все еще с грубо случайным распределением *, но которое теперь зависит от двух значений.
...
* На каждом бите двух чисел, которые нужно комбинировать, выводится 0, если два бита равны, иначе a 1. Другими словами, в 50% комбинаций будет выводиться 1. Поэтому, если два входных бита имеют примерно 50-50 вероятность быть 0 или 1, то так же будет и выходной бит.

Можете ли вы объяснить интуицию и/или математику за тем, почему XOR должно быть операцией по умолчанию для объединения хеш-функций (а не OR или AND и т.д.)?

Ответ 1

Принимая равномерно случайные (1-битные) входы, распределение вероятности выхода функции И составляет 75% 0 и 25% 1. И наоборот, OR составляет 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 наиболее подходит для цели, указанной в вашем вопросе?

Ответ 2

xor - опасная функция по умолчанию, используемая при хешировании. Это лучше, чем and и or, но это не говорит о многом.

xor является симметричным, поэтому порядок элементов теряется. Таким образом, "bad" будет объединять хэш так же, как и "dab".

xor отображает попарно одинаковые значения в ноль, и вам следует избегать отображения "общих" значений в ноль:

Таким образом, (a,a) отображается на 0, а (b,b) также отображается на 0. Поскольку такие пары почти всегда встречаются чаще, чем можно предположить по случайности, вы в конечном итоге сталкиваетесь с большим количеством столкновений в нуле, чем следует.

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

На современном оборудовании добавление обычно происходит примерно так же быстро, как xor (вероятно, он использует больше энергии для этого). Добавление таблицы истинности аналогично xor для рассматриваемого бита, но оно также отправляет бит до следующего бита, когда оба значения равны 1. Это означает, что оно стирает меньше информации.

Таким образом, hash(a) + hash(b) лучше, чем hash(a) xor hash(b), в том случае, если a==b, результатом будет hash(a)<<1 вместо 0.

Это остается симметричным; поэтому "bad" и "dab" получают одинаковый результат, остается проблемой. Мы можем нарушить эту симметрию за скромную цену:

hash(a)<<1 + hash(a) + hash(b)

ака hash(a)*3 + hash(b). (вычисление hash(a) один раз и сохранение рекомендуется, если вы используете сменное решение). Любая нечетная константа вместо 3 будет биективно отображать беззнаковое целое число "k -bit" на себя, поскольку отображение целых чисел без знака является математическим по модулю 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 после каждого объединения. My Наивный 3*hash(a)+hash(b) просто выводит 0 в этом случае).

(Для тех, кто не знаком с C/C++, size_t - это целое число без знака, которое достаточно велико, чтобы описать размер любого объекта в памяти. В 64-битной системе это обычно 64-битное целое число без знака. В 32-разрядной системе - 32-разрядное целое число без знака.)

Ответ 3

Несмотря на удобные свойства битового смешивания, XOR не является хорошим способом комбинирования хешей из-за его коммутативности. Подумайте, что произойдет, если вы сохранили перестановки {1, 2,..., 10} в хеш-таблице из 10 кортежей.

Гораздо лучший выбор - m * H(A) + H(B), где m - большое нечетное число.

Кредит: вышеупомянутый объединитель был чаевым от Боба Дженкинса.

Ответ 4

Xor может быть "стандартным" способом комбинирования хэшей, но ответ Грега Хьюглилла также показывает, почему у него есть свои подводные камни: Xor двух одинаковых хэш-значений равен нулю. В реальной жизни одинаковые хэши более распространены, чем можно было ожидать. Затем вы можете обнаружить, что в этих (не очень редких) угловых случаях результирующие комбинированные хэши всегда одинаковы (ноль). Конфликты Хэша были бы намного, гораздо более частыми, чем вы ожидаете.

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

Ответ 5

Там что-то я хочу явно указать другим, кто находит эту страницу. AND и OR ограничивают вывод, например BlueRaja - Danny Pflughoe пытается указать, но его можно определить лучше:

Сначала я хочу определить две простые функции, которые я буду использовать, чтобы объяснить это: 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, чтобы сделать их 1s. Таким образом, каждый нулевой бит остается равным нулю, и каждый бит имеет шанс стать нулевым битом (и, следовательно, меньшим значением).

С: C = A OR B

Противоположно верно: C >= Max(A, B) При этом мы видим следствие функции И. Любой бит, который уже является одним, не может быть ORed равным нулю, поэтому он остается одним, но каждый нулевой бит имеет шанс стать одним и, следовательно, большим числом.

Это означает, что в состоянии ввода применяются ограничения на выход. Если вы И что-нибудь с 90, вы знаете, что выход будет равен или меньше 90 независимо от того, что другое значение.

Для XOR нет ограничений на основе входных данных. Существуют особые случаи, когда вы можете обнаружить, что если вы XOR байт с 255, чем вы получите обратный, но любой возможный байт может быть выведен из этого. Каждый бит имеет шанс изменить состояние в зависимости от того же бита в другом операнде.

Ответ 6

Если вы XOR случайный ввод с предвзятым входом, выход является случайным. То же самое не относится к AND или OR. Пример:

00101001 XOR 00000000 = 00101001
00101001 AND 00000000 = 00000000
00101001 OR  11111111 = 11111111

Как отмечает @Greg Hewgill, даже если оба входа являются случайными, использование AND или OR приведет к смещенному выходу.

Причина, по которой мы используем XOR над чем-то более сложным, заключается в том, что нет нужды: XOR работает отлично, и это невероятно глупо-быстро.

Ответ 7

Покройте левые 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 ничего не дает об этом входы.

Ответ 8

Исходный код для различных версий 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;
}

Вы можете искать другие файлы StackOverflow Q & для получения дополнительной информации о магии за 31 и почему Java-код использует ее так часто. Он несовершенен, но имеет очень хорошие общие характеристики.

Ответ 9

XOR не игнорирует некоторые входные данные, такие как OR и AND.

Если вы возьмете , к примеру, AND (X, Y) и зададите для входа X значение false, тогда вход Y не имеет значения... и, возможно, вы захотите, чтобы значение ввода имело значение при объединении хэшей.

Если вы возьмете XOR (X, Y), тогда ОБА входы ВСЕГДА имеют значение. Там не будет никакого значения X, где Y не имеет значения. Если изменяется X или Y, то результат будет отражать это.