Mengapa XOR cara default untuk menggabungkan hash?

145

Katakanlah Anda memiliki dua hash H(A)dan H(B)dan Anda ingin menggabungkannya. Saya telah membaca bahwa cara yang baik untuk menggabungkan dua hash adalah dengan XORmereka, misalnya XOR( H(A), H(B) ).

Penjelasan terbaik yang saya temukan disentuh secara singkat di sini pada pedoman fungsi hash ini :

XORing dua angka dengan distribusi acak menghasilkan angka lain masih dengan distribusi acak *, tetapi yang sekarang tergantung pada dua nilai.
...
* Pada setiap bit dari dua angka untuk digabungkan, 0 adalah output jika kedua bit itu sama, atau 1. Dengan kata lain, dalam 50% dari kombinasi, 1 akan menjadi output. Jadi jika dua bit input masing-masing memiliki peluang sekitar 50-50 menjadi 0 atau 1, maka bit output juga akan.

Bisakah Anda menjelaskan intuisi dan / atau matematika di balik mengapa XOR harus menjadi operasi default untuk menggabungkan fungsi hash (daripada ATAU DAN DAN dll.)?

Nate Murray
sumber
20
Saya pikir Anda baru saja melakukannya;)
Massa
22
perhatikan bahwa XOR mungkin atau mungkin bukan cara "baik" untuk "menggabungkan" hash, tergantung pada apa yang Anda inginkan dalam "kombinasi". XOR bersifat komutatif: XOR (H (A), H (B)) sama dengan XOR (H (B), H (A)). Ini berarti bahwa XOR bukan cara yang tepat untuk membuat semacam hash dari urutan nilai yang dipesan, karena itu tidak menangkap urutan.
Thomas Pornin
6
Selain masalah dengan urutan (komentar di atas), ada masalah dengan nilai yang sama. XOR (H (1), H (1)) = 0 (untuk fungsi apa pun H), XOR (H (2), H (2)) = 0 dan seterusnya. Untuk setiap N: XOR (H (N), H (N)) = 0. Nilai yang sama terjadi cukup sering di aplikasi nyata, artinya hasil XOR akan 0 terlalu sering untuk dianggap sebagai hash yang baik.
Andrei Galatyn
Apa yang Anda gunakan untuk urutan nilai yang dipesan? Katakanlah saya ingin membuat hash cap waktu atau indeks. (MSB kurang penting dari LSB). Maaf jika utas ini berumur 1 tahun.
Alexis

Jawaban:

120

Dengan asumsi input acak seragam (1-bit), distribusi probabilitas output fungsi AND adalah 75% 0dan 25% 1. Sebaliknya, OR adalah 25% 0dan 75% 1.

Fungsi XOR adalah 50% 0dan 50% 1, oleh karena itu baik untuk menggabungkan distribusi probabilitas yang seragam.

Ini bisa dilihat dengan menuliskan tabel kebenaran:

 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

Latihan: Berapa banyak fungsi logis dari dua input 1-bit adan bmemiliki distribusi output yang seragam ini? Mengapa XOR paling cocok untuk tujuan yang disebutkan dalam pertanyaan Anda?

Greg Hewgill
sumber
24
menjawab latihan: dari 16 operasi XXX b yang mungkin berbeda (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), berikut ini memiliki 50% -50% distribusi 0s dan 1s, dengan asumsi a dan b memiliki distribusi 50% -50% dari 0s dan 1s:, a, b, !a, !b, a % b, a == byaitu sebaliknya XOR (EQUIV) bisa digunakan juga ...
Massa
7
Greg, ini jawaban yang luar biasa. Bola lampu menyala untuk saya setelah saya melihat jawaban asli Anda dan menulis tabel kebenaran saya sendiri. Saya mempertimbangkan jawaban @ Massa tentang bagaimana ada 6 operasi yang sesuai untuk menjaga distribusi. Dan sementara a, b, !a, !bakan memiliki distribusi yang sama dengan input masing-masing, Anda kehilangan entropi dari input lainnya. Artinya, XOR paling cocok untuk tujuan menggabungkan hash karena kami ingin menangkap entropi dari a dan b.
Nate Murray
1
Berikut adalah makalah yang menjelaskan bahwa menggabungkan hash dengan aman di mana setiap fungsi dipanggil hanya sekali tidak mungkin tanpa menghasilkan bit lebih sedikit dari jumlah jumlah bit di setiap nilai hash. Ini menunjukkan bahwa jawaban ini tidak benar.
Tamás Szelei
3
@Massa Saya belum pernah melihat% digunakan untuk XOR atau tidak sama.
Buge
7
Seperti ditunjukkan Yakk , XOR bisa berbahaya karena menghasilkan nol untuk nilai yang identik. Ini berarti (a,a)dan (b,b)keduanya menghasilkan nol, yang dalam banyak (kebanyakan?) Kasus sangat meningkatkan kemungkinan tabrakan dalam struktur data berbasis hash.
Drew Noakes
170

