Która funkcja skrótu typu integer jest dobra, która akceptuje klucz mieszający w postaci liczby całkowitej?

Która funkcja skrótu typu integer jest dobra, która akceptuje klucz mieszający w postaci liczby całkowitej?

Metoda multiplikatywna Knutha:

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

Ogólnie rzecz biorąc, powinieneś wybrać mnożnik, który jest zgodny z rozmiarem twojego skrótu ( 2^32w przykładzie) i nie ma z nim wspólnych czynników. W ten sposób funkcja skrótu równomiernie pokrywa całą przestrzeń skrótu.

Edycja: Największą wadą tej funkcji skrótu jest to, że zachowuje podzielność, więc jeśli wszystkie liczby całkowite są podzielne przez 2 lub 4 (co nie jest rzadkością), ich skróty też będą. Jest to problem w tabelach haszujących - możesz skończyć z tylko 1/2 lub 1/4 używanych pojemników.

Odkryłem, że 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, z wyjątkiem sytuacji, gdy procesor nie ma wbudowanej jednostki mnożenia liczb całkowitych. Kod C, zakładając, że intjest 32 bitów (Java, zastępuje >>się >>>i usunięcia unsigned)

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

Magiczna liczba została obliczona za pomocą specjalnego wielowątkowego programu testowego, który działał przez wiele godzin, który oblicza efekt lawiny (liczba bitów wyjściowych, które zmieniają się przy zmianie jednego bitu wejściowego; powinna wynosić średnio prawie 16), niezależność zmiany bitów wyjściowych (bity wyjściowe nie powinny od siebie zależeć) oraz prawdopodobieństwo zmiany każdego bitu wyjściowego w przypadku zmiany dowolnego bitu wejściowego. Obliczone wartości są lepsze niż 32-bitowy finalizator używany przez MurmurHash i prawie tak samo dobre (niezupełnie), jak przy użyciu AES . Niewielką zaletą jest to, że ta sama stała jest używana dwukrotnie (przy ostatnim testowaniu przyspieszyło to nieco, nie jestem pewien, czy nadal tak jest).

Można odwrócić proces (uzyskać wartość wejściowy z hash), jeśli zastąpi 0x45d9f3bsię 0x119de1f3(w Liczba odwrotna ):

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

W przypadku liczb 64-bitowych sugeruję użycie następujących, nawet myśląc, że może nie być najszybszy. Ten jest oparty na splitmix64 , który wydaje się być oparty na artykule na blogu 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;
}

Java, użytkowania long, dodać Ldo stałej, wymienić >>z >>>i usunąć unsigned. W takim przypadku cofanie 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;
}

Aktualizacja: Możesz również przyjrzeć się projektowi Hash Function Prospector , w którym wymienione są inne (prawdopodobnie lepsze) stałe.

Zależy od sposobu dystrybucji danych. Prosty licznik to najprostsza funkcja

f(i) = i

będzie dobry (podejrzewam, że optymalny, ale nie mogę tego udowodnić).

Szybkie i dobre funkcje skrótu mogą składać się z szybkich permutacji o mniejszych właściwościach, takich jak

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

Aby uzyskać funkcję haszującą o doskonałych właściwościach, jak pokazano w przypadku PCG do generowania liczb losowych.

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

Osobiście znalazłem

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

być wystarczająco dobrym.

Dobra funkcja skrótu powinna

1. dążyć do tego, aby nie tracić informacji, jeśli to możliwe i mieć jak najmniej kolizji
2. kaskadować tak dużo i tak równomiernie, jak to możliwe, tj. każdy bit wejściowy powinien odwracać każdy bit wyjściowy z prawdopodobieństwem 0,5.

Przyjrzyjmy się najpierw funkcji tożsamości. Spełnia wymagania 1., ale nie 2.:

Bit wejściowy n określa wyjściowy bit n z korelacją 100% (czerwony) i żadnymi innymi, dlatego są one niebieskie, dając doskonałą czerwoną linię w poprzek.

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

Mnożenie przez liczbę całkowitą bez znaku jest znacznie lepsze, kaskaduje silniej i odwraca więcej bitów wyjściowych z prawdopodobieństwem 0,5, czyli tym, czego chcesz, na zielono. Spełnia 1., ponieważ dla każdej nieparzystej liczby całkowitej występuje odwrotność multiplikatywna.

