Pierwszą rzeczą, którą robisz podczas wstawiania / wycofywania z tabeli hash jest obliczenie hashCode dla podanego klucza, a następnie znalezienie właściwego bucket przez przycinanie hashCode do rozmiaru tabeli hashTable, wykonując hashCode % table_length. Oto 2 'wypowiedzi', które prawdopodobnie gdzieś przeczytałeś

1. Jeśli używasz potęgi 2 dla table_length, znalezienie (hashCode (klucz) % 2^n) jest tak proste i szybkie jak (hashCode (klucz) & (2^n -1)). Ale jeśli twoja funkcja do obliczania hashCode dla dany klucz nie jest dobry, na pewno będziesz cierpieć z powodu klastrowania wielu kluczy w kilku wiadrach hash.
2. ale jeśli używasz liczb pierwszych dla table_length, obliczone hashcody mogą mapować do różnych koszyków hashowych, nawet jeśli masz nieco głupią funkcję hashCode.

A oto dowód.

Jeśli Załóżmy, że twoja funkcja hashCode powoduje następujące hashcody m.in. {x , 2X, 3X, 4X, 5X, 6X...}, wtedy wszystkie te zostaną zgrupowane w zaledwie m Liczba wiadra, gdzie m = table_length/GreatestCommonFactor (table_length, x). (Sprawdzenie/wyprowadzenie tego jest trywialne). Teraz możesz wykonać jedną z następujących czynności, aby uniknąć klastrowania

Upewnij się, że nie generujesz zbyt wielu hashcodów, które są wielokrotnościami innego 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 niech m będzie równe table_length, czyniąc GreatestCommonFactor (table_length, x) równym 1, tzn. robiąc table_length coprime z x. i jeśli x może być dowolną liczbą, upewnij się, że table_length jest liczbą pierwszą.

From - http://srinvis.blogspot.com/2006/07/hash-table-lengths-and-prime-numbers.html

Http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

Dość jasne wyjaśnienie, ze zdjęciami też.

Edit: jako podsumowanie, liczby pierwsze są używane, ponieważ masz największe szanse na uzyskanie unikalnej wartości przy pomnożeniu wartości przez wybraną liczbę pierwszą i dodaniu ich wszystkich. Na przykład, jeśli dany ciąg znaków, pomnożenie każdej wartości literowej przez liczbę pierwszą, a następnie dodanie tych wszystkich do góry, da ci jego wartość hash.

A lepszym pytaniem byłoby, dlaczego dokładnie numer 31?

Tl;dr

index[hash(input)%2] spowoduje kolizję dla połowy wszystkich możliwych skrótów i zakresu wartości. index[hash(input)%prime] powoduje kolizję

Liczby pierwsze są używane, ponieważ masz duże szanse na uzyskanie unikalnej wartości dla typowej funkcji hash, która używa wielomianów modulo P. Powiedzmy, że używasz takiej funkcji hash dla ciągów o długości liczba pierwsza). Więc jeśli N jest znacznie mniejsza niż P, prawdopodobnie nie będziesz miał kolizji. Następnie, eksperyment może prawdopodobnie pokazać, że 37 jest wystarczająco duży, aby uniknąć kolizji dla tabeli hash ciągów o długości 5-10 i jest wystarczająco mały, aby użyć do obliczeń.

Aby zapewnić alternatywny punkt widzenia jest ta strona:

Http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth

Który twierdzi, że należy użyć jak największej liczby łyżek w przeciwieństwie do zaokrąglania w dół do pierwszej liczby łyżek. To rozsądna możliwość. Intuicyjnie, na pewno widzę, jak większa liczba wiader byłaby lepsza, ale nie jestem w stanie przedstawić matematycznego argumentu na ten temat.

To zależy od wyboru funkcji hash.

Wiele funkcji skrótu łączy różne elementy danych, mnożąc je przez kilka współczynników modulo moc dwóch odpowiadających wielkości słowa maszyny (ten moduł jest wolny, pozwalając na przepełnienie obliczeń).

