Dlaczego najlepiej używać liczby pierwszej jako modu w funkcji skrótu?

Jeśli mam listę kluczowych wartości od 1 do 100 i chcę je uporządkować w szeregu 11 segmentów, nauczono mnie tworzyć funkcję mod

Teraz wszystkie wartości zostaną umieszczone jeden po drugim w 9 rzędach. Na przykład w pierwszym segmencie będzie $0, 11, 22 \dots$ . W drugim będą $1, 12, 23 \dots$ itp.

Powiedzmy, że zdecydowałem się być złym chłopcem i jako funkcję skrótu używam non-prime - weź 12. Korzystanie z funkcji mieszania

spowoduje tablicę skrótów o wartościach $0, 12, 24 \dots$ w pierwszym segmencie, $1, 13, 25 \dots$ itp. w drugim i tak dalej.

Zasadniczo są one tym samym. Nie zmniejszyłem liczby kolizji i nie rozłożyłem się lepiej, używając kodu skrótu liczby głównej i nie widzę, jak to zawsze jest korzystne.

Rozważmy zestaw kluczy $K=\{0,1,...,100\}$ i tablicę skrótów, gdzie liczba segmentów wynosi $m=12$ . Ponieważ $3$ jest współczynnikiem $12$ , klucze, które są wielokrotnościami $3$ zostaną zamienione na segmenty, które są wielokrotnościami $3$ :

• Klucze $\{0,12,24,36,...\}$ zostaną zaszyfrowane do segmentu $0$ .
• Klucze zostaną zaszyfrowane w segmencie .$\{3,15,27,39,...\}$$3$
• Klucze zostaną zaszyfrowane do segmentu .$\{6,18,30,42,...\}$$6$
• Klucze zostaną zaszyfrowane do segmentu .$\{9,21,33,45,...\}$$9$

Jeśli jest równomiernie rozmieszczone (tzn. Każdy klucz w jest równie prawdopodobne, że wystąpi), to wybór nie jest tak istotny. Ale co się stanie, jeśli nie będzie równomiernie rozłożone? Wyobraź sobie, że najbardziej prawdopodobne są klucze wielokrotności . W takim przypadku wszystkie segmenty, które nie są wielokrotnościami będą puste z dużym prawdopodobieństwem (co jest naprawdę złe pod względem wydajności tabeli skrótów).$K$$K$$m$$K$$3$$3$

Ta sytuacja jest bardziej powszechna, niż może się wydawać. Wyobraź sobie na przykład, że śledzisz obiekty w oparciu o miejsce ich przechowywania w pamięci. Jeśli rozmiar słowa twojego komputera wynosi cztery bajty, będziesz mieszał klucze, które są wielokrotnościami . Nie trzeba dodawać, że wybranie jako wielokrotności byłoby okropnym wyborem: miałbyś całkowicie puste wiadra, a wszystkie klucze zderzyłyby się z pozostałymi wiadrami .$4$$m$$4$$3m/4$$m/4$

Ogólnie:

Każdy klucz w który dzieli wspólny czynnik z liczbą segmentów zostanie skrócony do segmentu będącego wielokrotnością tego czynnika.$K$$m$

W związku z tym, aby zminimalizować kolizji, to ważne jest, aby zmniejszyć ilość czynników wspólnych pomiędzy i elementów . Jak można to osiągnąć? Wybierając aby być liczbą, która ma bardzo mało czynników: liczba pierwsza .$m$$K$$m$

To, czy kolizja jest mniej prawdopodobna przy użyciu liczb pierwszych, zależy od dystrybucji kluczy.

Jeśli wiele twoich kluczy ma postać a twoja funkcja skrótu to , to klucze te przechodzą do małego podzbioru segmentów iff dzieli . Powinieneś więc zminimalizować liczbę takich , które można osiągnąć wybierając liczbę pierwszą.$a+k\cdot b$$H(n)=n \bmod m$$b$$n$$b$

Z drugiej strony, jeśli chcesz mieć od do segmentów i wiesz, że różnice będące wielokrotnościami są bardziej prawdopodobne niż różnice, które są wielokrotnościami i , możesz wybrać dla swojego specjalnego zastosowania.$11$$12$$11$$2$$3$$12$

To, czy ma to wpływ (także), zależy od tego, jak traktujesz kolizje. W przypadku niektórych wariantów otwartego mieszania użycie liczb pierwszych gwarantuje, że puste miejsca są znalezione, o ile tabela jest wystarczająco pusta.

Spróbuj na przykład pokazać:

Załóżmy, że chcemy wstawić element mieszający, aby rozwiązać adres i rozwiązać kolizje, wypróbowując kolejno pozycje dla .$a$$a + i^2$$i=1,2,\dots$

Pokaż, że ta procedura zawsze daje pustą pozycję, jeśli tablica skrótu ma rozmiar , pierwsza większa niż , a co najmniej połowa wszystkich pozycji jest wolna.$p$$p$$3$

Wskazówka: Użyj faktu, że moduł resztkowy pierścienia modulo jest polem, jeśli jest liczbą pierwszą, a zatem ma co najwyżej rozwiązania.$p$$p$$i^2=c$$2$

Jeśli twoja funkcja skrótu ma postać gdzie jest liczbą pierwszą, a jest wybierane losowo, wówczas prawdopodobieństwo, że 2 różne klucze skrótu do tego samego segmentu wynoszą . Tak więc dla , co jest bardzo małe.$h(k)=a\times k \mod m$$m$$a$$1\over m$$m=1009$$Pr\{h(x)=h(y), x\neq y\}=0.00099108027$

Ten schemat jest znany jako: Universal Hashing.