Jaka funkcja hashowa integer jest dobra, która akceptuje klucz hashowy integer?

Znalazłem następujący algorytm zapewnia bardzo dobry rozkład statystyczny. Każdy bit wejściowy wpływa na każdy bit wyjściowy z około 50% prawdopodobieństwem. Nie ma kolizji (każde wejście skutkuje innym wyjściem). Algorytm jest szybki, chyba że procesor nie ma wbudowanej jednostki mnożenia całkowitej. Kod C, zakładając, że int jest 32-bitowy (w przypadku Javy zastąp >> na >>> i usuń unsigned):

unsigned int hash(unsigned int x) {
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = (x >> 16) ^ x;
    return x;
}

Liczba magiczna została obliczona za pomocą specjalnego testu wielowątkowego program, który działał przez wiele godzin, który oblicza efekt lawinowy (liczba bitów wyjściowych, które zmieniają się w przypadku zmiany pojedynczego bitu wejściowego; powinna wynosić średnio prawie 16), niezależność zmian bitów wyjściowych (bity wyjściowe nie powinny zależeć od siebie) i prawdopodobieństwo zmiany każdego bitu wyjściowego, jeśli jakikolwiek bit wejściowy zostanie zmieniony. Obliczone wartości są lepsze niż 32-bitowy finalizer używany przez MurmurHash , i prawie tak dobre (nie całkiem) jak przy użyciu AES. Lekką zaletą jest to, że ta sama stała jest używana dwa razy (zrobiła to nieco szybciej ostatnim razem, gdy testowałem, Nie wiem, czy nadal tak jest).

Możesz odwrócić proces (pobrać wartość wejściową z hasha), jeśli zastąpisz 0x45d9f3b 0x119de1f3 (mnożnik odwrotny):

unsigned int unhash(unsigned int x) {
    x = ((x >> 16) ^ x) * 0x119de1f3;
    x = ((x >> 16) ^ x) * 0x119de1f3;
    x = (x >> 16) ^ x;
    return x;
}

Dla liczb 64-bitowych, proponuję użyć następującego, nawet pomyślałem, że może nie być najszybszy. Ten jest oparty na splitmix64 , który wydaje się być oparty na blogu article Better Bit Mixing (mix 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;
}

W Javie użyj long, dodaj L do stałej, zamień >> na >>> i usuń unsigned. W tym przypadku odwrócenie jest bardziej skomplikowane:

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

Update: warto również przyjrzeć się projektowi hash function Prospector , w którym wymienione są inne (być może lepsze) stałe.

Zależy od sposobu dystrybucji danych. Dla prostego licznika najprostsza Funkcja

f(i) = i

Będzie dobre (podejrzewam, że optymalne, ale nie mogę tego udowodnić).

Szybkie i dobre funkcje hash mogą być złożone z szybkich permutacji o słabszych właściwościach, takich jak

• mnożenie przez nieparzystą liczbę całkowitą
• rotacje binarne
• xorshift

Aby uzyskać funkcję haszującą o wyższych właściwościach, jak pokazano w PCG dla generowania liczb losowych.

W rzeczywistości jest to również przepis rrxmrrxmsx_0 i murmur hash używają, świadomie lub nieświadomie.

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

Dobra funkcja hash powinna

1. BYĆ bijektywnym, aby nie stracić informacji, jeśli to możliwe i mieć najmniej kolizji
2. kaskada tak bardzo i tak równomiernie, jak to możliwe, tzn. każdy bit wejściowy powinien odwrócić każdy bit wyjściowy z prawdopodobieństwem 0,5.

Bit wejściowy N określa bit wyjściowy n z korelacją 100% (czerwony) i nie ma innych, są więc niebieskie, dając idealną czerwoną linię w poprzek.

Xorshift (N,32) nie jest dużo lepszy, dając półtorej linii. Nadal satysfakcjonujące 1., ponieważ jest odwracalny przy drugim zastosowaniu.

Mnożenie przez niepodpisaną liczbę całkowitą jest znacznie lepsze, mocniejsze kaskadowanie i przerzucanie większej ilości bitów wyjściowych z prawdopodobieństwem 0,5, czyli to, co chcesz, na Zielono. Spełnia 1. jak dla każdej nierównej liczby całkowitej istnieje multiplikatywna odwrotność.

Połączenie tych dwóch daje następujące wyjście, nadal spełniające 1. ponieważ skład dwóch funkcji bijektywnych daje inną funkcję bijektywną.

Drugie zastosowanie mnożenia i xorshift daje następujące:

