funkcja hash dla string

Po pierwsze, zazwyczaj nie chcesz użyć kryptograficznego skrótu dla tabeli skrótów. Algorytm, który jest Bardzo Szybki według standardów kryptograficznych, jest nadal potwornie powolny przez standardy tabel hashowych.

Po Drugie, chcesz mieć pewność, że każdy bit Wejścia może / wpłynie na wynik. Jednym z łatwych sposobów na to jest obrócenie bieżącego wyniku o pewną liczbę bitów, a następnie XOR bieżącego kodu skrótu z bieżącym bajtem. Powtarzaj, aż dojdziesz do końca łańcucha. Uwaga że zazwyczaj nie chcesz, aby obrót był nawet wielokrotnością rozmiaru bajtu.

Na przykład, zakładając powszechną Wielkość 8 bitów bajtów, można obrócić o 5 bitów:

int hash(char const *input) { 
    int result = 0x55555555;

    while (*input) { 
        result ^= *input++;
        result = rol(result, 5);
    }
}

Edit: należy również pamiętać, że 10000 slotów rzadko jest dobrym wyborem dla rozmiaru tabeli hash. Zwykle potrzebujesz jednej z dwóch rzeczy: albo chcesz liczbę pierwszą jako rozmiar (wymagany do zapewnienia poprawności przy niektórych rodzajach rozdzielczości skrótu), albo moc 2 (więc zmniejszenie wartości do poprawnej zakres można wykonać za pomocą prostej maski bitowej).

Istnieje wiele implementacji hashtable dla języka C, od standardowej biblioteki C hcreate/hdestroy/hsearch, po te w Apr i glib, które również dostarczają prebuiltowanych funkcji hashowych. Zdecydowanie polecam używanie tych, a nie wymyślanie własnej funkcji hashtable lub hash; zostały one zoptymalizowane pod kątem typowych przypadków użycia.

Jeśli jednak twój zbiór danych jest statyczny, najlepszym rozwiązaniem jest prawdopodobnie użycie perfect hash . gperf będzie Wygeneruj idealny hash dla danego zbioru danych.

Wikipedia pokazuje ładną funkcję hashową o nazwie Jenkins po kolei Hash. Cytuje również ulepszone wersje tego hasha.

uint32_t jenkins_one_at_a_time_hash(char *key, size_t len)
{
    uint32_t hash, i;
    for(hash = i = 0; i < len; ++i)
    {
        hash += key[i];
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
    return hash;
}

Po pierwsze, to 40 kolizji dla 130 słów hashowanych do 0..99 źle? Nie możesz oczekiwać doskonałego hashowania, jeśli nie podejmujesz kroków specjalnie dla tego. Zwykła funkcja hash nie będzie miała mniej kolizji niż generator losowy przez większość czasu.

Funkcja hash o dobrej reputacji to MurmurHash3 .

Wreszcie, jeśli chodzi o rozmiar tabeli hash, to naprawdę zależy, jaki rodzaj tabeli hash masz na myśli, zwłaszcza, czy wiadra są rozszerzalne lub jednorzędowe. Jeśli łyżki są rozszerzalne, ponownie istnieje wybór: wybierasz średnią długość łyżki dla ograniczeń pamięci/prędkości, które masz.

Próbowałem tych funkcji hashowych i otrzymałem następujący wynik. Mam około 960 ^ 3 wpisy, każdy 64 bajty długości, 64 znaki w innej kolejności, wartość hash 32bit. Kody z Tutaj .

Hash function  |  collision rate | how many minutes to finish
MurmurHash3    |    6.?%         |       4m15s
Jenkins One..  |    6.1%         |       6m54s   
Bob, 1st in link|   6.16%        |       5m34s
SuperFastHash  |    10%          |       4m58s
bernstein      |    20%          | 14s only finish 1/20
one_at_a_time  |    6.16%        |       7m5s
crc            |    6.16%        |       7m56s

Dziwną rzeczą jest to, że prawie wszystkie funkcje hash mają współczynnik kolizji 6% dla moich danych.

Choć djb2, ponieważ zaprezentowane na stackoverflow przez cnicutar , jest prawie na pewno lepsze, myślę, że warto też pokazać K & R hashes:

unsigned long hash(unsigned char *str)
{
    unsigned int hash = 0;
    int c;

    while (c = *str++)
        hash += c;

    return hash;
}

2) prawdopodobnie całkiem przyzwoity algorytm hashowy, jak przedstawiono w k & r Wersja 2 (zweryfikowany przeze mnie na pg. 144 księgi); uwaga: Należy usunąć % HASHSIZE z deklaracji powrotu, jeśli planujesz zrobić rozmiar modułu do długości tablicy poza algorytmem hash. Ponadto, zalecam wykonanie typu return i" hashval " unsigned long zamiast prostego unsigned (int).

