Angka ajaib dalam peningkatan :: hash_combine

94

Fungsi boost::hash_combinetemplate mengambil referensi ke hash (dipanggil seed) dan objek v. Menurut dokumen , ini digabungkan seeddengan hash voleh

seed ^= hash_value(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);

Saya dapat melihat bahwa ini deterministik. Saya mengerti mengapa XOR digunakan.

Saya yakin penambahan membantu dalam memetakan nilai yang sama secara terpisah sehingga tabel hash probing tidak akan rusak, tetapi dapatkah seseorang menjelaskan apa konstanta ajaib itu?

c++ algorithm boost hash magic-numbers Fred Foo
sumber
Mengingat bahwa pada banyak komputer, biaya rotasi bilangan bulat hampir sama dengan pergeseran akan ada keuntungan dalam mengonversi ekspresi menjadi: <code> seed ^ = hash_value (v) + 0x9e3779b9 + rotl (seed, 6) + rotr (seed, 2); </code>
John Yates

Jawaban:

141

Angka ajaib seharusnya 32 bit acak, di mana masing-masing kemungkinan besar adalah 0 atau 1, dan tanpa korelasi sederhana antara bit. Cara umum untuk menemukan string bit tersebut adalah dengan menggunakan ekspansi biner dari bilangan irasional; dalam hal ini, angka itu adalah kebalikan dari rasio emas:

phi = (1 + sqrt(5)) / 2
2^32 / phi = 0x9e3779b9

Jadi memasukkan nomor ini "secara acak" mengubah setiap bit benih; seperti yang Anda katakan, ini berarti nilai yang berurutan akan berjauhan. Termasuk versi bergeser dari seed lama memastikan bahwa, meskipun hash_value()memiliki kisaran nilai yang cukup kecil, perbedaan akan segera tersebar di semua bit.

Mike Seymour
sumber
14
Keren! Saya suka ketika teori bilangan tiba-tiba berguna :)
Fred Foo
8
@larsmans Saya suka penggunaan 'tiba-tiba' Anda - itu sangat tepat! Teori bilangan seperti "ya, itu bagus ... tapi saya punya pekerjaan nyata yang harus dilakukan, maaf" dalam 99% dari semua kasus. Dan kemudian, seperti yang Anda katakan, 'tiba-tiba', teori bilangan sangat berguna. Ini bukan seperti palu di mana itu lebih berguna untuk sejumlah besar hal. Sebaliknya, ini seperti pisau bedah yang sangat berguna untuk beberapa hal.
corsiKa
5
@SamKellett Akan bekerja lebih baik jika Anda menggunakan jumlah tanda kurung yang benar dan mendapatkan0x9e3779b97f4a7800
Barry
5
Karena bilangan floating point Python tidak memiliki ketepatan yang cukup, rasio emas 64-bit di atas tidak benar. Hasil sebenarnya seharusnya 0x9e3779b97f4a7c15.
kennytm
1
@kennytm Bukan maksudmu 0x9e3779b97f4a7c16? Maksudku, ini hanya diskon 1.
bit2shift
25

Lihatlah artikel DDJ oleh Bob Jenkins dari tahun 1997 . Konstanta ajaib ("rasio emas") dijelaskan sebagai berikut:

Rasio emas sebenarnya adalah nilai yang sewenang-wenang. Tujuannya adalah untuk menghindari pemetaan semua nol menjadi semua nol.

NPE
sumber