Почему XOR является стандартным способом объединения хэшей?

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

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

XOR двух чисел с примерно случайным распределением приводит к другому числу, все еще с примерно случайным распределением *, но которое теперь зависит от двух значений.
...
* В каждом бите двух объединяемых чисел выводится 0, если два бита равны, иначе - 1. Другими словами, в 50% комбинаций выводится 1. Таким образом, если каждый из двух входных битов имеет примерно 50-50 шанс быть равным 0 или 1, то и выходной бит тоже будет.

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

Принимая во внимание равномерно случайные (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опасная функция по умолчанию для использования при хешировании Это лучше чем 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-битное" целое число без знака для себя, так как отображение на целые числа без знака является математическим по модулю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с константой (которая в основном случайная 0s и 1s - в частности, это обратное значение золотого сечения как 32-битной дроби с фиксированной запятой) с некоторым добавлением и xor. Это нарушает симметрию и вводит некоторый «шум», если входящие хэшированные значения плохие (т.е. представьте, что каждый компонент хеширует до 0 - вышеупомянутый обрабатывает это хорошо, генерируя мазок 1и 0s после каждого объединения. Мой наивный 3*hash(a)+hash(b)просто выводит a0 in тот случай).

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

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

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

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

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 битами А или В сделать их 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 ничего не дает по этому поводу.

Исходный код для различных версий 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 для получения дополнительной информации о магии, стоящей за ней 31, и о том , почему Java-код использует ее так часто. Он несовершенен, но имеет очень хорошие общие характеристики.

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

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

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