unsigned hash(char *s)
{
    unsigned hashval;

    for (hashval = 0; *s != '\0'; s++)
        hashval = *s + 31*hashval;
    return hashval % HASHSIZE;
}

Zauważ, że z dwóch algorytmów wynika, że jednym z powodów, dla których hash pierwszej edycji jest tak straszny, jest to, że nie bierze pod uwagę znaków kolejność , więc hash("ab") zwróci tę samą wartość co hash("ba"). To jest a nie więc z 2 wydaniem hash, jednak, który byłby (znacznie lepiej!) zwraca dwie różne wartości dla tych łańcuchów.

GCC C++11 funkcji hashujących używanych do unordered_map (Szablon tabeli hash) oraz unordered_set (szablon hash set) wygląda następująco.

• W 2007 roku, w ramach projektu "The Sims 2008", w ramach projektu "The Sims 2009", w ramach projektu "The Sims 2009", w ramach projektu "The Sims 2009", w ramach projektu "The Sims 2009", w ramach projektu "The Sims 2009", w ramach projektu "The Sims 2009" w ramach projektu "The Sims 2009" w ramach projektu "The Sims 2009" w ramach projektu "The Sims 2009" w ramach projektu "The Sims 2009" ( http://murmurhash.googlepages.com/).
• w pliku "gcc / libstdc++ - v3 / libsupc++/hash_bytes.cc", tutaj ( https://github.com/gcc-mirror/gcc/blob/master/libstdc++ - v3 / libsupc++/hash_bytes.cc ), znalazłem implementacje. Oto przykład dla zwracanej wartości" 32-bit size_t " (pobranej 11 sierpnia 2017):

Kod:

// Implementation of Murmur hash for 32-bit size_t.
size_t _Hash_bytes(const void* ptr, size_t len, size_t seed)
{
  const size_t m = 0x5bd1e995;
  size_t hash = seed ^ len;
  const char* buf = static_cast<const char*>(ptr);

  // Mix 4 bytes at a time into the hash.
  while (len >= 4)
  {
    size_t k = unaligned_load(buf);
    k *= m;
    k ^= k >> 24;
    k *= m;
    hash *= m;
    hash ^= k;
    buf += 4;
    len -= 4;
  }

  // Handle the last few bytes of the input array.
  switch (len)
  {
    case 3:
      hash ^= static_cast<unsigned char>(buf[2]) << 16;
      [[gnu::fallthrough]];
    case 2:
      hash ^= static_cast<unsigned char>(buf[1]) << 8;
      [[gnu::fallthrough]];
    case 1:
      hash ^= static_cast<unsigned char>(buf[0]);
      hash *= m;
  };

  // Do a few final mixes of the hash.
  hash ^= hash >> 13;
  hash *= m;
  hash ^= hash >> 15;
  return hash;
}

Jedna rzecz, której używałem z dobrymi wynikami jest następująca(Nie wiem, czy już o niej wspomniano, bo nie pamiętam jego nazwy).

Obliczasz tabelę T z losową liczbą dla każdego znaku w alfabecie Twojego klucza [0,255]. Masz klucz " k0 k1 k2 ... kN ' biorąc T [k0] xor T [k1] xor ... xor T [kN]. Możesz łatwo pokazać, że jest to tak losowe, jak generator liczb losowych i jego obliczeniowo bardzo wykonalne, a jeśli naprawdę napotkasz bardzo złą instancję z dużą ilością kolizje możesz po prostu powtórzyć całość za pomocą świeżej partii losowych liczb.