Dlaczego Rozmiar 127 (prime) jest lepszy niż 128 dla tabeli hash?

Metoda Podziału

" stosując metodę podziału, Zwykle unikamy pewnych wartości m (wielkość tabeli). Na przykład, M nie powinno być potęgą 2, ponieważ jeśli M = 2p, wtedy h(k) jest tylko p bitami najniższego rzędu k."

--CLRS

Aby zrozumieć, dlaczego m = 2p używa tylko p najniższych bitów k, musisz najpierw zrozumieć funkcję modulo hash h(k) = k % m.

Klucz można zapisać w postaci ilorazu q, a pozostałe r.

k = nq + r

Wybór ilorazu na q = m pozwala nam zapisać k % m po prostu jako resztę w powyższym równaniu:

k % m = r = k - nm,  where r < m

Dlatego {[16] } jest równoważne ciągłemu odejmowaniu m sumy n razy (do r < m):

k % m = k - m - m - ... - m,  until r < m

Spróbujmy zahaszować klucz k = 91 za pomocą m = 24 = 16.

  91 = 0101 1011
- 16 = 0001 0000
----------------
  75 = 0100 1011
- 16 = 0001 0000
----------------
  59 = 0011 1011
- 16 = 0001 0000
----------------
  43 = 0010 1011
- 16 = 0001 0000
----------------
  27 = 0001 1011
- 16 = 0001 0000
----------------
  11 = 0000 1011

Tak więc, 91 % 24 = 11 jest tylko binarną formą 91 z tylko p=4 najniższymi bitami.

Ważne Rozróżnienie:

Odnosi się to w szczególności do metody podziałuhaszowania. W rzeczywistości konwersja jest prawdziwa dla metody mnożenia , jak podano w CLRS:

"zaletą metody mnożenia jest to, że wartość m nie jest krytyczna... Zazwyczaj wybieramy [m] jako moc 2, ponieważ możemy łatwo zaimplementować tę funkcję na większości komputerów."

Nick ma rację, że ogólnie wielkość tabeli hash nie ma znaczenia. Jednak w szczególnym przypadku, gdy stosuje się adresację otwartą z podwójnym hashowaniem (w którym interwał między sondami jest obliczany przez inną funkcję hashową), to tabela hashowa o rozmiarze liczb pierwszych jest najlepsza, aby zapewnić, że wszystkie wpisy w tabeli hash są dostępne dla nowego elementu (jak wspomniano Corkscreewe.)

Po pierwsze, nie chodzi o wybranie liczby pierwszej. Na przykład, jeśli wiesz, że twój zestaw danych będzie w zakresie od 1 do 10 000, wybranie 127 lub 128 nie zrobi różnicy bc to kiepski wybór projektu.

Raczej lepiej wybrać naprawdę duży prime, taki jak 3967 dla Twojego przykładu, aby każde dane miały swoją unikalną parę klucz / wartość. Chcesz również zminimalizować kolizje. Wybranie 127 lub 128 dla Twojego przykładu nie zrobi różnicy bc wszystkie wiadra 127/128 będą jednolicie filled (jest to złe i obniża czas wykonania wstawiania i Wyszukiwania O(1) do O (n)) w przeciwieństwie do 3967(które zachowa czas wykonania o (1))

EDIT # 4

Konstrukcja "funkcji hashowej" jest coś w stylu czarnej sztuki. Może być duży wpływ na dane, które przeznaczone do przechowywania w struktura danych oparta na hashowaniu, więc dyskusja na temat sensownego hashowania funkcja może często błądzić w dyskusja na temat konkretnych wejść.

Jako dlaczego pierwsze są "preferowane", ma się rozważenie analizy "przeciwnika", przypuśćmy, że zaprojektowałem generała. struktura danych oparta na hashowaniu, jak czy będzie działać, biorąc pod uwagę najgorszy wkład od przeciwnika. Od wykonania jest podyktowane hashowaniem kolizji pytanie staje się co to jest hash do zastosowanie, które minimalizuje kolizję w najgorszy stan. Jednym z takich warunków jest gdy wejściami są zawsze liczby podzielna przez liczbę całkowitą, powiedzmy 4. Jeśli używasz N = 128 wtedy dowolna liczba podzielna przez 4 mod 128 jest nadal podzielna przez 4, co oznacza tylko wiadra 4, 8, 12, ... are always ever stosowane, co skutkuje 25% wykorzystaniem struktura danych. Primes skutecznie zmniejsza prawdopodobieństwo takich scenariusz występujący, z liczbami > N.

Jeśli masz idealną funkcję hash, która ma równomierną dystrybucję, to nie ma to znaczenia.

Wikipedia rzeczywiście ma dobre podsumowanie tego:

Http://en.wikipedia.org/wiki/Hash_table

Zwracają uwagę, że niektóre funkcje skrótu są zaprojektowane do działania tylko z liczbami pierwszymi. Ten artykuł wyjaśnia, dlaczego potęgi dwóch są złe:

Http://www.concentric.net / ~Ttwang/tech/primehash.htm

Nie mogę już tego udowodnić, chociaż pamiętam, że musiałem to zrobić na egzaminie na Uniwersytecie milion lat temu, ale optymalne rozmiary haszyszu to nie tylko prime. Chcesz wybrać liczbę pierwszą N taką, że N = 4*M − 1 (gdzie M jest również liczbą całkowitą).

Jak już mówiłem, nie pamiętam już matematyki, aby to udowodnić. Informatyka był na kursie teoretycznym prowadzonym przez Rachel Manber, żonę Udi, jakieś 25 lat temu.

Oto sposób na zrozumienie " k % 127 zależy od wszystkich bitów K. K % 128 zależy tylko od 7 najniższych bitów." .
k % 128 jest równe k &(2^7-1).na przykład: 129% 128 = 1 , w systemie binarnym: 1000 0001 & 0111 1111 =0000 0001,każdy bit wysokości (2^7-1) będzie równy 0, co oznacza, że nie ma znaczenia, jaka jest wysoka pozycja. ale ten przekład jest nieprawidłowy dla liczb, które nie są równe 2^n.
teraz przyjrzyjmy się, jak robimy podział dziesiętny 129 % 127, najpierw przyjrzyjmy się najwyższej pozycji 1, mniej niż 127, następnie otrzymujemy następny punkt 2 Połącz z pięścią otrzymujemy 12, 12 jest mniejsze niż 127, następnie połącz z 9 co oznacza 129, dzielone przez 127 reszta to 2, możemy to napisać w matematyce: 129 = 1 * 127 +2 , więc mamy 2[wszystko to nazywa się Long_division] i jest to samo w podziale binarnym, teraz wiemy, że k % 127 zależy od wszystkich bitów k

Wierzę, że ma to związek z tym, że komputery działają w bazie 2. Coś podobnego dzieje się z bazą 10.

...

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 podzbiór.

z dlaczego tabele hash powinny używać wielkości liczby pierwszej .