Albo można użyć mnożenia pól Galois jak GHash , stały się one dość szybkie na nowoczesnych procesorach i mają doskonałe cechy w jednym kroku.

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

• 32-bitowa metoda multiplikatywna (bardzo szybka) patrz @Rafał

  #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 and 64-bits (good distribution) at: MurmurHash

• Integer Hash Function

Ta strona zawiera listę prostych funkcji hashowych, które zazwyczaj są przyzwoite, ale każdy prosty hash ma patologiczne przypadki, w których nie działa dobrze.

Jest ładny przegląd niektórych algorytmów hashowych w wiecznie Konfuzzled. Polecam jeden na raz hash Boba Jenkinsa, który szybko dociera do avalanche i dlatego może być używany do efektywnego wyszukiwania tabel hashowych.

Odpowiedź zależy od wielu rzeczy takich jak:

Gdzie zamierzasz go zatrudnić? Co chcesz zrobić z tym Haszem?
• Czy potrzebujesz crytograficznie zabezpieczonej funkcji hash?

Proponuję rzucić okiem na Merkle-Damgard rodzinę funkcji hashowych, takich jak SHA-1 itp

Nie sądzę, że możemy powiedzieć, że funkcja hash jest "dobra" bez uprzedniej znajomości Twoich danych ! i nie wiedząc, co z tym zrobisz.

Istnieją lepsze struktury danych niż tabele haszujące dla nieznanych rozmiarów danych(zakładam, że robisz tutaj haszowanie dla tabeli haszującej). Osobiście użyłbym tabeli hash, gdy Wiem, że mam "skończoną" liczbę elementów, które wymagają przechowywania w ograniczonej ilości pamięci. Postaram się zrobić szybką analizę statystyczną na moim dane, zobaczyć jak jest rozprowadzany itp zanim zacznę myśleć o mojej funkcji hash.

Dla losowych wartości skrótu, niektórzy inżynierowie powiedzieli, że golden ratio liczba pierwsza (2654435761) jest złym wyborem, z moimi wynikami testów stwierdziłem, że to nieprawda; zamiast tego, 2654435761 rozkłada wartości skrótu całkiem dobrze.

#define MCR_HashTableSize 2^10

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

Rozmiar tabeli hash musi być potęgą dwóch.

Napisałem program testowy do oceny wielu funkcji hashowych dla liczb całkowitych, wyniki pokazują, że GRPrimeNumber jest całkiem dobrym wyborem.

Próbowałem:

1. total_data_entry_number / total_bucket_number = 2, 3, 4; where total_bucket_number = hash table size;
2. Mapuj domenę wartości hash do domeny indeksu bucket; to znaczy Konwertuj wartość hash na indeks bucket za pomocą logicznego i operacji za pomocą (hash_table_size - 1), Jak pokazano w Hash_UInt_GRPrimeNumber ();
3. oblicz liczbę kolizji każdego wiadra;
4. Zapisz wiadro, które nie zostało zmapowane, czyli puste wiadro;
5. znajdź maksymalną liczbę kolizji wszystkich wiadrów, czyli najdłuższa długość łańcucha;

Z moich wyników badań, odkryłem, że złoty stosunek liczba pierwsza zawsze ma mniej pustych wiadra lub zero pustego wiadra i najkrótszą długość łańcucha kolizji.

Niektóre funkcje hashujące dla liczb całkowitych są uważane za dobre, ale wyniki testów pokazują, że gdy total_data_entry / total_bucket_number = 3, najdłuższa długość łańcucha jest większa niż 10(Maksymalna liczba kolizji > 10), a wiele łyżek nie jest mapowanych( puste łyżki), co jest bardzo złe, w porównaniu z wynikiem zerowej pustej łyżki i najdłuższej długości łańcucha 3 przez złoty stosunek liczby pierwszej.

BTW, z moich wyników testów, znalazłem jedną wersję shifting - XOR hash functions jest całkiem dobry (jest współdzielony przez mikera).

unsigned int Hash_UInt_M3(unsigned int key)
{
  key ^= (key << 13);
  key ^= (key >> 17);    
  key ^= (key << 5); 
  return key;
}

Używam splitmix64 (wskazanego w odpowiedzi Thomasa Muellera ) odkąd znalazłem ten wątek. Jednak ostatnio natknąłem się na Rrxmrrxmsx_0 Pelle Evensen, który dał znacznie lepszy rozkład statystyczny niż oryginalny Finalizer MurmurHash3 i jego następcy (splitmix64 i inne mixy). Oto fragment kodu w 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 zapewnia również dogłębną analizę 64-bitowego miksera użytego w końcowym etapie MurmurHash3 i więcej Ostatnie warianty.