Nie chcesz mieć wspólnego czynnika między mnożnikiem dla elementu danych a rozmiarem tabeli hash, ponieważ wtedy może się zdarzyć, że zmienność elementu danych nie rozłoży danych na cały stół. Jeśli wybierzesz prime dla wielkości stołu, taki wspólny czynnik jest bardzo mało prawdopodobny.

Z drugiej strony, te czynniki zwykle składają się z nieparzystych liczb pierwszych, więc powinieneś być bezpieczny używając potęg dwóch dla swojej tabeli hash (np. Eclipse używa 31, gdy generuje metodę Java hashCode ()).

Liczby pierwsze są liczbami unikalnymi. Są to unikalny w tym, produkt prime z każdym innym numerem ma najlepsze szansa bycia unikalnym (nie tak unikalnym jako sam prime of-course) ze względu na fakt, że prime jest używany do skomponuj to. Ta właściwość jest wykorzystywana w funkcje haszujące.

Biorąc pod uwagę ciąg znaków "Samuel", możesz Wygeneruj unikalny hash przez mnożenie każda z cyfr składowych lub litery z liczbą pierwszą i dodawanie w górę. Dlatego primes są używane.

Jednak używanie primes jest starym technika. Klucz do zrozumienia że tak długo, jak można wygenerować wystarczająco unikalny klucz, który możesz przenieść do innych technik haszujących. Idź. tutaj znajdziesz więcej na ten temat o http://www.azillionmonkeys.com/qed/hash.html

Http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

Załóżmy, że rozmiar tabeli (lub liczba modulo) wynosi T=(B * C). Jeśli hash dla Twojego wejścia jest podobny (N * A * B), gdzie N może być dowolną liczbą całkowitą, to twoje wyjście nie będzie dobrze rozłożone. Ponieważ za każdym razem n staje się C, 2C, 3C itp., Twoje wyniki zaczną się powtarzać. tzn. Twoje wyniki będą dystrybuowane tylko w pozycjach C. Zauważ, że C tutaj jest (T / HCF (table-size, hash)).

Ten problem można wyeliminować, wykonując HCF 1. Liczby pierwsze są do tego bardzo dobre.

Inny ciekawostką jest to, że gdy T wynosi 2^n. to daje wyjście dokładnie takie samo jak wszystkie niższe N bitów input-hash. Ponieważ każda liczba może być reprezentowana potęgami 2, gdy weźmiemy modulo dowolnej liczby z T, odejmujemy wszystkie potęgi 2 postaci liczby, które są > = n, stąd zawsze oddajemy liczbę określonego wzoru, zależną od wejścia. To również zły wybór.

Podobnie, t jak 10^N jest złe również z podobnych powodów (wzór w zapisie dziesiętnym liczb zamiast binary).

Tak więc liczby pierwsze mają tendencję do lepszego rozłożenia wyników, dlatego są dobrym wyborem dla wielkości tabeli.

Kopiowanie z mojej innej odpowiedzi https://stackoverflow.com/a/43126969/917428 . Zobacz go po więcej szczegółów i przykładów.

• 8 % 10 = 8
• 18 % 10 = 8
• 87865378 % 10 = 8

Nie ma znaczenia, jaka jest Liczba: tak długo, jak kończy się na 8, jego modulo 10 będzie 8.

Wybranie wystarczająco dużej liczby Nie-mocy dwóch upewni się, że funkcja skrótu rzeczywiście jest funkcją wszystkich bitów wejściowych, a nie ich podzbiorem.

Chciałbym coś dodać do odpowiedzi Steve ' a Jessopa(nie mogę tego skomentować, ponieważ nie mam wystarczającej reputacji). Ale znalazłem pomocne materiały. Jego odpowiedź jest bardzo pomocna, ale popełnił błąd: rozmiar wiadra nie powinien być mocą 2. Cytuję tylko z książki" Wprowadzenie do algorytmu " Thomasa Cormena, Charlesa Leisersena i innych na stronie 263:

