Masz dobrą funkcję hash dla tabeli hashowej C++?

Ten prosty wielomian działa zaskakująco dobrze. Dostałem go od Paula Larsona z Microsoft Research, który studiował szeroką gamę funkcji skrótu i mnożników skrótu.

unsigned hash(const char* s, unsigned salt)
{
    unsigned h = salt;
    while (*s)
        h = h * 101 + (unsigned) *s++;
    return h;
}

salt powinna być zainicjalizowana do wybranej wartości losowo przed utworzeniem hashtable w celu obrony przed atakamitabela hash . Jeśli nie jest to dla Ciebie problemem, po prostu użyj 0.

Rozmiar tabeli jest również ważny, aby zminimalizować kolizje. Wygląda na to, że twoja jest w porządku.

Boost.Functional / Hash może Ci się przydać. Nie próbowałem, więc nie mogę ręczyć za jego wydajność.

Boost posiada również bibliotekę CRC .

Spojrzałbym na .Unordered first (tj. boost:: unordered_map). Używa map hash zamiast drzew binarnych dla kontenerów.

Wydaje mi się, że niektóre implementacje STL mają kontener hash_map w przestrzeni nazw stdext.

Rozmiar Twojej tabeli będzie określał, jakiego rozmiaru hasha powinieneś użyć. Oczywiście chcesz zminimalizować kolizje. Nie jestem pewien, co określasz przez elementy max i pojemność (wydają mi się to samo) w każdym przypadku, które z tych liczb sugerują, że 32 bitowy hash byłby wystarczający. Możesz uciec z CRC16 (~65,000 możliwości), ale prawdopodobnie będziesz miał wiele kolizji do czynienia. Z drugiej strony kolizja może być szybsza niż CRC32 hash.

Powiedziałbym, idź z CRC32. Nie zabraknie dokumentacji i przykładowego kodu. Ponieważ masz swoje maksimum zorientowane i szybkość jest priorytetem, przejdź z tablicy wskaźników. Użyj skrótu do wygenerowania indeksu. Przy kolizji, inkrementuj indeks, aż trafisz w puste wiadro.. szybko i prosto.

Ponieważ przechowujesz angielskie słowa, większość twoich znaków będzie literami i nie będzie wiele różnic w najważniejszych dwóch bitach Twoich danych. Poza tym chciałbym zachować to bardzo proste, po prostu za pomocą XOR. W końcu nie szukasz siły kryptograficznej, ale tylko rozsądnie równomiernej dystrybucji. Coś w tym stylu:

size_t hash(const std::string &data) {
  size_t h(0);
  for (int i=0; i<data.length(); i++)
    h = (h << 6) ^ (h >> 26) ^ data[i];
  }
  return h;
}

Poza tym, czy patrzyłeś na STD::tr1::hash jako funkcję haszującą i / lub STD:: tr1:: unordered_map jako implementację hasz table? Korzystanie z nich byłoby prawdopodobnie zaoszczędzić wiele pracy w przeciwieństwie do wdrażania własnych klas.

Priorytetem mojej tabeli hash jest szybkie wyszukiwanie (pobieranie).

Dobrze więc używasz odpowiedniej struktury danych, ponieważ wyszukiwanie w tabeli hash jest O (1)! :)

A może coś prostego:

// Initialize hash lookup so that it maps the characters
// in your string to integers between 0 and 31
int hashLookup[256];

// Hash function for six character strings.
int hash(const char *str)
{
    int ret = 0, mult = 1;
    for (const char *p = str; *p; *p++, mult *= 32) {
        assert(*p >= 0 && *p < 256);
        ret += mult * hashLookup[*p];
    }

    return ret;
}

Zakłada to 32-bitowe ints. Używa 5 bitów na znak, więc wartość hash ma tylko 30 bitów. Można to naprawić, być może, generując sześć bitów dla pierwszego jednego lub dwóch znaków. Jeśli zestaw znaków jest wystarczająco mały, możesz potrzebować nie więcej niż 30 bitów.

Jeśli potrzebujesz przeszukać krótkie ciągi i wstawianie nie jest problemem, może przydałoby się drzewo B, lub drzewo 2-3, w Twoim przypadku nie zyskasz wiele przez haszowanie.

Sposób, w jaki to zrobisz, polega na umieszczeniu litery w każdym węźle, więc najpierw sprawdzasz węzeł "a", następnie sprawdzasz dzieci "a"dla "p", a dzieci dla "p", a następnie "l" i "e". W sytuacjach, gdy masz "apple" I "apply", musisz szukać ostatniego węzła, (ponieważ jedyna różnica jest w ostatnim " e" i "y")

Ale w większości przypadków będziesz w stanie uzyskać słowo po kilku krokach ("ksylofon" => "x"->"ylofon"), więc możesz zoptymalizować w ten sposób. Może to być szybsze niż hashowanie

Od C++11, C++ dostarcza std::hash< string >( string ). Jest to prawdopodobnie wydajna funkcja haszująca, która zapewnia dobry rozkład kodów haszujących dla większości łańcuchów.

Ponadto, jeśli myślisz o zaimplementowaniu tabeli hash, powinieneś teraz rozważyć użycie C++ std::unordered_map zamiast tego.