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

57

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

H = k mod 11

$H = k \bmod \ 11$

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

H = k mod 12

$H = k \bmod \ 12$

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.

— CodyBugstein
źródło

Odpowiednie pytanie, dlaczego używamy xor w funkcji skrótu stackoverflow.com/questions/5889238/…

— shuva

62

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$

— Mario Cervera
źródło

Właśnie zobaczyłem, że moje zapytanie jest zgodne z twoją odpowiedzią. Czy uważasz, że funkcja skrótu w moim zapytaniu działa dobrze?

— nadmierna wymiana

@overexchange: Odpowiedziałem na twoje pytanie. Ta odpowiedź może Cię również zainteresować.

— Mario Cervera,

dlaczego tak jest, że wybór m ma znaczenie tylko wtedy, gdy K jest przekrzywiony? czy nie jest prawdą, że będziemy mieć gorszą wydajność przy złym m, nawet jeśli K jest równomiernie rozłożony?

— vorou

To zależy od tego, co rozumiesz przez „zły ”. Jeśli masz na myśli „mały w porównaniu do liczby elementów w tabeli skrótów” (tzn. Wysoki współczynnik obciążenia ), wówczas wydajność będzie niska. Jeśli jednak masz na myśli „nie pierwszą”, to fakt ten nie jest tak ważny, jeśli wszystkie klucze są jednakowo prawdopodobne, ponieważ zostaną rozmieszczone równomiernie w tabeli skrótów. Samo pytanie stanowi przykład.

m

$m$

— Mario Cervera,

16

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$

— Frafl
źródło

1

Ale jeśli moje klucze nie mają formy to nie ma znaczenia? Czy to prawda?

a + k \times b

$a + k \times b$

m

$m$

— CodyBugstein

1

@lmray, jeśli twoje klucze są równomiernie rozmieszczone, nie ma znaczenia. Jeśli nie są, to zależy od rozkładu dokładności, aby miał znaczenie, czy nie.

m

$m$

m

$m$

— AProgrammer

Właśnie cofnąłem ostatnią edycję, zapomniałem, że .

12 > 11

$12>11$

— frafl

3

Czy miałeś na myśli, że „przejdź do małego podzbioru segmentów iff dzieli ”?

b

$b$

m

$m$

— Michaił Dubow

8

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$

— Raphael
źródło

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.

— saadtaame
źródło