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

Xor jest niebezpieczną domyślną funkcją używaną podczas hashowania. Jest lepsze niż and I or, ale to niewiele mówi.

Xor jest symetryczny, więc kolejność elementów jest tracona. Tak więc "bad" połączy hash tak samo jak "dab".

XOR odwzorowuje identyczne wartości do zera, i należy unikać mapowania "wspólnych" wartości do zera:

Więc (a,a) zostanie zmapowana do 0, a (b,b) również zostanie zmapowana do 0. Ponieważ takie pary są bardziej powszechne niż może sugerować przypadkowość, kończysz z daleko do wiele kolizji na zero, niż powinieneś.

Z tymi dwoma problemami, XOR staje się kombinatorem haszyszu, który wygląda w połowie przyzwoicie na powierzchni, ale nie po dalszej kontroli.

Na nowoczesnym sprzęcie, dodawanie zwykle tak szybkie jak xor(prawdopodobnie zużywa więcej mocy, aby to zrobić, co prawda). Tabela prawdy dodawania jest podobna do xor dla danego bitu, ale wysyła również bit do następnego bitu, gdy obie wartości są równe 1. To usuwa mniej informacji.

Więc {[6] } jest lepsze w tym, że jeśli a==b, wynik jest zamiast hash(a)<<1 zamiast 0.

To pozostaje symetryczne. Możemy złamać tę symetrię za skromną cenę: {]}

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

Aka hash(a)*3 + hash(b). (w przypadku użycia rozwiązania shift zaleca się jednorazową kalkulację hash(a) i przechowywanie). Każda stała nieparzysta zamiast 3 będzie bijektywnie mapować size_t (lub K-bitową niepodpisaną stałą) do siebie, ponieważ mapa na niepodpisanych stałych to math modulo 2^k dla niektórych k, a każda stała nieparzysta jest względnie pierwsza do 2^k.

Dla jeszcze bardziej fantazyjnej wersji możemy zbadać boost::hash_combine, czyli efektywnie:

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

Tutaj dodajemy kilka przesuniętych wersji seed ze stałą (która jest w zasadzie losowa 0s I 1s-w szczególności jest to odwrotność złotego współczynnika jako 32-bitowego ułamka punktu stałego) z pewnym dodatkiem i xor. To łamie symetrię i wprowadza pewien "szum", jeśli przychodzące wartości haszowane są słabe (tj. wyobraź sobie, że każdy komponent hashuje do 0 -- powyżej obsługuje go dobrze, generując rozmaz 1 i 0s po każdym połączeniu. Mine po prostu wyprowadza 0).

Dla osób nie znających C/C++, size_t jest 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 niepodpisana liczba całkowita. W systemie 32-bitowym, 32-bitowa niepodpisana liczba całkowita.

Pomimo swoich przydatnych właściwości mieszania bitów, XOR nie jest dobrym sposobem łączenia hashów ze względu na jego komutatywność. Zastanów się, co by się stało, gdybyś przechowywał permutacje {1, 2,..., 10} w tabeli skrótów składającej się z 10 krotek.

Znacznie lepszym wyborem jest m * H(A) + H(B), gdzie m jest dużą liczbą nieparzystą.

Kredyt: powyższy kombiner był napiwkiem 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 skrótu wynosi zero. W prawdziwym życiu istnieją identyczne skróty, które są bardziej powszechne, niż można się było spodziewać. Może się wtedy okazać, że w tych (nie tak rzadkich) narożnych przypadkach, wynikowe połączone skróty są zawsze takie same (zero). Kolizje haszyszu byłyby znacznie częstsze niż się spodziewasz.

W wymyślonym przykładzie możesz być łączenie zaszyfrowanych haseł użytkowników z różnych stron internetowych, którymi zarządzasz. Niestety, duża liczba użytkowników ponownie używa swoich haseł, a zaskakująca proporcja wynikowych hashów wynosi zero!

Jest coś, co chcę wyraźnie podkreślić dla innych, którzy znajdą tę stronę. And and or restrict output like BlueRaja - Danny Pflughoe próbuje wskazać, ale może być lepiej zdefiniowane:

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

Min (A, B) zwróci wartość mniejszą od A i B, na przykład: Min(1, 5) zwraca 1.

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

Jeśli podano: C = A AND B

Wtedy można stwierdzić, że C <= Min(A, B) wiemy to, ponieważ nie ma nic, co można i z 0 bitów A lub B zrobić je 1s. więc każdy bit zero pozostaje bitem zero i każdy jeden bit ma szansę stać się bitem zero (a tym samym mniejszą wartością).

Z: C = A OR B

Jest odwrotnie: C >= Max(A, B) z tym widzimy następstwo funkcji AND. Każdy bit, który jest już jedynką, nie może być ani zerem, 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 ty i cokolwiek z 90, wiesz, że wyjście będzie równe lub mniejsze niż 90, niezależnie od tego, jaka jest druga wartość.

Dla XOR, nie ma domniemanych ograniczeń opartych na wejściach. Istnieją specjalne przypadki, w których można stwierdzić, że jeśli XOR bajt z 255, to otrzymasz odwrotność, ale każdy możliwy bajt może być wyprowadzony z tego. Każdy bit ma szansę zmienić stan w zależności od tego samego bitu w drugim operandie.

Jeśli XOR losowe wejście z tendencyjnym wejściem, wyjście jest losowe. To samo nie dotyczy AND ani OR. Przykład:

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

Jak wspomina @ Greg Hewgill, nawet jeśli oba wejścia są losowe, użycie AND lub OR spowoduje stronnicze wyjście.

Powodem, dla którego używamy XOR nad czymś bardziej złożonym jest to, że, cóż, nie ma potrzeby: XOR działa idealnie i jest niesamowicie głupi-szybki.

Kod źródłowy dla różnych wersji hashCode() w java.util.Arrays {[6] } jest doskonałym punktem odniesienia dla solidnych algorytmów hashujących ogólnego zastosowania. Są łatwo zrozumiałe i przetłumaczone na inne języki programowania.

Z grubsza rzecz biorąc, większość implementacji multi-atrybutówhashCode() podąża za 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 StackOverflow, aby uzyskać więcej informacji na temat magii kryjącej się za 31 i dlaczego kod Java używa go tak często. Jest niedoskonały, ale ma bardzo dobre ogólne właściwości użytkowe.

Zakryj lewe 2 kolumny i spróbuj ustalić, jakie wejścia używają tylko wyjścia.

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

Kiedy zobaczyłeś 1-bit, powinieneś był zorientować się, że oba wejścia są 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 nic o tym nie mówi.