Saya mencari untuk mengimplementasikan tabel hash yang cepat dan didistribusikan dengan baik di C #. Saya mengalami masalah dalam memilih fungsi hash-constraining yang mengambil kode hash sembarang dan "membatasi" sehingga dapat digunakan untuk mengindeks ember. Ada dua opsi yang saya lihat sejauh ini:
Di satu sisi, Anda dapat memastikan ember Anda selalu memiliki jumlah elemen utama, dan untuk membatasi hash Anda cukup memodonya dengan jumlah ember. Inilah sebenarnya yang dilakukan oleh .NET's Dictionary . Masalah dengan pendekatan ini adalah bahwa menggunakan% sangat lambat dibandingkan dengan operasi lain; jika Anda melihat tabel instruksi Agner Fog ,
idiv(yang merupakan kode rakitan yang dihasilkan untuk%) memiliki latensi instruksi ~ 25 siklus untuk prosesor Intel yang lebih baru. Bandingkan ini dengan sekitar 3 untukmul, atau 1 untuk ops bitwise sepertiand,or, atauxor.Di sisi lain, Anda dapat memiliki jumlah ember selalu menjadi kekuatan 2. Anda masih harus menghitung modulus hash sehingga Anda tidak berusaha untuk mengindeks di luar array, tetapi kali ini akan lebih murah . Karena untuk kekuatan 2
% Nhanya& (N - 1), pembatas direduksi menjadi operasi masking yang hanya membutuhkan 1-2 siklus. Ini dilakukan oleh Google sparsehash . Kelemahan dari ini adalah bahwa kami mengandalkan pengguna untuk menyediakan hash yang baik; menutupi hash pada dasarnya memotong sebagian dari hash, jadi kita tidak lagi memperhitungkan semua bagian dari hash. Jika hash pengguna tidak terdistribusi secara merata, misalnya hanya bit yang lebih tinggi yang diisi atau bit yang lebih rendah secara konsisten sama, maka pendekatan ini memiliki tingkat tabrakan yang jauh lebih tinggi.
Saya mencari algoritme yang dapat saya gunakan yang memiliki yang terbaik dari kedua dunia: ia mengambil semua bit hash ke dalam akun, dan juga lebih cepat daripada menggunakan%. Itu tidak harus harus menjadi modulus, hanya sesuatu yang dijamin berada dalam kisaran 0..N-1(di mana N adalah panjang ember) dan memiliki distribusi yang merata untuk semua slot. Apakah ada algoritma seperti itu?
Terima kasih telah membantu.
sumber
(2^N +/- 1), lihat stackoverflow.com/questions/763137/…Jawaban:
Implementasi tabel hash modern tidak menggunakan fungsi modulo. Mereka sering menggunakan kekuatan dua tabel ukuran dan memotong bit yang tidak dibutuhkan. Fungsi hash yang ideal akan memungkinkan ini. Penggunaan modulo dikombinasikan dengan ukuran tabel bilangan prima muncul pada hari-hari ketika fungsi hash umumnya buruk, karena mereka sering dalam pengembangan .net. Saya merekomendasikan membaca tentang SipHash , fungsi hash modern, kemudian membaca tentang beberapa fungsi modern lainnya, seperti xxHash .
Saya harus menjelaskan mengapa. Fungsi hash bersih sering buruk. Di .net, programmer sering dipaksa untuk mengimplementasikan fungsi hash dengan mengesampingkan GetHashcode. Tetapi .net tidak menyediakan alat yang diperlukan untuk memastikan fungsi yang dibuat programmer berkualitas tinggi, yaitu:
Untuk informasi lebih lanjut tentang menggunakan hasil fungsi hash sebagai indeks tabel hash, silakan lihat definisi bentuk universal hashing dalam makalah ini: hashing universal 64-bit lebih cepat menggunakan multiplikasi carry-less
sumber
Untuk menggunakan DAN sambil tetap menyimpan semua bit, gunakan XOR juga.
Sebagai contoh
temp = (hash & 0xFFFF) ^ ( hash >> 16); index = (temp & 0xFF) ^ (temp >> 8);,.Untuk contoh ini, tidak ada modulo dan semua 32 bit
hashefek 8-bitindex. Namun, apakah itu lebih cepat daripada DIV adalah sesuatu yang tergantung pada terlalu banyak faktor, dan dapat dengan mudah lebih lambat daripada DIV dalam beberapa kasus (misalnya hash besar dan indeks kecil).sumber
indexakan berada dalam jangkauan[0..255]. Saya butuh sesuatu di kisaran[0..n-1], di mananjumlah ember.Anda dapat mengambil keuntungan dari kenyataan bahwa banyak bilangan bulat utama memiliki pembalikan multiplikasi modular. Lihat artikel ini . Anda telah memenuhi salah satu kendala dengan menjadikan indeks bucket Anda prima dan modulus 2, yang secara inheren relatif prima.
Artikel ini menjelaskan algoritma untuk menemukan angka sedemikian sehingga mengalikannya dengan angka itu, dan mengabaikan luapan, akan menghasilkan hasil yang sama seolah-olah Anda telah dibagi dengan ukuran indeks ember.
sumber