xoradalah fungsi default berbahaya untuk digunakan saat hashing. Itu lebih baik daripada anddan or, tapi itu tidak banyak bicara.

xorsimetris, sehingga urutan unsur-unsurnya hilang. Jadi "bad"hash akan menggabungkan sama dengan "dab".

xor memetakan nilai identik berpasangan ke nol, dan Anda harus menghindari pemetaan nilai "umum" ke nol:

Jadi (a,a)dipetakan ke 0, dan (b,b)juga dipetakan ke 0. Karena pasangan seperti itu hampir selalu lebih umum daripada keacakan mungkin menyiratkan, Anda berakhir dengan banyak tabrakan jauh di nol dari yang seharusnya.

Dengan dua masalah ini, xorakhirnya menjadi hash combiner yang terlihat setengah layak di permukaan, tetapi tidak setelah pemeriksaan lebih lanjut.

Pada perangkat keras modern, menambahkan biasanya sekitar secepat xor(mungkin menggunakan lebih banyak daya untuk melakukan ini, diakui). Menambahkan tabel kebenaran mirip dengan xorpada bit yang dimaksud, tetapi juga mengirimkan sedikit ke bit berikutnya ketika kedua nilai adalah 1. Ini berarti ia menghapus lebih sedikit informasi.

Jadi hash(a) + hash(b)lebih baik daripada hash(a) xor hash(b)jika a==b, hasilnya hash(a)<<1bukan 0.

Ini tetap simetris; jadi "bad"dan"dab" mendapatkan hasil yang sama tetap menjadi masalah. Kami dapat memutus simetri ini dengan biaya sederhana:

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

alias hash(a)*3 + hash(b) . (menghitung hash(a)sekali dan menyimpan disarankan jika Anda menggunakan solusi shift). Konstanta ganjil mana pun alih-alih 3secara bijektif akan memetakan kbilangan bulat tak bertanda "-bit" ke dirinya sendiri, karena peta bilangan bulat tak bertanda adalah modulo matematika 2^kuntuk beberapak , dan konstanta ganjil apa pun relatif utama 2^k.

Untuk versi yang lebih keren, kita dapat memeriksa boost::hash_combine, yang secara efektif:

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

di sini kami menambahkan bersama beberapa versi bergeser dari seed dengan konstanta (yang pada dasarnya acak 0s dan 1s - khususnya itu adalah kebalikan dari rasio emas sebagai fraksi titik tetap 32 bit) dengan beberapa tambahan dan xor. Ini memecah simetri, dan memperkenalkan beberapa "noise" jika nilai hash yang masuk buruk (yaitu, bayangkan setiap komponen hash ke 0 - di atas menanganinya dengan baik, menghasilkan noda 1dan0 s setelah masing-masing digabungkan. Naif saya 3*hash(a)+hash(b)hanya menghasilkan a 0di kasus itu).

(Bagi mereka yang tidak terbiasa dengan C / C ++, a size_t adalah nilai integer yang tidak ditandatangani yang cukup besar untuk menggambarkan ukuran objek apa pun dalam memori. Pada sistem 64 bit, biasanya integer 64 bit yang tidak ditandai. Pada sistem 32 bit , bilangan bulat 32 bit unsigned.)

Yakk - Adam Nevraumont
sumber
Jawaban bagus Yakk. Apakah algoritma ini bekerja dengan baik pada sistem 32bit dan 64bit? Terima kasih.
Dave
1
@ jangan tambahkan bit ke 0x9e3779b9.
Yakk - Adam Nevraumont
10
OK, harus lengkap ... di sini adalah konstanta 64bit presisi penuh (dihitung dengan ganda panjang, dan panjang tidak ditandai): 0x9e3779b97f4a7c16. Menariknya, ini masih merata. Melakukan kembali perhitungan yang sama menggunakan PI dan bukannya Golden Ratio menghasilkan: 0x517cc1b727220a95 yang aneh, bukan genap, sehingga mungkin "lebih prima" daripada konstanta lainnya. Saya menggunakan: std :: cout << std :: hex << (panjang tidak ditandai) ((1.0L / 3.14159265358979323846264338327950288419716939937510L) * (powl (2.0L, 64.0L))) << std :: endl; dengan cout.precision (numeric_limits <long double> :: max_digits10); Terima kasih lagi Yakk.
Dave
2
@Memiliki aturan rasio emas terbalik untuk kasus ini adalah angka ganjil pertama sama dengan atau lebih besar dari perhitungan yang Anda lakukan. Jadi tambahkan saja 1. Ini adalah angka penting karena urutan N * rasio, mod ukuran maks (2 ^ 64 di sini) menempatkan nilai berikutnya dalam urutan tepat pada rasio di tengah 'celah' terbesar di angka. Cari di web untuk "Fibonacci hashing" untuk info lebih lanjut.
Scott Carey
1
@Dapatkan nomor yang benar adalah 0,9E3779B97F4A7C15F39 ... Lihat tautan . Anda mungkin menderita dari aturan round-to-even (yang baik untuk akuntan), atau hanya, jika Anda mulai dengan konstanta literal (5) literal, ketika Anda mengurangi 1, Anda menghapus bit orde tinggi, sebuah bit pasti telah hilang.
migle
29