Połączenie tych dwóch daje następujący wynik, wciąż spełniający 1., ponieważ połączenie dwóch funkcji bijektywnych daje kolejną funkcję bijektywną.

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

Lub możesz użyć mnożenia pól Galois, takich jak GHash , stały się one dość szybkie na nowoczesnych procesorach i mają doskonałe właściwości 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];                                              
   }

Ta strona zawiera listę kilku prostych funkcji skrótu, które generalnie są przyzwoite, ale każdy prosty skrót ma patologiczne przypadki, w których nie działa dobrze.

• 32-bitowa metoda multiplikatywna (bardzo szybka) patrz @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-bity i 64-bity (dobra dystrybucja) pod adresem: MurmurHash

• Funkcja mieszania liczb całkowitych

W Eternally Confuzzled znajduje się ładny przegląd niektórych algorytmów mieszania . Poleciłbym jednorazowy hash Boba Jenkinsa, który szybko osiąga lawinę i dlatego może być używany do wydajnego wyszukiwania tabeli skrótów.

Odpowiedź zależy od wielu rzeczy, takich jak:

• Gdzie zamierzasz go zatrudnić?
• Co próbujesz zrobić z haszem?
• Czy potrzebujesz kryptograficznie bezpiecznej funkcji skrótu?

Proponuję przyjrzeć się rodzinie funkcji skrótu Merkle-Damgard, takich jak SHA-1 itp

Nie sądzę, abyśmy mogli powiedzieć, że funkcja skrótu jest „dobra” bez wcześniejszej znajomości danych! i nie wiedząc, co z tym zrobisz.

Istnieją lepsze struktury danych niż tabele skrótów dla nieznanych rozmiarów danych (zakładam, że robisz haszowanie dla tabeli skrótów tutaj). Osobiście użyłbym tablicy mieszającej, gdy wiem, że mam „skończoną” liczbę elementów, które muszą być przechowywane w ograniczonej ilości pamięci. Spróbowałbym przeprowadzić szybką analizę statystyczną moich danych, zobaczyć, jak są one dystrybuowane itp., Zanim zacznę myśleć o mojej funkcji skrótu.

W przypadku losowych wartości skrótu niektórzy inżynierowie stwierdzili, że liczba pierwsza złotego podziału (2654435761) jest złym wyborem. Wyniki moich testów wykazały, że to nieprawda; zamiast tego 2654435761 dystrybuuje 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 tablicy mieszania musi być potęgą dwóch.

Napisałem program testowy do oceny wielu funkcji skrótu dla liczb całkowitych, wyniki pokazują, że GRPrimeNumber to całkiem dobry wybór.

Próbowałem:

1. total_data_entry_number / total_bucket_number = 2, 3, 4; gdzie total_bucket_number = rozmiar tablicy hash;
2. mapowanie domeny wartości skrótu do domeny indeksu zasobnika; to znaczy przekonwertuj wartość skrótu na indeks zasobnika przez operację logiczną i operacyjną z (hash_table_size - 1), jak pokazano w Hash_UInt_GRPrimeNumber ();
3. obliczyć liczbę kolizji każdego wiadra;
4. zapisz zasobnik, który nie został zmapowany, to znaczy pusty zasobnik;
5. znaleźć maksymalną liczbę kolizji wszystkich wiader; to znaczy najdłuższa długość łańcucha;

Z moich wyników testów stwierdziłem, że Golden Ratio Prime Number zawsze ma mniej pustych kubłów lub zero pustych kubłów i najkrótszą długość łańcucha kolizji.

Niektóre funkcje skrótu 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ższy łańcuch jest większy niż 10 (maksymalna liczba kolizji> 10), a wiele segmentów nie jest mapowanych (puste segmenty ), co jest bardzo złe w porównaniu z wynikiem zerowego pustego wiadra i najdłuższego łańcucha 3 przez Golden Ratio Prime Number Hashing.

Przy okazji, z wynikami moich testów stwierdziłem, że jedna wersja funkcji skrótu shifting-xor jest całkiem dobra (jest wspólna dla mikera).

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

Używam splitmix64(spiczasty Thomasa Muellera odpowiedzi ) odkąd znalazłem ten wątek. Jednak ostatnio natknąłem się na rrxmrrxmsx_0 Pelle Evensena , który dał znacznie lepszy rozkład statystyczny niż oryginalny finalizator MurmurHash3 i jego następcy ( splitmix64i inne miksy). 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żywanego w ostatnim etapie MurmurHash3i nowszych wariantach.