Dlaczego XOR jest domyślnym sposobem łączenia skrótów?

Powiedzmy, że masz dwa skróty H(A)i H(B)chcesz je połączyć. Czytałem, że dobrym sposobem na połączenie dwóch skrótów jest do XORnich np XOR( H(A), H(B) ).

Najlepsze wyjaśnienie, jakie znalazłem, zostało pokrótce omówione tutaj w tych wytycznych dotyczących funkcji skrótu :

XORowanie dwóch liczb z mniej więcej losowym rozkładem daje w wyniku kolejną liczbę, która nadal ma mniej więcej losowy rozkład *, ale która teraz zależy od tych dwóch wartości.
...
* Na każdym bicie z dwóch liczb do połączenia wyprowadzane jest 0, jeśli dwa bity są równe, w przeciwnym razie 1. Innymi słowy, w 50% kombinacji zostanie wyprowadzone 1. Więc jeśli każdy z dwóch bitów wejściowych ma z grubsza 50-50 szans na 0 lub 1, to tak samo będzie z bitem wyjściowym.

Czy możesz wyjaśnić intuicję i / lub matematykę, dlaczego XOR powinien być domyślną operacją łączenia funkcji skrótu (zamiast OR lub AND itp.)?

Zakładając jednolicie losowe (1-bitowe) dane wejściowe, rozkład prawdopodobieństwa wyjścia funkcji AND wynosi 75% 0i 25% 1. I odwrotnie, OR wynosi 25% 0i 75% 1.

Funkcja XOR wynosi 50% 0i 50% 1, dlatego dobrze jest łączyć jednolite rozkłady prawdopodobieństwa.

Można to zobaczyć, wypisując tabele prawdy:

 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

Ćwiczenie: Ile funkcji logicznych ma dwa 1-bitowe wejścia ai bma taki jednolity rozkład wyjściowy? Dlaczego XOR jest najbardziej odpowiedni do celu określonego w pytaniu?

xorjest niebezpieczną funkcją domyślną do użycia podczas mieszania. Jest lepszy niż andi or, ale to niewiele mówi.

xorjest symetryczny, więc kolejność elementów zostaje utracona. Więc "bad"hash będzie łączyć to samo co "dab".

xor odwzorowuje parami identyczne wartości na zero i należy unikać mapowania „wspólnych” wartości na zero:

Jest więc (a,a)mapowane na 0, a (b,b)także na 0. Ponieważ takie pary są prawie zawsze bardziej powszechne, niż może to sugerować przypadkowość, kończy się z dużą liczbą kolizji na poziomie zerowym, niż powinieneś.

Z tymi dwoma problemami xorkończy się sumatorem mieszania, który wygląda na w połowie przyzwoicie, ale nie po dalszej kontroli.

Na nowoczesnym sprzęcie, dodawanie zwykle tak szybko, jak xor(trzeba przyznać, że prawdopodobnie zużywa więcej energii, aby to zrobić). Dodawanie tabeli prawdy jest podobne do tego xorna danym bicie, ale wysyła również trochę do następnego bitu, gdy obie wartości są równe 1. Oznacza to, że usuwa mniej informacji.

Więc hash(a) + hash(b)jest lepsze niż hash(a) xor hash(b)w przypadku a==b, gdy wynikiem jest hash(a)<<1zamiast 0.

To pozostaje symetryczne; więc "bad"i "dab"otrzymuję ten sam rezultat pozostaje problemem. Możemy złamać tę symetrię niewielkim kosztem:

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

aka hash(a)*3 + hash(b). ( hash(a)zaleca się jednorazowe obliczenie i przechowywanie, jeśli używasz rozwiązania zmianowego). Każda nieparzysta stała zamiast 3będzie bijektywnie odwzorowywać " k-bit" liczbę całkowitą bez znaku na siebie, ponieważ mapowanie na liczbach całkowitych bez znaku jest 2^kdla niektórych matematyczne modulo k, a każda nieparzysta stała jest względnie pierwsza 2^k.

Aby uzyskać jeszcze bardziej wyszukaną wersję, możemy sprawdzić boost::hash_combine, co jest efektywne:

size_t hash_combine( size_t lhs, size_t rhs ) {
  lhs ^= rhs + 0x9e3779b9 + (lhs << 6) + (lhs >> 2);
  return lhs;
}

tutaj dodajemy razem kilka przesuniętych wersji seedze stałą (która jest w zasadzie losowym 0s i 1s - w szczególności jest to odwrotność złotego podziału jako 32-bitowy ułamek z punktem stałym) z dodatkiem i xor. To łamie symetrię i wprowadza pewien „szum”, jeśli przychodzące wartości skrótu są słabe (tj. Wyobraź sobie, że każdy komponent hashuje do 0 - powyższe działa dobrze, generując rozmazanie 1i 0s po każdym połączeniu. Mój naiwny 3*hash(a)+hash(b)po prostu wyświetla 0in ta walizka).

(Dla tych, którzy nie znają języka C / C ++, a size_tjest liczbą całkowitą bez znaku, która jest wystarczająco duża, aby opisać rozmiar dowolnego obiektu w pamięci. W systemie 64-bitowym jest to zwykle 64-bitowa liczba całkowita bez znaku. W systemie 32-bitowym , 32-bitowa liczba całkowita bez znaku).

Pomimo swoich poręcznych właściwości mieszania bitów, XOR nie jest dobrym sposobem łączenia hashów ze względu na swoją przemienność. Zastanów się, co by się stało, gdybyś zapisał permutacje {1, 2,…, 10} w tablicy z 10 krotkami.