Terlepas dari sifat pencampuran bitnya yang praktis, XOR tidak cara yang baik untuk menggabungkan hash karena sifatnya yang komutatif. Pertimbangkan apa yang akan terjadi jika Anda menyimpan permutasi {1, 2, ..., 10} dalam tabel hash dengan 10-tupel.

Pilihan yang jauh lebih baik adalah m * H(A) + H(B), di mana m adalah angka ganjil yang besar.

Credit: Combiner di atas adalah tip dari Bob Jenkins.

Marcelo Cantos
sumber
2
Terkadang komutatif adalah hal yang baik, tetapi xor adalah pilihan yang buruk bahkan karena semua pasangan item yang cocok akan mendapatkan hash menjadi nol. Jumlah aritmatika lebih baik; hash dari sepasang item yang cocok akan mempertahankan hanya 31 bit data berguna daripada 32, tapi itu jauh lebih baik daripada mempertahankan nol. Pilihan lain mungkin untuk menghitung jumlah aritmatika sebagai a longdan kemudian mengisi bagian atas kembali dengan bagian bawah.
supercat
1
m = 3sebenarnya merupakan pilihan yang baik dan sangat cepat pada banyak sistem. Perhatikan bahwa untuk setiap mpenggandaan bilangan bulat ganjil adalah modulo 2^32atau 2^64dan karena itu tidak dapat dibalik sehingga Anda tidak kehilangan bit.
StefanKarpinski
Apa yang terjadi ketika Anda melampaui MaxInt?
Mengganggu
2
alih-alih angka ganjil, siapa pun harus memilih perdana
TermoTux
2
@Infinum yang tidak perlu saat menggabungkan hash.
Marcelo Cantos
17

Xor mungkin merupakan cara "default" untuk menggabungkan hash tetapi jawaban Greg Hewgill juga menunjukkan mengapa ia memiliki jebakan: Xor dari dua nilai hash yang identik adalah nol. Dalam kehidupan nyata, ada hash yang identik lebih umum daripada yang diperkirakan. Anda kemudian mungkin menemukan bahwa dalam kasus-kasus sudut (tidak begitu jarang) ini, hash gabungan yang dihasilkan selalu sama (nol). Tabrakan hash akan jauh, jauh lebih sering daripada yang Anda harapkan.

Dalam contoh yang dibuat-buat, Anda mungkin menggabungkan kata sandi hash dari pengguna dari berbagai situs web yang Anda kelola. Sayangnya, sejumlah besar pengguna menggunakan kembali kata sandi mereka, dan proporsi yang mengejutkan dari hash yang dihasilkan adalah nol!

Leo Goodstadt
sumber
Saya harap contoh yang dibuat tidak pernah terjadi, kata sandi harus diasinkan.
user60561
8

Ada sesuatu yang ingin saya tunjukkan secara eksplisit untuk orang lain yang menemukan halaman ini. DAN dan ATAU membatasi keluaran seperti BlueRaja - Danny Pflughoe berusaha menunjukkan, tetapi dapat didefinisikan dengan lebih baik:

Pertama saya ingin mendefinisikan dua fungsi sederhana yang akan saya gunakan untuk menjelaskan ini: Min () dan Max ().

Min (A, B) akan mengembalikan nilai yang lebih kecil antara A dan B, misalnya: Min (1, 5) mengembalikan 1.

Max (A, B) akan mengembalikan nilai yang lebih besar antara A dan B, misalnya: Max (1, 5) mengembalikan 5.

Jika Anda diberikan: C = A AND B

