pengembangan-web-mp.com

Dari mana konstanta hashing "ajaib" seperti 0x9e3779b9 dan 0x9e3779b1 berasal?

Dalam menangani kode tabel hash, saya sering menemukan 0x9e3779b9 konstan atau kadang-kadang 0x9e3779b1. Sebagai contoh

hash = n * 0x9e3779b1 >>> 24

Mengapa nilai khusus ini digunakan?

137
bkgs

0x9e3779b9 Adalah bagian integral dari bagian pecahan Golden Rasio 0.61803398875 ... (sqrt (5) -1)/2, dikalikan dengan 2 ^ 32.

Maka, jika φ = (sqrt (5) +1)/2 = 1.61803398875 adalah Rasio Emas, fungsi hash menghitung bagian fraksional dari n * φ, yang memiliki sifat hamburan Nice. Untuk meyakinkan diri Anda sendiri, cukup buat sebar sebaran (n, n*c-FLOOR(n*c)) Di spreadsheet favorit Anda, ganti c dengan φ, e, π, dll. Beberapa masalah kehidupan nyata yang menarik ketika melakukan kesalahan dijelaskan dalam https://lkml.org/lkml/2016/4/29/838 .

Metode ini sering disebut sebagai "Golden Ratio Hashing", atau "Fibonacci Hashing" dan dipopulerkan oleh Donald Knuth (Seni Pemrograman Komputer: Volume 3: Penyortiran dan Pencarian). Dalam sejumlah istilah teoretis, sebagian besar bermuara pada dugaan Steinhaus ( https://en.wikipedia.org/wiki/Three-gap_theorem ) dan simetri rekursif dari bagian pecahan dari kelipatan dari Rasio Emas φ.

Kadang-kadang, Anda juga dapat melihat 0x9e3779b1, Yang merupakan yang paling dekat dengan 0x9e3779b9 (Dan tampaknya sedikit "pemujaan kargo" karena ini bukan hash modular). Demikian pula, 0x9e3779b97f4a7c15 Dan 0x9e3779b97f4a7c55 Adalah setara 64 bit dari angka-angka ini.

220
32f

Jawaban lain menjelaskan maksud di balik angka-angka ajaib itu, yang mungkin ingin Anda ketahui. Namun orang dapat mengatakan bahwa dari mana "mereka berasal" berasal dari praktik pemrograman yang buruk. Angka ajaib itu buruk, dan itu tidak boleh digunakan. Konstanta seperti yang disebutkan harus diberi nama variabel deskriptif yang tepat, dan mungkin bahkan komentar harus ditambahkan ke tempat mereka didefinisikan. Kemudian, setiap tampilan nilai dalam kode harus dalam bentuk variabel bernama. Jika demikian halnya dalam kode-kode di mana Anda memenuhi nilai-nilai itu, Anda tidak akan bingung dengan niat mereka di tempat pertama.

contoh:

Contoh buruk - menggunakan angka ajaib

hash = n * 0x9e3779b1

Contoh yang lebih baik - dengan komentar dan variabel yang bermakna

# Golden Ratio constant used for better hash scattering
# See https://softwareengineering.stackexchange.com/a/402543 
GOLDEN_RATIO = 0x9e3779b1
hash = n * GOLDEN_RATIO
30
isilanes
Dalam menangani kode tabel hash, saya sering menemukan konstanta 0x9e3779b9 atau terkadang 0x9e3779b1

Jawaban lain dengan benar menjelaskan mengapa nilai ini digunakan. Namun, jika Anda sering menemukan ini konstan, apa yang Anda mungkin tidak menyadari bahwa Anda sering menemukan kode rentan terhadap serangan banjir hash.

Ada dua strategi melawan serangan hash flooding:

  1. Gunakan fungsi hash aman yang memiliki benih acak rahasia. Fungsi hash Anda tidak memiliki benih acak rahasia. Murmurhash3_32 memiliki benih acak rahasia, tetapi memiliki multicollision bebas-benih karena kondisi internal kecil. Fungsi hash terbaik yang memiliki keamanan mendekati kriptografis dan kinerja yang hampir dapat diterima mungkin adalah SipHash. Sayangnya, ini lambat, meskipun tidak selambat SHA512 dll.

  2. Gunakan fungsi hash yang cepat untuk menghitung (seperti fungsi hash yang Anda temukan, atau Murmurhash3_32), dan buat setiap ember hash ke dalam akar pohon pencarian biner seimbang. Jadi, tabel hash terpisah yang dirantai secara terpisah memiliki masing-masing bucket sebagai daftar tertaut, yang lambat jika banyak nilai hash ke bucket yang sama. Dengan menjadikannya pohon pencarian biner seimbang seperti pohon AVL atau pohon merah-hitam, Anda masih memiliki jaminan kinerja terburuk.

Pendapat saya adalah (2) lebih baik karena SipHash sangat lambat. Juga, dalam ruang kernel sistem operasi mungkin tidak ada cukup entropi untuk membuat seed acak rahasia di awal tahap boot-up, jadi dalam ruang kernel Anda mungkin tidak memiliki kemampuan untuk membuat angka acak di awal bootup.

Tabel hash banyak disalahgunakan. Mudah untuk menurunkan banyak sistem hingga berhenti secara praktis hanya dengan mengirimkan banyak nilai yang hash ke keranjang yang sama.

5
juhist