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 XOR
mereka, 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.)?
cryptography
bit-manipulation
hash
probability
xor
Nate Murray
sumber
sumber
Jawaban:
Dengan asumsi input acak seragam (1-bit), distribusi probabilitas output fungsi AND adalah 75%
0
dan 25%1
. Sebaliknya, OR adalah 25%0
dan 75%1
.Fungsi XOR adalah 50%
0
dan 50%1
, oleh karena itu baik untuk menggabungkan distribusi probabilitas yang seragam.Ini bisa dilihat dengan menuliskan tabel kebenaran:
Latihan: Berapa banyak fungsi logis dari dua input 1-bit
a
danb
memiliki distribusi output yang seragam ini? Mengapa XOR paling cocok untuk tujuan yang disebutkan dalam pertanyaan Anda?sumber
(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 == b
yaitu sebaliknya XOR (EQUIV) bisa digunakan juga ...a, b, !a, !b
akan 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.(a,a)
dan(b,b)
keduanya menghasilkan nol, yang dalam banyak (kebanyakan?) Kasus sangat meningkatkan kemungkinan tabrakan dalam struktur data berbasis hash.xor
adalah fungsi default berbahaya untuk digunakan saat hashing. Itu lebih baik daripadaand
danor
, tapi itu tidak banyak bicara.xor
simetris, 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,
xor
akhirnya 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 denganxor
pada 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 daripadahash(a) xor hash(b)
jikaa==b
, hasilnyahash(a)<<1
bukan 0.Ini tetap simetris; jadi
"bad"
dan"dab"
mendapatkan hasil yang sama tetap menjadi masalah. Kami dapat memutus simetri ini dengan biaya sederhana:alias
hash(a)*3 + hash(b)
. (menghitunghash(a)
sekali dan menyimpan disarankan jika Anda menggunakan solusi shift). Konstanta ganjil mana pun alih-alih3
secara bijektif akan memetakank
bilangan bulat tak bertanda "-bit" ke dirinya sendiri, karena peta bilangan bulat tak bertanda adalah modulo matematika2^k
untuk beberapak
, dan konstanta ganjil apa pun relatif utama2^k
.Untuk versi yang lebih keren, kita dapat memeriksa
boost::hash_combine
, yang secara efektif:di sini kami menambahkan bersama beberapa versi bergeser dari
seed
dengan konstanta (yang pada dasarnya acak0
s dan1
s - 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 noda1
dan0
s setelah masing-masing digabungkan. Naif saya3*hash(a)+hash(b)
hanya menghasilkan a0
di 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.)sumber
0x9e3779b9
.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.
sumber
long
dan kemudian mengisi bagian atas kembali dengan bagian bawah.m = 3
sebenarnya merupakan pilihan yang baik dan sangat cepat pada banyak sistem. Perhatikan bahwa untuk setiapm
penggandaan bilangan bulat ganjil adalah modulo2^32
atau2^64
dan karena itu tidak dapat dibalik sehingga Anda tidak kehilangan bit.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!
sumber
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.
sumber
OR
adalah max bitwise , danAND
adalah bitwise min .Jika Anda
XOR
input acak dengan input bias, outputnya acak. Hal yang sama tidak berlaku untukAND
atauOR
. Contoh:Seperti @Greg Hewgill menyebutkan, bahkan jika kedua input tersebut acak, menggunakan
AND
atauOR
akan menghasilkan output yang bias.Alasan kami menggunakan
XOR
lebih dari sesuatu yang lebih kompleks adalah, yah, tidak perlu:XOR
bekerja dengan sempurna, dan sangat cepat.sumber
Tutupi 2 kolom kiri dan coba cari tahu apa input menggunakan hanya output.
Ketika Anda melihat 1-bit, Anda seharusnya mengetahui bahwa kedua input tersebut adalah 1.
Sekarang lakukan hal yang sama untuk XOR
XOR tidak memberikan apa-apa tentang itu input.
sumber
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: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.sumber
string
bertabrakan denganstring + "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.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.
sumber