Szukam funkcji szybkiego mieszania o dobrej (tj. Prawie równomiernej) dystrybucji do użycia w implementacji tabeli mieszania.Algorytm mieszania dla implementacji tabeli mieszania
Tablica haszów będzie używana wyłącznie do przechowywania wartości za pomocą klawisza liczby całkowitej.
Czy mogę użyć mniejszych bitów liczby całkowitej jako skrótu?
np. Int key = n & 15; i stworzyć tablicę z 16 slotami do ich przechowywania.
Jakieś rekomendacje?
Widać tutaj xxhash
Twój wspomniano funkcja skrótu jest bardzo szybki, ale jest też bardzo źle. Jeśli chcesz mieć "głupią" funkcję skrótu, możesz wziąć pod uwagę moduł.
przykład:
int key = item % size_of_hash_table
Dlaczego "to" jest złe? –
No ostatniej nocy się wszechstronne badania mieszania (w C), który obejmuje kilka hashers najwyższej pistolet i 38 różnych kluczy.
Wszyscy są mile widziane odniesienia go pod adresem: http://www.overclock.net/t/1319572/benchmarking-the-fastest-hash-function/0_20#post_18495990
Byłbym szczęśliwy dla ujawniając jak Intel vs AMD i Intel 12.1 kompilator vs Microsoft 16 (VS2010) kombinacje kompilatora zachowywać z twoją pomocą.
Nie ma czegoś takiego jak idealna funkcja skrótu. Jeśli jednak potrzebujesz pewnych algorytmów z odpowiednim kodem źródłowym, zobacz tutaj: http://partow.net/programming/hashfunctions/index.html –
Podejmowanie najniższych bitów jest prawdopodobnie najgorszą rzeczą do zrobienia. (ale: wszystko zależy od zakresu wartości, których można się spodziewać w kluczu int) Spróbuj również wymieszać górne bity lub pomnóż z dużą liczbą (nieparzysta, pierwsza). Wiedz, czego się spodziewać i zmierzyć. – wildplasser
Dodaj komentarz jako odpowiedź, a ja to zaakceptuję. –