Dużo lepszym wyborem jest to m * H(A) + H(B), gdzie m to duża liczba nieparzysta.

Kredyt: Powyższy sumator był wskazówką od Boba Jenkinsa.

Xor może być "domyślnym" sposobem łączenia hashów, ale odpowiedź Grega Hewgilla pokazuje również, dlaczego ma swoje pułapki: xor dwóch identycznych wartości hash wynosi zero. W prawdziwym życiu identyczne skróty są częstsze, niż można by się spodziewać. Może się wtedy okazać, że w tych (nie tak rzadkich) przypadkach narożnych wynikowe połączone skróty są zawsze takie same (zero). Zderzenia z haszowaniem byłyby dużo, dużo częstsze niż się spodziewasz.

W wymyślonym przykładzie możesz łączyć zaszyfrowane hasła użytkowników z różnych zarządzanych witryn internetowych. Niestety, wielu użytkowników ponownie używa swoich haseł, a zaskakująca część powstałych skrótów wynosi zero!

Jest coś, co chciałbym wyraźnie wskazać innym osobom, które znajdą tę stronę. AND i OR ograniczają wydajność, jak BlueRaja - Danny Pflughoe próbuje wskazać, ale można to lepiej zdefiniować:

Najpierw chcę zdefiniować dwie proste funkcje, których użyję do wyjaśnienia tego: Min () i Max ().

Min (A, B) zwróci wartość, która jest mniejsza między A i B, na przykład: Min (1, 5) zwraca 1.

Max (A, B) zwróci większą wartość między A i B, na przykład: Max (1, 5) zwraca 5.

Jeśli otrzymasz: C = A AND B

Wtedy możesz stwierdzić, że C <= Min(A, B)wiemy o tym, ponieważ nie ma nic, co możesz ORAZ z 0 bitami A lub B, aby uzyskać jedynki. Zatem każdy bit zerowy pozostaje bitem zerowym, a każdy bit ma szansę stać się bitem zerowym (a tym samym mniejszą wartością).

Z: C = A OR B

Jest odwrotnie: w C >= Max(A, B)tym przypadku widzimy następstwo funkcji AND. Żaden bit, który jest już jedynką, nie może zostać zmieniony na zero, więc pozostaje jedynką, ale każdy bit zerowy ma szansę stać się jedynką, a tym samym większą liczbą.

Oznacza to, że stan wejścia nakłada ograniczenia na wyjście. Jeśli ORAZ coś z 90, wiesz, że wynik będzie równy lub mniejszy niż 90, niezależnie od tego, jaka jest inna wartość.

W przypadku XOR nie ma dorozumianych ograniczeń opartych na danych wejściowych. Istnieją specjalne przypadki, w których możesz stwierdzić, że jeśli XOR bajt z wartością 255, otrzymasz odwrotność, ale każdy możliwy bajt może zostać z tego wyprowadzony. Każdy bit ma szansę na zmianę stanu w zależności od tego samego bitu w innym operandzie.

Jeśli masz XORlosowe wejście z polaryzowanym wejściem, wyjście jest losowe. To samo nie dotyczy ANDlub OR. Przykład:

00101001 XOR 00000000 = 00101001
00101001 I 00000000 = 00000000
00101001 LUB 11111111 = 11111111

Jak wspomina @Greg Hewgill, nawet jeśli oba wejścia są losowe, użycie ANDlub ORspowoduje odchylenie wyjścia.

Powodem, dla którego używamy XORczegoś bardziej złożonego, jest to, że nie ma potrzeby: XORdziała idealnie i jest niesamowicie głupio-szybkie.

Zakryj dwie lewe kolumny i spróbuj ustalić, jakie dane wejściowe wykorzystują tylko dane wyjściowe.

 a | b | a AND b
---+---+--------
 0 | 0 |    0
 0 | 1 |    0
 1 | 0 |    0
 1 | 1 |    1

Kiedy zobaczyłeś 1-bit, powinieneś był się domyślić, że oba wejścia mają wartość 1.

Teraz zrób to samo dla XOR

 a | b | a XOR b
---+---+--------
 0 | 0 |    0
 0 | 1 |    1
 1 | 0 |    1
 1 | 1 |    0

XOR nie zdradza nic na temat danych wejściowych.

Kod źródłowy różnych wersji hashCode()w java.util.Arrays to świetne odniesienie do solidnych, ogólnych algorytmów haszujących. Są łatwo zrozumiałe i przetłumaczone na inne języki programowania.

Z grubsza rzecz biorąc, większość hashCode()implementacji z wieloma atrybutami jest zgodna z tym wzorcem:

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;
}

Możesz przeszukać inne pytania i odpowiedzi StackOverflow, aby uzyskać więcej informacji o magii 31i dlaczego kod Java używa go tak często. Jest niedoskonały, ale ma bardzo dobre ogólne właściwości użytkowe.

XOR nie ignoruje niektórych danych wejściowych, czasem takich jak OR i AND .

Jeśli weźmiesz na przykład AND (X, Y) i wprowadzisz do wejścia X fałsz, to wejście Y nie ma znaczenia ... i prawdopodobnie chciałoby się, aby dane wejściowe miały znaczenie podczas łączenia hashów.

Zażycie XOR (X, Y), a następnie OBU wejść ZAWSZE sprawa. Nie byłoby wartości X, gdzie Y nie ma znaczenia. Jeśli zmieni się X lub Y, dane wyjściowe to odzwierciedlą.