Używając metody dzielenia, Zwykle unikamy pewnych wartości m. na przykład, m nie powinno być potęgą 2, ponieważ jeśli m = 2^p, To h (k) jest tylko P bitami najniższego rzędu k. Jeśli nie wiemy, że wszystkie p-bitowe wzorce niskiego rzędu są równie prawdopodobne, lepiej zaprojektować funkcję skrótu tak, aby zależała od wszystkich bitów klucza. Ponieważ ćwiczenie 11.3-3 wymaga pokazania, wybór m = 2^p-1, gdy k jest ciągiem znaków interpretowanym w radix 2^p może być złym wyborem, ponieważ permutowanie znaków k nie zmienia jego wartości hash.

Mam nadzieję, że to pomoże.

"naturą matematyki" w odniesieniu do modułów mocy pierwszej jest to, że są one jednym elementem składowym skończonego pola. Pozostałe dwa elementy konstrukcyjne to operacja dodawania i mnożenia. Szczególną właściwością modułów pierwszych jest to, że tworzą skończone pole z" regularnymi " operacjami dodawania i mnożenia, przyjętymi do modułu. Oznacza to, że każde mnożenie odwzorowuje inną liczbę całkowitą modulo liczby pierwszej, podobnie jak każde dodawanie.

Prime moduli są korzystne ponieważ:

• dają największą swobodę przy wyborze mnożnika wtórnego w hashowaniu wtórnym, wszystkie mnożniki z wyjątkiem 0 będą odwiedzać wszystkie elementy dokładnie raz
• jeśli wszystkie skróty są mniejsze niż moduł nie będzie kolizji w ogóle
• losowe liczby pierwsze mieszają się lepiej niż potęga dwóch moduli i kompresują informacje o wszystkich bitach, a nie tylko podzbiorze

Mają jednak duży minus, wymagają podziału całkowitego, który zajmuje wiele (~ 15-40) cykli, nawet na nowoczesnym procesorze. Przy około połowie obliczeń można upewnić się, że hash jest bardzo dobrze wymieszany. Dwa mnożenia i operacje xorshift będą się lepiej mieszać niż moudulus. Następnie możemy użyć dowolnego rozmiaru tabeli hash, a redukcja skrótu jest najszybsza, dając w sumie 7 operacji dla mocy 2 rozmiarów tabeli i około 9 operacji dla dowolnych rozmiarów.

Przejrzałem ostatnio wiele najszybszych implementacji tabel hashowych i większość z nich nie używa prime moduli.

Rozkład indeksów tabeli skrótów zależy głównie od używanej funkcji skrótu. moduł prime nie może naprawić złej funkcji hash, a dobra funkcja hash nie korzysta z modułu prime. są jednak przypadki, w których mogą być korzystne. Może na przykład naprawić pół-złą funkcję skrótu.

Dla funkcji skrótu ważne jest nie tylko zminimalizowanie kolizyjności, ale także uniemożliwienie pozostawania z tym samym Hashem podczas chaningu kilku bajtów.

Powiedz, że masz równanie: (x + y*z) % key = x z 0<x<key i 0<z<key. Jeśli klucz jest liczbą pierwotną n * y=klucz jest true dla każdego n W N I false dla każdej innej liczby.

Przykład, w którym key nie jest pierwszym przykładem: x= 1, z = 2 i klucz=8 Ponieważ klucz / z=4 jest nadal liczbą naturalną, 4 staje się rozwiązaniem naszego równania i w tym przypadku (n/2) * y = klucz jest prawdziwy dla każdego n W N. ilość rozwiązań dla równania podwoiła się, ponieważ 8 nie jest liczbą pierwszą.

Jeśli nasz atakujący wie już, że 8 jest możliwym rozwiązaniem równania, może zmienić plik z 8 na 4 i nadal otrzymuje ten sam hash.

Przeczytałem popularną witrynę wordpress podlinkowaną w niektórych z powyższych popularnych odpowiedzi na górze. Z tego, co zrozumiałem, chciałbym podzielić się prostą obserwacją.

