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

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

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.

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.

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).

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.:

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_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];                                              
   }

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.

• 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

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.

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.

#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;
}

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.