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 XOR
nich 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.)?
cryptography
bit-manipulation
hash
probability
xor
Nate Murray
źródło
źródło
Odpowiedzi:
Zakładając jednolicie losowe (1-bitowe) dane wejściowe, rozkład prawdopodobieństwa wyjścia funkcji AND wynosi 75%
0
i 25%1
. I odwrotnie, OR wynosi 25%0
i 75%1
.Funkcja XOR wynosi 50%
0
i 50%1
, dlatego dobrze jest łączyć jednolite rozkłady prawdopodobieństwa.Można to zobaczyć, wypisując tabele prawdy:
Ćwiczenie: Ile funkcji logicznych ma dwa 1-bitowe wejścia
a
ib
ma taki jednolity rozkład wyjściowy? Dlaczego XOR jest najbardziej odpowiedni do celu określonego w pytaniu?źródło
(0, a & b, a > b, a, a < b, b, a % b, a | b, !a & !b, a == b, !b, a >= b, !a, a <= b, !a | !b, 1)
następujące mają rozkłady 50% -50% zera i 1, przy założeniu, że a i b mają rozkłady 50% -50% zera i jedynki:a, b, !a, !b, a % b, a == b
czyli odwrotnie of XOR (EQUIV) mógł być również użyty ...a, b, !a, !b
będą miały taki sam rozkład, jak ich odpowiednie dane wejściowe, tracisz entropię drugiego wejścia. Oznacza to, że XOR jest najbardziej odpowiedni do łączenia skrótów, ponieważ chcemy uchwycić entropię zarówno z a, jak i b.(a,a)
i(b,b)
oba produkty zera, co w wielu (większość?) Przypadkach znacznie zwiększa prawdopodobieństwo kolizji w strukturach danych opartych hash.xor
jest niebezpieczną funkcją domyślną do użycia podczas mieszania. Jest lepszy niżand
ior
, ale to niewiele mówi.xor
jest 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
xor
koń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 tegoxor
na 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 przypadkua==b
, gdy wynikiem jesthash(a)<<1
zamiast 0.To pozostaje symetryczne; więc
"bad"
i"dab"
otrzymuję ten sam rezultat pozostaje problemem. Możemy złamać tę symetrię niewielkim kosztem: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 zamiast3
będzie bijektywnie odwzorowywać "k
-bit" liczbę całkowitą bez znaku na siebie, ponieważ mapowanie na liczbach całkowitych bez znaku jest2^k
dla niektórych matematyczne modulok
, a każda nieparzysta stała jest względnie pierwsza2^k
.Aby uzyskać jeszcze bardziej wyszukaną wersję, możemy sprawdzić
boost::hash_combine
, co jest efektywne:tutaj dodajemy razem kilka przesuniętych wersji
seed
ze stałą (która jest w zasadzie losowym0
s i1
s - 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 rozmazanie1
i0
s po każdym połączeniu. Mój naiwny3*hash(a)+hash(b)
po prostu wyświetla0
in ta walizka).(Dla tych, którzy nie znają języka C / C ++, a
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 liczba całkowita bez znaku. W systemie 32-bitowym , 32-bitowa liczba całkowita bez znaku).źródło
0x9e3779b9
.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.
źródło
long
a następnie połączenie górnej części z dolną częścią.m = 3
jest właściwie dobrym wyborem i bardzo szybkim w wielu systemach. Zauważ, że dla każdego nieparzystegom
mnożenia liczb całkowitych jest modulo2^32
lub2^64
i dlatego jest odwracalne, więc nie tracisz żadnych bitów.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!
źródło
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.
źródło
OR
jest bitowe max iAND
jest bitowe min .Jeśli masz
XOR
losowe wejście z polaryzowanym wejściem, wyjście jest losowe. To samo nie dotyczyAND
lubOR
. Przykład:Jak wspomina @Greg Hewgill, nawet jeśli oba wejścia są losowe, użycie
AND
lubOR
spowoduje odchylenie wyjścia.Powodem, dla którego używamy
XOR
czegoś bardziej złożonego, jest to, że nie ma potrzeby:XOR
działa idealnie i jest niesamowicie głupio-szybkie.źródło
Zakryj dwie lewe kolumny i spróbuj ustalić, jakie dane wejściowe wykorzystują tylko dane wyjściowe.
Kiedy zobaczyłeś 1-bit, powinieneś był się domyślić, że oba wejścia mają wartość 1.
Teraz zrób to samo dla XOR
XOR nie zdradza nic na temat danych wejściowych.
źródło
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:Możesz przeszukać inne pytania i odpowiedzi StackOverflow, aby uzyskać więcej informacji o magii
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.źródło
string
Kolizjami zstring + "AA"
IIRC) i dawno temu żałowali, że nie wprowadzili tego algorytmu do specyfikacji. To powiedziawszy, użycie większej liczby nieparzystej z większą liczbą ustawionych bitów i dodanie przesunięć lub obrotów rozwiązuje ten problem. „Mix” MurmurHash3 robi to.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ą.
źródło