Wszystkie szczegóły znajdziesz w artykule tutaj , ale załóżmy, że tak jest:

• użycie liczby pierwszej daje nam "największą szansę" na unikalną wartość

Ogólna implementacja hashmap chce, aby 2 rzeczy były unikalne.

• unikalny Kod hashowy dla klucza
• unikalny indeks do przechowywania rzeczywistej wartości

Jak uzyskać unikalny indeks? Przez co początkowy rozmiar wewnętrznego pojemnika również jest prime. Więc w zasadzie, prime jest zaangażowany, ponieważ posiada tę unikalną cechę wytwarzania unikalnych liczb, które ostatecznie używamy do identyfikowania obiektów i znajdowania indeksów wewnątrz wewnętrznego Pojemnik.

Przykład:

Klucz = "Klucz"

Value = " Wartość" uniqueId = "k" * 31 ^ 2 + "e" * 31 ^ 1` + "y"

Maps to unique id

Teraz chcemy unikalnej lokalizacji dla naszej wartości - więc my

uniqueId % internalContainerSize == uniqueLocationForValue , zakładając, że internalContainerSize jest również liczbą pierwszą.

To pytanie zostało połączone z bardziej odpowiednim pytaniem, Dlaczego tabele hash powinny używać tablic wielkości pierwszej, a nie potęgi 2. Dla samych funkcji hashowych jest tu wiele dobrych odpowiedzi, ale na powiązane pytanie, dlaczego niektóre tabele hashowe o krytycznym znaczeniu dla bezpieczeństwa, takie jak glibc, używają tablic wielkości pierwszej, nie ma ich jeszcze.

Ogólnie moc 2 tabel są znacznie szybsze. Tam droga h % n => h & bitmask, gdzie maska bitowa może być obliczona przez clz ("Policz wiodące zera") o rozmiarze N. A funkcja modulo musi wykonać dzielenie liczb całkowitych, które jest około 50x wolniejsze niż logiczne and. Istnieje kilka sztuczek, aby uniknąć modulo, jak użycie Lemire ' s https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction / , ale ogólnie szybkie tabele hash używają mocy 2, A bezpieczne tabele hash używają wartości primes.

Bezpieczeństwo w tym przypadku jest definiowane przez ataki na strategię rozwiązywania kolizji, która jest w większości tabel hash tylko Wyszukiwanie liniowe w linkowanych lista kolizji. Lub z szybszym wyszukiwaniem liniowym tabel z adresacją otwartą bezpośrednio w tabeli. Tak więc z mocą 2 tabel i pewną wewnętrzną znajomością tabeli, np. rozmiarem lub kolejnością listy kluczy dostarczanych przez jakiś interfejs JSON, otrzymujesz liczbę użytych prawych bitów. Liczba jedynek na maskach bitowych. Zwykle jest to mniej niż 10 bitów. A dla 5-10 bitów trywialne jest zderzenie siłowe nawet z najsilniejszymi i najwolniejszymi funkcjami hashowymi. Nie dostajesz pełnego bezpieczeństwo Twoich 32-bitowych lub 64-bitowych funkcji hashowych. Chodzi o to, aby używać szybkich, małych funkcji hashowych, a nie potworów, takich jak szmer, a nawet syf.

Więc jeśli dostarczasz zewnętrzny interfejs do tabeli hash, jak rozwiązywanie DNS, język programowania, ... chcesz dbać o nadużycia ludzi, którzy lubią DOS takich usług. Zwykle łatwiej jest takim ludziom zamknąć swoją służbę publiczną za pomocą znacznie łatwiejszych metod, ale tak się stało. Więc ludziom zależało.

Więc najlepsze opcje zapobiegania takim atakom kolizji są albo

1) używać tabel prime, ponieważ wtedy

• wszystkie 32 lub 64 bity są istotne, aby znaleźć wiadro, a nie tylko kilka.
• funkcja zmiany rozmiaru tabeli hash jest bardziej naturalna niż tylko Podwójna. Najlepszą funkcją wzrostu jest ciąg Fibonacciego i liczby pierwsze zbliżają się do tego niż do podwojenia.

2) używaj lepszych środków przeciwko faktycznemu atakowi, wraz z szybką mocą 2 rozmiarów.

• count kolizje i przerywanie lub uśpienie wykrytych ataków, czyli liczby kolizji z prawdopodobieństwem
• konwersja połączonej listy kolizji do drzewa za pomocą wyszukiwania O (log n), A NIE O(n), gdy wykryty zostanie atak kolizji. To właśnie robi np. java.

Istnieje szeroko rozpowszechniony mit, że bezpieczniejsze funkcje hash pomagają zapobiegać takim atakom, co jest błędne, jak wyjaśniłem. Nie ma Bezpieczeństwo tylko z niskimi bitami. To działa tylko z tabel wielkości prime, ale to będzie używać kombinacji dwóch najwolniejszych metod, slow hash plus slow Prime modulo.

Funkcje skrótu dla tabel skrótu muszą być przede wszystkim małe (aby mogły być połączone) i szybkie. Bezpieczeństwo może wynikać tylko z zapobiegania liniowym poszukiwaniom w kolizjach. I nie używać trywialnie złych funkcji hashowych, takich jak te niewrażliwe na pewne wartości (np. \0 podczas mnożenia).

Używanie losowych nasion jest również dobra opcja, ludzie zaczęli od tego jako pierwsi, ale z wystarczającą ilością informacji o tabeli nawet losowe ziarno nie pomaga zbyt wiele, a dynamiczne języki zazwyczaj sprawiają, że trywialne jest uzyskanie nasion za pomocą innych metod, ponieważ są one przechowywane w znanych miejscach pamięci.

Powiedziałbym, że pierwsza odpowiedź na ten link jest najjaśniejszą odpowiedzią, jaką znalazłem w związku z tym pytaniem.

Rozważmy zestaw kluczy K = {0,1,...,100} oraz tabelę hash, w której liczba wiader wynosi m = 12 . Od 3 jest czynnikiem 12, klucze, które są wielokrotnościami 3 zostaną zahaszowane do wiadra, które są wielokrotnościami 3:

• Klucze {0,12,24,36,... zostanie zaszyfrowany do bucket 0.
• Klucze {3,15,27,39,... zostanie zahaszowany do wiadra 3.
• Klucze {6,18,30,42,... zostanie zahaszowany do wiadra 6.
• Klucze {9,21,33,45,... zostanie zahaszowany do wiadra 9.

Jeśli K jest równomiernie rozłożona (tj. każdy klucz w K jest równie prawdopodobne), wtedy wybór m nie jest tak krytyczny. Ale co się stanie, jeśli K nie jest równomiernie rozłożone? Wyobraź sobie, że klucze, które najczęściej występują wielokrotności 3. W tym przypadku wszystkie wiadra, które nie są wielokrotnościami 3 będzie pusty z dużym prawdopodobieństwem(co jest naprawdę złe pod względem wydajności tabeli hash).

Ta sytuacja jest bardziej powszechna, niż może się wydawać. Wyobraź sobie na przykład, że śledzisz obiekty na podstawie tego, gdzie są przechowywane w pamięci. Jeśli rozmiar słowa twojego komputera wynosi cztery bajty, będziesz mieszał klucze, które są wielokrotnościami 4. Nie trzeba dodawać, że wybór m jest wielokrotnością 4 to byłby straszny wybór: miałbyś 3M/4 wiadra całkowicie puste, a wszystkie Twoje klucze kolidują z pozostałymi wiadrami m/4.

Ogólnie:

Każdy klucz W K, który ma wspólny czynnik z liczbą łyżek m, zostanie zahaszowany do łyżki, która jest wielokrotnością tego współczynnika.

Dlatego, aby zminimalizować kolizje, ważne jest, aby zmniejszyć liczbę wspólne czynniki między m A elementami K. Jak można to osiągnąć? Wybierając m jako liczbę, która ma bardzo niewiele czynników: liczba pierwsza .

Z odpowiedzi autorstwa Mario.