Secara umum, Anda harus memilih pengali yang sesuai dengan urutan ukuran hash Anda ( 2^32dalam contoh) dan tidak memiliki faktor persekutuan dengannya. Dengan cara ini fungsi hash mencakup semua ruang hash Anda secara seragam.
Sunting: Kerugian terbesar dari fungsi hash ini adalah ia mempertahankan pembagian, jadi jika semua bilangan bulat Anda habis dibagi 2 atau oleh 4 (yang tidak jarang), hash mereka juga akan habis. Ini adalah masalah dalam tabel hash - Anda bisa mendapatkan hanya 1/2 atau 1/4 ember yang digunakan.
Ini adalah fungsi hash yang sangat buruk, meskipun dilampirkan ke nama terkenal.
Seun Osewa
5
Ini sama sekali bukan fungsi hash yang buruk jika digunakan dengan ukuran tabel utama. Juga, ini dimaksudkan untuk hashing tertutup . Jika nilai hash tidak didistribusikan secara seragam, penggandaan hashing memastikan bahwa tabrakan dari satu nilai tidak mungkin "mengganggu" item dengan nilai hash lainnya.
Paolo Bonzini
11
Bagi yang penasaran, konstanta ini dipilih menjadi ukuran hash (2 ^ 32) dibagi dengan Phi
awdz9nld
7
Paolo: Metode Knuth adalah "buruk" dalam arti bahwa ia tidak longsor di bagian atas
awdz9nld
9
Jika diamati lebih dekat, ternyata 2654435761 sebenarnya adalah bilangan prima. Jadi itu mungkin mengapa itu dipilih daripada 2654435769.
karadoc
149
Saya menemukan algoritme berikut memberikan distribusi statistik yang sangat baik. Setiap bit input mempengaruhi setiap bit output dengan probabilitas sekitar 50%. Tidak ada benturan (setiap masukan menghasilkan keluaran yang berbeda). Algoritmanya cepat kecuali jika CPU tidak memiliki unit perkalian integer built-in. Kode C, dengan asumsi int32 bit (untuk Java, ganti >>dengan >>>dan hapus unsigned):
unsignedint hash(unsignedint x){
x =((x >>16)^ x)*0x45d9f3b;
x =((x >>16)^ x)*0x45d9f3b;
x =(x >>16)^ x;return x;}
Angka ajaib dihitung menggunakan program uji multi-utas khusus yang berjalan selama berjam-jam, yang menghitung efek longsoran (jumlah bit keluaran yang berubah jika satu bit masukan diubah; rata-rata harus hampir 16), independensi perubahan bit keluaran (bit keluaran tidak harus bergantung satu sama lain), dan kemungkinan perubahan pada setiap bit keluaran jika ada bit masukan yang diubah. Nilai yang dihitung lebih baik daripada finalizer 32-bit yang digunakan oleh MurmurHash , dan hampir sama baiknya (tidak cukup) seperti saat menggunakan AES . Sedikit keuntungannya adalah bahwa konstanta yang sama digunakan dua kali (itu membuatnya sedikit lebih cepat terakhir kali saya menguji, tidak yakin apakah itu masih terjadi).
Anda dapat membalikkan proses (mendapatkan nilai input dari hash) jika Anda mengganti 0x45d9f3bdengan 0x119de1f3( pembalikan perkalian ):
unsignedint unhash(unsignedint x){
x =((x >>16)^ x)*0x119de1f3;
x =((x >>16)^ x)*0x119de1f3;
x =(x >>16)^ x;return x;}
Untuk nomor 64-bit, saya sarankan untuk menggunakan yang berikut ini, meskipun menurut saya ini bukan yang tercepat. Yang ini didasarkan pada splitmix64 , yang tampaknya didasarkan pada artikel blog Better Bit Mixing (campuran 13).
uint64_t hash(uint64_t x){
x =(x ^(x >>30))* UINT64_C(0xbf58476d1ce4e5b9);
x =(x ^(x >>27))* UINT64_C(0x94d049bb133111eb);
x = x ^(x >>31);return x;}
Untuk Java, gunakan long, tambahkan Lkonstanta, ganti >>dengan >>>dan hapus unsigned. Dalam kasus ini, membalikkan lebih rumit:
uint64_t unhash(uint64_t x){
x =(x ^(x >>31)^(x >>62))* UINT64_C(0x319642b2d24d8ec3);
x =(x ^(x >>27)^(x >>54))* UINT64_C(0x96de1b173f119089);
x = x ^(x >>30)^(x >>60);return x;}
Pembaruan: Anda mungkin juga ingin melihat proyek Hash Function Prospector , di mana konstanta lain (mungkin lebih baik) terdaftar.
dua baris pertama persis sama! apakah ada kesalahan ketik di sini?
Kshitij Banerjee
3
Tidak, ini bukan salah ketik, baris kedua selanjutnya mencampur bit. Menggunakan satu perkalian saja tidaklah baik.
Thomas Mueller
3
Saya mengubah angka ajaib karena menurut kasus uji saya menulis nilai 0x45d9f3b memberikan kebingungan dan difusi yang lebih baik , khususnya jika satu bit output berubah, bit output satu sama lain berubah dengan probabilitas yang hampir sama (selain semua bit output berubah dengan probabilitas yang sama jika bit masukan berubah). Bagaimana Anda mengukur 0x3335b369 bekerja lebih baik untuk Anda? Apakah int 32 bit untuk Anda?
Thomas Mueller
3
Saya mencari fungsi hash yang bagus untuk 64 bit unsigned int ke 32 bit unsigned int. Apakah untuk kasus itu, angka ajaib di atas akan sama? Saya menggeser 32 bit, bukan 16 bit.
alessandro
3
Saya percaya dalam hal ini faktor yang lebih besar akan lebih baik, tetapi Anda perlu menjalankan beberapa tes. Atau (ini yang saya lakukan) penggunaan pertama x = ((x >> 32) ^ x)dan kemudian gunakan perkalian 32 bit di atas. Saya tidak yakin mana yang lebih baik. Anda mungkin juga ingin melihat finalizer 64-bit untuk Murmur3
Thomas Mueller
29
Tergantung pada bagaimana data Anda didistribusikan. Untuk penghitung sederhana, fungsi paling sederhana
f(i)= i
akan bagus (saya kira optimal, tapi saya tidak bisa membuktikannya).
Masalahnya dengan ini adalah umum untuk memiliki kumpulan besar bilangan bulat yang dapat dibagi oleh faktor yang sama (kata-kata alamat memori, dll.). Sekarang jika tabel hash Anda habis dibagi oleh faktor yang sama, Anda hanya akan mendapatkan setengah (atau 1/4, 1/8, dll.) Bucket yang digunakan.
Rafał Dowgird
8
@ Rafal: Itulah mengapa responsnya mengatakan "untuk penghitung sederhana" dan "Tergantung pada bagaimana data Anda didistribusikan"
@JuandeCarrion Itu menyesatkan karena bukan hash yang digunakan. Setelah beralih menggunakan kekuatan dua ukuran tabel, Java mengulangi setiap hash yang dihasilkan .hashCode(), lihat di sini .
Esailija
8
Fungsi identitas cukup tidak berguna sebagai hash dalam banyak aplikasi praktis karena sifat distributifnya (atau ketiadaan), kecuali, tentu saja, lokalitas adalah atribut yang diinginkan
awdz9nld
12
Fungsi hash yang cepat dan baik dapat disusun dari permutasi cepat dengan kualitas yang lebih rendah, seperti
perkalian dengan bilangan bulat yang tidak rata
rotasi biner
xorshift
Untuk menghasilkan fungsi hashing dengan kualitas superior, seperti yang ditunjukkan dengan PCG untuk pembuatan nomor acak.
Ini sebenarnya juga resep rrxmrrxmsx_0 dan hash murmur digunakan, disadari atau tidak disadari.
Saya pribadi menemukan
uint64_t xorshift(constuint64_t& n,int i){return n^(n>>i);}uint64_t hash(constuint64_t& n){uint64_t p =0x5555555555555555ull;// pattern of alternating 0 and 1uint64_t c =17316035218449499591ull;// random uneven integer constant; return c*xorshift(p*xorshift(n,32),32);}
untuk menjadi cukup baik.
Fungsi hash yang baik seharusnya
bijective untuk tidak kehilangan informasi, jika mungkin dan memiliki tabrakan paling sedikit
kaskade sebanyak dan serata mungkin, yaitu setiap bit masukan harus membalik setiap bit keluaran dengan probabilitas 0,5.
Pertama mari kita lihat fungsi identitas. Ini memenuhi 1. tapi tidak 2.:
Input bit n menentukan bit output n dengan korelasi 100% (merah) dan tidak ada yang lain, oleh karena itu bit input berwarna biru, memberikan garis merah sempurna.
Sebuah xorshift (n, 32) tidak jauh lebih baik, menghasilkan satu setengah baris. Masih memuaskan 1., karena bisa dibalik dengan aplikasi kedua.
Perkalian dengan unsigned integer jauh lebih baik, mengalir lebih kuat dan membalik lebih banyak bit keluaran dengan probabilitas 0,5, yang Anda inginkan, berwarna hijau. Ini memenuhi 1. karena untuk setiap bilangan bulat tidak rata ada pembalikan perkalian.
Menggabungkan keduanya menghasilkan keluaran berikut, 1. masih memuaskan karena komposisi dari dua fungsi bijektiva menghasilkan fungsi bijektiva yang lain.
Aplikasi perkalian dan xorshift kedua akan menghasilkan yang berikut:
Atau Anda dapat menggunakan perkalian medan Galois seperti GHash , perkalian tersebut telah menjadi cukup cepat pada CPU modern dan memiliki kualitas unggul dalam satu langkah.
uint64_tconstinline gfmul(constuint64_t& i,constuint64_t& j){
__m128i I{};I[0]^=i;
__m128i J{};J[0]^=j;
__m128i M{};M[0]^=0xb000000000000000ull;
__m128i X = _mm_clmulepi64_si128(I,J,0);
__m128i A = _mm_clmulepi64_si128(X,M,0);
__m128i B = _mm_clmulepi64_si128(A,M,0);return A[0]^A[1]^B[1]^X[0]^X[1];}
gfmul: Kode tersebut tampaknya adalah kode semu, karena afaik Anda tidak dapat menggunakan tanda kurung dengan __m128i. Masih sangat menarik. Baris pertama tampaknya mengatakan "ambil __m128i (I) yang disatukan dan xor dengan (parameter) i. Haruskah saya membaca ini sebagai inisialisasi I dengan 0 dan xor dengan i? Jika demikian, apakah akan sama dengan memuat I dengan i dan melakukan tidak (operasi) pada I?
Jan
@ Jan apa yang saya ingin lakukan adalah __m128i I = i; //set the lower 64 bits, tapi saya tidak bisa, jadi saya gunakan ^=. 0^1 = 1Oleh karena itu tidak ada tidak melibatkan. Mengenai inisialisasi dengan {}compiler saya tidak pernah mengeluh, ini mungkin bukan solusi terbaik, tetapi yang saya inginkan adalah menginisialisasi semuanya ke 0 sehingga saya dapat melakukan ^=atau |=. Saya rasa saya mendasarkan kode itu di posting blog ini yang juga memberikan pembalikan, sangat berguna: D
Wolfgang Brehm
6
Halaman ini mencantumkan beberapa fungsi hash sederhana yang cenderung lumayan secara umum, tetapi hash sederhana apa pun memiliki kasus patologis yang tidak berfungsi dengan baik.
Ada gambaran bagus tentang beberapa algoritma hash di Eternally Confuzzled . Saya akan merekomendasikan hash satu per satu Bob Jenkins yang dengan cepat mencapai longsoran salju dan oleh karena itu dapat digunakan untuk pencarian tabel hash yang efisien.
Itu adalah artikel yang bagus, tetapi difokuskan pada kunci string hashing, bukan integer.
Adrian Mouat
Hanya untuk memperjelas, meskipun metode dalam artikel akan berfungsi untuk bilangan bulat (atau dapat disesuaikan), saya berasumsi ada algoritma yang lebih efisien untuk bilangan bulat.
Adrian Mouat
2
Jawabannya bergantung pada banyak hal seperti:
Di mana Anda ingin menggunakannya?
Apa yang Anda coba lakukan dengan hash?
Apakah Anda memerlukan fungsi hash yang aman secara crytographically?
Saya menyarankan agar Anda melihat keluarga Merkle-Damgard dari fungsi hash seperti SHA-1 dll
Saya rasa kita tidak dapat mengatakan bahwa fungsi hash adalah "baik" tanpa mengetahui data Anda sebelumnya! dan tanpa mengetahui apa yang akan Anda lakukan dengannya.
Ada struktur data yang lebih baik daripada tabel hash untuk ukuran data yang tidak diketahui (saya berasumsi Anda melakukan hashing untuk tabel hash di sini). Saya pribadi akan menggunakan tabel hash ketika saya tahu saya memiliki sejumlah "terbatas" elemen yang perlu disimpan dalam jumlah memori terbatas. Saya akan mencoba dan melakukan analisis statistik cepat pada data saya, melihat bagaimana didistribusikan, dll sebelum saya mulai memikirkan tentang fungsi hash saya.
Untuk nilai hash acak, beberapa insinyur mengatakan bilangan prima rasio emas (2654435761) adalah pilihan yang buruk, dengan hasil pengujian saya, saya menemukan bahwa itu tidak benar; sebaliknya, 2654435761 mendistribusikan nilai hash dengan cukup baik.
Saya telah menulis program pengujian untuk mengevaluasi banyak fungsi hash untuk integer, hasilnya menunjukkan bahwa GRPrimeNumber adalah pilihan yang cukup bagus.
Saya telah mencoba:
total_data_entry_number / total_bucket_number = 2, 3, 4; di mana total_bucket_number = ukuran tabel hash;
memetakan domain nilai hash ke dalam domain indeks keranjang; yaitu, ubah nilai hash menjadi indeks keranjang dengan Logical And Operation dengan (hash_table_size - 1), seperti yang ditunjukkan dalam Hash_UInt_GRPrimeNumber ();
hitung jumlah tabrakan setiap ember;
catat ember yang belum dipetakan, yaitu ember kosong;
cari tahu jumlah tabrakan maksimal dari semua bucket; yaitu, rantai terpanjang;
Dengan hasil pengujian saya, saya menemukan bahwa Golden Ratio Prime Number selalu memiliki lebih sedikit ember kosong atau nol ember kosong dan panjang rantai tabrakan terpendek.
Beberapa fungsi hash untuk integer diklaim bagus, tetapi hasil pengujian menunjukkan bahwa ketika total_data_entry / total_bucket_number = 3, panjang rantai terpanjang lebih besar dari 10 (jumlah tabrakan maks> 10), dan banyak bucket tidak dipetakan (bucket kosong) ), yang sangat buruk, dibandingkan dengan hasil keranjang kosong nol dan panjang rantai terpanjang 3 oleh Golden Ratio Prime Number Hashing.
BTW, dengan hasil pengujian saya, saya menemukan satu versi fungsi hash shifting-xor yang cukup bagus (Ini dibagikan oleh mikera).
Tapi mengapa tidak menggeser produk dengan benar, jadi Anda menyimpan bit yang paling campuran? Begitulah seharusnya cara kerjanya
harold
1
@harold, bilangan prima rasio emas dipilih dengan hati-hati, meskipun saya pikir itu tidak akan membuat perbedaan apa pun, tetapi saya akan menguji untuk melihat apakah itu jauh lebih baik dengan "bit yang paling tercampur". Sementara maksud saya adalah bahwa "Ini bukan pilihan yang baik." tidak benar, seperti yang ditunjukkan oleh hasil pengujian, ambil saja bagian bawah bit sudah cukup baik, dan bahkan lebih baik daripada banyak fungsi hash.
Chen-ChungChia
(2654435761, 4295203489) adalah rasio emas bilangan prima.
Chen-ChungChia
(1640565991, 2654435761) juga merupakan rasio emas bilangan prima.
Chen-ChungChia
@harold, Menggeser produk ke kanan menjadi lebih buruk, meskipun hanya menggeser ke kanan dengan 1 posisi (dibagi 2), itu tetap menjadi lebih buruk (meskipun masih nol ember kosong, tetapi panjang rantai terpanjang lebih besar); bergeser ke kanan dengan lebih banyak posisi, hasilnya menjadi lebih buruk. Mengapa? Menurut saya alasannya adalah: menggeser produk dengan benar membuat lebih banyak nilai hash tidak menjadi coprime, tebakan saya, alasan sebenarnya melibatkan teori bilangan.
Chen-ChungChia
1
Saya telah menggunakan splitmix64(menunjuk pada jawaban Thomas Mueller ) sejak saya menemukan utas ini. Namun, saya baru-baru ini menemukan rrxmrrxmsx_0 Pelle Evensen , yang menghasilkan distribusi statistik yang jauh lebih baik daripada finalizer MurmurHash3 asli dan penerusnya ( splitmix64dan campuran lainnya). Berikut adalah potongan kode di C:
#include<stdint.h>staticinlineuint64_t ror64(uint64_t v,int r){return(v >> r)|(v <<(64- r));}uint64_t rrxmrrxmsx_0(uint64_t v){
v ^= ror64(v,25)^ ror64(v,50);
v *=0xA24BAED4963EE407UL;
v ^= ror64(v,24)^ ror64(v,49);
v *=0x9FB21C651E98DF25UL;return v ^ v >>28;}
Pelle juga memberikan analisis mendalam tentang mixer 64-bit yang digunakan pada langkah terakhir MurmurHash3dan varian yang lebih baru.
Fungsi ini tidak bersifat bijective. Untuk semua v dimana v = ror (v, 25) yaitu semua 0 dan semua 1 akan menghasilkan keluaran yang sama di dua tempat. Untuk semua nilai v = ror64 (v, 24) ^ ror64 (v, 49), yang setidaknya dua lebih banyak dan sama dengan v = ror (v, 28), menghasilkan 2 ^ 4 lagi, dengan total sekitar 22 tabrakan yang tidak perlu . Dua aplikasi splitmix mungkin sama bagus dan cepatnya, tetapi masih dapat dibalik dan bebas benturan.
Jawaban:
Metode perkalian Knuth:
Secara umum, Anda harus memilih pengali yang sesuai dengan urutan ukuran hash Anda (
2^32
dalam contoh) dan tidak memiliki faktor persekutuan dengannya. Dengan cara ini fungsi hash mencakup semua ruang hash Anda secara seragam.Sunting: Kerugian terbesar dari fungsi hash ini adalah ia mempertahankan pembagian, jadi jika semua bilangan bulat Anda habis dibagi 2 atau oleh 4 (yang tidak jarang), hash mereka juga akan habis. Ini adalah masalah dalam tabel hash - Anda bisa mendapatkan hanya 1/2 atau 1/4 ember yang digunakan.
sumber
Saya menemukan algoritme berikut memberikan distribusi statistik yang sangat baik. Setiap bit input mempengaruhi setiap bit output dengan probabilitas sekitar 50%. Tidak ada benturan (setiap masukan menghasilkan keluaran yang berbeda). Algoritmanya cepat kecuali jika CPU tidak memiliki unit perkalian integer built-in. Kode C, dengan asumsi
int
32 bit (untuk Java, ganti>>
dengan>>>
dan hapusunsigned
):Angka ajaib dihitung menggunakan program uji multi-utas khusus yang berjalan selama berjam-jam, yang menghitung efek longsoran (jumlah bit keluaran yang berubah jika satu bit masukan diubah; rata-rata harus hampir 16), independensi perubahan bit keluaran (bit keluaran tidak harus bergantung satu sama lain), dan kemungkinan perubahan pada setiap bit keluaran jika ada bit masukan yang diubah. Nilai yang dihitung lebih baik daripada finalizer 32-bit yang digunakan oleh MurmurHash , dan hampir sama baiknya (tidak cukup) seperti saat menggunakan AES . Sedikit keuntungannya adalah bahwa konstanta yang sama digunakan dua kali (itu membuatnya sedikit lebih cepat terakhir kali saya menguji, tidak yakin apakah itu masih terjadi).
Anda dapat membalikkan proses (mendapatkan nilai input dari hash) jika Anda mengganti
0x45d9f3b
dengan0x119de1f3
( pembalikan perkalian ):Untuk nomor 64-bit, saya sarankan untuk menggunakan yang berikut ini, meskipun menurut saya ini bukan yang tercepat. Yang ini didasarkan pada splitmix64 , yang tampaknya didasarkan pada artikel blog Better Bit Mixing (campuran 13).
Untuk Java, gunakan
long
, tambahkanL
konstanta, ganti>>
dengan>>>
dan hapusunsigned
. Dalam kasus ini, membalikkan lebih rumit:Pembaruan: Anda mungkin juga ingin melihat proyek Hash Function Prospector , di mana konstanta lain (mungkin lebih baik) terdaftar.
sumber
x = ((x >> 32) ^ x)
dan kemudian gunakan perkalian 32 bit di atas. Saya tidak yakin mana yang lebih baik. Anda mungkin juga ingin melihat finalizer 64-bit untuk Murmur3Tergantung pada bagaimana data Anda didistribusikan. Untuk penghitung sederhana, fungsi paling sederhana
akan bagus (saya kira optimal, tapi saya tidak bisa membuktikannya).
sumber
.hashCode()
, lihat di sini .Fungsi hash yang cepat dan baik dapat disusun dari permutasi cepat dengan kualitas yang lebih rendah, seperti
Untuk menghasilkan fungsi hashing dengan kualitas superior, seperti yang ditunjukkan dengan PCG untuk pembuatan nomor acak.
Ini sebenarnya juga resep rrxmrrxmsx_0 dan hash murmur digunakan, disadari atau tidak disadari.
Saya pribadi menemukan
untuk menjadi cukup baik.
Fungsi hash yang baik seharusnya
Pertama mari kita lihat fungsi identitas. Ini memenuhi 1. tapi tidak 2.:
Input bit n menentukan bit output n dengan korelasi 100% (merah) dan tidak ada yang lain, oleh karena itu bit input berwarna biru, memberikan garis merah sempurna.
Sebuah xorshift (n, 32) tidak jauh lebih baik, menghasilkan satu setengah baris. Masih memuaskan 1., karena bisa dibalik dengan aplikasi kedua.
Perkalian dengan unsigned integer jauh lebih baik, mengalir lebih kuat dan membalik lebih banyak bit keluaran dengan probabilitas 0,5, yang Anda inginkan, berwarna hijau. Ini memenuhi 1. karena untuk setiap bilangan bulat tidak rata ada pembalikan perkalian.
Menggabungkan keduanya menghasilkan keluaran berikut, 1. masih memuaskan karena komposisi dari dua fungsi bijektiva menghasilkan fungsi bijektiva yang lain.
Aplikasi perkalian dan xorshift kedua akan menghasilkan yang berikut:
Atau Anda dapat menggunakan perkalian medan Galois seperti GHash , perkalian tersebut telah menjadi cukup cepat pada CPU modern dan memiliki kualitas unggul dalam satu langkah.
sumber
__m128i I = i; //set the lower 64 bits
, tapi saya tidak bisa, jadi saya gunakan^=
.0^1 = 1
Oleh karena itu tidak ada tidak melibatkan. Mengenai inisialisasi dengan{}
compiler saya tidak pernah mengeluh, ini mungkin bukan solusi terbaik, tetapi yang saya inginkan adalah menginisialisasi semuanya ke 0 sehingga saya dapat melakukan^=
atau|=
. Saya rasa saya mendasarkan kode itu di posting blog ini yang juga memberikan pembalikan, sangat berguna: DHalaman ini mencantumkan beberapa fungsi hash sederhana yang cenderung lumayan secara umum, tetapi hash sederhana apa pun memiliki kasus patologis yang tidak berfungsi dengan baik.
sumber
Metode perkalian 32-bit (sangat cepat) lihat @rafal
32-bits dan 64-bits (distribusi yang baik) di: MurmurHash
sumber
Ada gambaran bagus tentang beberapa algoritma hash di Eternally Confuzzled . Saya akan merekomendasikan hash satu per satu Bob Jenkins yang dengan cepat mencapai longsoran salju dan oleh karena itu dapat digunakan untuk pencarian tabel hash yang efisien.
sumber
Jawabannya bergantung pada banyak hal seperti:
Saya menyarankan agar Anda melihat keluarga Merkle-Damgard dari fungsi hash seperti SHA-1 dll
sumber
Saya rasa kita tidak dapat mengatakan bahwa fungsi hash adalah "baik" tanpa mengetahui data Anda sebelumnya! dan tanpa mengetahui apa yang akan Anda lakukan dengannya.
Ada struktur data yang lebih baik daripada tabel hash untuk ukuran data yang tidak diketahui (saya berasumsi Anda melakukan hashing untuk tabel hash di sini). Saya pribadi akan menggunakan tabel hash ketika saya tahu saya memiliki sejumlah "terbatas" elemen yang perlu disimpan dalam jumlah memori terbatas. Saya akan mencoba dan melakukan analisis statistik cepat pada data saya, melihat bagaimana didistribusikan, dll sebelum saya mulai memikirkan tentang fungsi hash saya.
sumber
Untuk nilai hash acak, beberapa insinyur mengatakan bilangan prima rasio emas (2654435761) adalah pilihan yang buruk, dengan hasil pengujian saya, saya menemukan bahwa itu tidak benar; sebaliknya, 2654435761 mendistribusikan nilai hash dengan cukup baik.
Ukuran tabel hash harus pangkat dua.
Saya telah menulis program pengujian untuk mengevaluasi banyak fungsi hash untuk integer, hasilnya menunjukkan bahwa GRPrimeNumber adalah pilihan yang cukup bagus.
Saya telah mencoba:
Dengan hasil pengujian saya, saya menemukan bahwa Golden Ratio Prime Number selalu memiliki lebih sedikit ember kosong atau nol ember kosong dan panjang rantai tabrakan terpendek.
Beberapa fungsi hash untuk integer diklaim bagus, tetapi hasil pengujian menunjukkan bahwa ketika total_data_entry / total_bucket_number = 3, panjang rantai terpanjang lebih besar dari 10 (jumlah tabrakan maks> 10), dan banyak bucket tidak dipetakan (bucket kosong) ), yang sangat buruk, dibandingkan dengan hasil keranjang kosong nol dan panjang rantai terpanjang 3 oleh Golden Ratio Prime Number Hashing.
BTW, dengan hasil pengujian saya, saya menemukan satu versi fungsi hash shifting-xor yang cukup bagus (Ini dibagikan oleh mikera).
sumber
Saya telah menggunakan
splitmix64
(menunjuk pada jawaban Thomas Mueller ) sejak saya menemukan utas ini. Namun, saya baru-baru ini menemukan rrxmrrxmsx_0 Pelle Evensen , yang menghasilkan distribusi statistik yang jauh lebih baik daripada finalizer MurmurHash3 asli dan penerusnya (splitmix64
dan campuran lainnya). Berikut adalah potongan kode di C:Pelle juga memberikan analisis mendalam tentang mixer 64-bit yang digunakan pada langkah terakhir
MurmurHash3
dan varian yang lebih baru.sumber