Maka Anda dapat menemukannya C <= Min(A, B) Kami tahu ini karena tidak ada yang dapat Anda DAN dengan 0 bit A atau B untuk menjadikannya 1s. Jadi setiap bit nol tetap merupakan bit nol dan setiap bit memiliki peluang untuk menjadi bit nol (dan dengan demikian nilai yang lebih kecil).

Dengan: C = A OR B

Yang sebaliknya adalah benar: C >= Max(A, B)Dengan ini, kita melihat konsekuensi wajar untuk fungsi AND. Setiap bit yang sudah menjadi satu tidak bisa ORed menjadi nol, jadi itu tetap satu, tetapi setiap bit nol memiliki kesempatan untuk menjadi satu, dan dengan demikian jumlah yang lebih besar.

Ini menyiratkan bahwa keadaan input berlaku pembatasan pada output. Jika Anda DAN apa pun dengan 90, Anda tahu output akan sama dengan atau kurang dari 90 terlepas dari apa nilai lainnya.

Untuk XOR, tidak ada batasan tersirat berdasarkan input. Ada kasus-kasus khusus di mana Anda dapat menemukan bahwa jika Anda XOR byte dengan 255 daripada Anda mendapatkan kebalikannya, tetapi byte yang mungkin dapat dihasilkan dari itu. Setiap bit memiliki kesempatan untuk mengubah status tergantung pada bit yang sama di operan lainnya.

Corey Ogburn
sumber
6
Orang bisa mengatakan bahwa ORadalah max bitwise , dan ANDadalah bitwise min .
Paŭlo Ebermann
Paulo Ebermann menyatakan dengan sangat baik. Senang melihat Anda di sini dan juga Crypto.SE!
Corey Ogburn
Saya membuat filter yang menyertakan saya segala sesuatu yang ditandai dengan kriptografi , juga mengubah pertanyaan lama. Dengan cara ini saya menemukan jawaban Anda di sini.
Paŭlo Ebermann
3

Jika Anda XORinput acak dengan input bias, outputnya acak. Hal yang sama tidak berlaku untuk ANDatau OR. Contoh:

00101001 XOR 00000000 = 00101001
00101001 DAN 00000000 = 00000000
00101001 ATAU 11111111 = 11111111

Seperti @Greg Hewgill menyebutkan, bahkan jika kedua input tersebut acak, menggunakan ANDatau ORakan menghasilkan output yang bias.

Alasan kami menggunakan XORlebih dari sesuatu yang lebih kompleks adalah, yah, tidak perlu: XORbekerja dengan sempurna, dan sangat cepat.

BlueRaja - Danny Pflughoeft
sumber
1

Tutupi 2 kolom kiri dan coba cari tahu apa input menggunakan hanya output.

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

Ketika Anda melihat 1-bit, Anda seharusnya mengetahui bahwa kedua input tersebut adalah 1.

Sekarang lakukan hal yang sama untuk XOR

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

XOR tidak memberikan apa-apa tentang itu input.

Robert
sumber
0

Kode sumber untuk berbagai versi hashCode()di java.util.Arrays adalah referensi yang bagus untuk algoritma hashing yang umum digunakan. Mereka mudah dipahami dan diterjemahkan ke dalam bahasa pemrograman lain.

Secara kasar, sebagian besar hashCode()implementasi multi-atribut mengikuti pola ini:

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

Anda dapat mencari Tanya Jawab StackOverflow lainnya untuk informasi lebih lanjut tentang keajaiban di baliknya 31, dan mengapa kode Java sering menggunakannya. Tidak sempurna, tetapi memiliki karakteristik kinerja umum yang sangat baik.

kevinarpe
sumber
2
Default Java "multply by 31 and add / akumulasi" hash dimuat dengan tabrakan (misalnya setiap stringbertabrakan dengan string + "AA"IIRC) dan mereka sejak lama berharap mereka tidak memasukkan algoritma itu ke dalam spesifikasi. Yang mengatakan, menggunakan nomor ganjil yang lebih besar dengan bit lebih banyak diatur, dan menambahkan pergeseran atau rotasi memperbaiki masalah itu. 'Campuran' MurmurHash3 melakukan ini.
Scott Carey
0

XOR tidak mengabaikan beberapa input terkadang seperti OR dan AND .

Jika Anda mengambil AND (X, Y) misalnya, dan memasukkan input X dengan false, maka input Y tidak masalah ... dan orang mungkin ingin input menjadi masalah saat menggabungkan hash.

Jika Anda mengambil XOR (X, Y) maka KEDUA masukan SELALU penting. Tidak akan ada nilai X di mana Y tidak masalah. Jika X atau Y diubah maka output akan mencerminkan itu.

Sunsetquest
sumber