Apa fungsi hash integer yang baik yang menerima kunci hash integer?

Jawaban:

47

Metode perkalian Knuth:

hash(i)=i*2654435761 mod 2^32

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.

Rafał Dowgird
sumber
36
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):

unsigned int hash(unsigned int 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 ):

unsigned int unhash(unsigned int 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.

Thomas Mueller
sumber
2
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).

erikkallen
sumber
3
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"
erikkallen
5
Itu sebenarnya implementasi Sun dari metode hashCode () di java.lang.Integer grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/…
Juande Carrion
5
@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(const uint64_t& n,int i){
  return n^(n>>i);
}
uint64_t hash(const uint64_t& n){
  uint64_t p = 0x5555555555555555ull; // pattern of alternating 0 and 1
  uint64_t c = 17316035218449499591ull;// random uneven integer constant; 
  return c*xorshift(p*xorshift(n,32),32);
}

untuk menjadi cukup baik.

Fungsi hash yang baik seharusnya

  1. bijective untuk tidak kehilangan informasi, jika mungkin dan memiliki tabrakan paling sedikit
  2. 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.:

fungsi identitas

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.

xorshift

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.

knuth

Menggabungkan keduanya menghasilkan keluaran berikut, 1. masih memuaskan karena komposisi dari dua fungsi bijektiva menghasilkan fungsi bijektiva yang lain.

knuth • xorshift

Aplikasi perkalian dan xorshift kedua akan menghasilkan yang berikut:

hash yang diusulkan

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_t const inline gfmul(const uint64_t& i,const uint64_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];                                              
   }
Wolfgang Brehm
sumber
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.

Tyler McHenry
sumber
6
  • Metode perkalian 32-bit (sangat cepat) lihat @rafal

    #define hash32(x) ((x)*2654435761)
    #define H_BITS 24 // Hashtable size
    #define H_SHIFT (32-H_BITS)
    unsigned hashtab[1<<H_BITS]  
    .... 
    unsigned slot = hash32(x) >> H_SHIFT
  • 32-bits dan 64-bits (distribusi yang baik) di: MurmurHash

  • Fungsi Integer Hash
tagihan
sumber
3

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.

Christoph
sumber
4
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

dirkgently
sumber
1

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.

Ouanixi
sumber
1

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.

#define MCR_HashTableSize 2^10

unsigned int
Hash_UInt_GRPrimeNumber(unsigned int key)
{
  key = key*2654435761 & (MCR_HashTableSize - 1)
  return key;
}

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:

  1. total_data_entry_number / total_bucket_number = 2, 3, 4; di mana total_bucket_number = ukuran tabel hash;
  2. 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 ();
  3. hitung jumlah tabrakan setiap ember;
  4. catat ember yang belum dipetakan, yaitu ember kosong;
  5. 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).

unsigned int Hash_UInt_M3(unsigned int key)
{
  key ^= (key << 13);
  key ^= (key >> 17);    
  key ^= (key << 5); 
  return key;
}
Chen-ChungChia
sumber
2
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>

static inline uint64_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.

Frederico Schardong
sumber
2
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.
Wolfgang Brehm