Powiel możliwe:
Why should hash functions use a prime number modulus?Tabela mieszania: dlaczego rozmiar powinien być najlepszy?
Dlaczego jest to konieczne (struktury danych) tabeli mieszania za rozmiar, aby być głównym?
Z tego co rozumiem, zapewnia bardziej równomierną dystrybucję, ale czy istnieje jakikolwiek inny powód?
Jedynym powodem jest uniknięcie grupowania wartości w niewielką liczbę segmentów (tak, dystrybucja). Bardziej równomiernie rozkładany hashtable będzie działał bardziej konsekwentnie.
z http://srinvis.blogspot.com/2006/07/hash-table-lengths-and-prime-numbers.html
Jeśli załóżmy wyniki funkcyjnych hashCode w następujących hashCodes m.in. {x, 2x, 3x, 4x, 5x, 6x ...}, a następnie wszystko to będzie skupione w tylko liczba m kubełków, gdzie m = table_length/GreatestCommonFactor (table_length, x). (Sprawdzenie/wyprowadzenie tego jest trywialne). Teraz można wykonać jedną z następujących czynności, aby uniknąć klasteringu
Upewnij się, że nie generuje zbyt wiele hashCodes które są wielokrotnością innej hashcode jak w {x, 2x, 3x, 4x, 5x, 6x. ..} Ale może to być trudne, jeśli twój hashTable ma mieć miliony wpisów.
Lub po prostu ustaw m równy długości table_length przez uczynienie GreatestCommonFactor (table_length, x) równym 1, tj. Przez zrobienie table_length coprime zx. Jeśli x może być dowolną liczbą, upewnij się, że długość_tabeli jest liczbą pierwszą.
Niż domyślam się, że moje zrozumienie było słuszne: Unikaj grupowania <=> Uzyskaj lepszą dystrybucję. Dobrze? Dzięki za referencję. –
@Olivier Lalonde, jeśli to odpowiedział na twoje pytanie, proszę oznaczyć je jako odpowiedź. –
Cokolwiek hashfunction użyć masz całkowitą. Aby zmapować to do tablicy hashtable, zwykle musisz mieć mod liczbę całkowitą z rozmiarem hali, aby ta wartość była mniejsza niż rozmiar tabeli, aby ją zmapować.
powrót hashVal% tableSize
jestem nieco zagubiony od tego momentu, ale IIRC jeśli tableSize jest parzysta, wszystkie wpisy będą jeszcze. Połowa twojego hashtable nigdy nie zostanie wypełniona.
To kolejna dobra uwaga. I uważam, że powodem do premiery jest zmniejszenie ryzyka wzorców (na przykład 10, 20, 30, 40, które wszystkie dają 0, jeśli tableSize = 10) w hashVal, co może skutkować nierówną dystrybucją, jak wspomina @Sam . –
347% 20 to 7, a nawet nie. –
To jest duplikat [Dlaczego funkcje skrótu używają modułu liczb pierwszych?] (Http://stackoverflow.com/questions/1145217/why-should-hash-functions-use-a-prime-number-modulus) - pierwszy link w sekcji "Powiązane" na pasku bocznym - i myślę, że [zaakceptowana odpowiedź] (http://stackoverflow.com/questions/1145217/why-should-hash-functions-use-a-prime- number-modulus/1147232 # 1147232) jest bardzo dobry. –
Powinieneś przyjąć odpowiedź. – gwg