Dlaczego 5381 i 33 są tak ważne w algorytmie djb2?

Question

Funkcja mieszania dla ciągów znaków ma funkcję mieszania.

unsigned long hash = 5381; 
int c; 

while (c = *str++) 
    hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ 

Dlaczego 5381 i 33 są takie ważne?

Answer 1

Może dlatego, że 33 == 2^5 + 1 i wiele algorytmów mieszających używa ich mnożnika jako 2^n + 1?

zgłosił Jerome Berger

Aktualizacja:

To wydaje się być potwierdzone przez obecną wersję djb2 pakietu oprogramowania pochodzi z: cdb

Noty I związana opisać serce algorytm mieszający używający h = ((h << 5) + h)^c do wykonania mieszania ... x << 5 to szybki sposób na użycie 2^5 jako mnożnika.

Answer 2

W 5381 Dan Bernstein (djb2) mówi w this article:

[...] praktycznie każdy dobry mnożnik działa. Myślę, że niepokoisz się o to, że 31c + d nie obejmuje żadnego rozsądnego zakresu wartości skrótu , jeśli c i d są w zakresie od 0 do 255. To dlatego, gdy odkryłem z 33 funkcją skrótu i ​​zacząłem jej używać w moich kompresorach, zacząłem z wartością mieszającą 5381. Myślę, że przekonasz się, że to tak samo jak oraz mnożnik 261.

Cały wątek to here, jeśli jesteś zainteresowany.

Ozan Yigit ma a page on hash functions który mówi:

[...] magia liczby 33 (dlaczego to działa lepiej niż wiele innych stałych, premierów lub nie) nigdy nie zostały odpowiednio wyjaśnione.

Answer 3

Funkcja mieszająca jest podobny do Linear Congruential Generator (LCG - prosty klasa funkcji generuje szereg liczb pseudohalogenku losowych), która na ogół ma postać:

X = (a * X) + c; // "mod M", where M = 2^32 or 2^64 typically 

Uwaga podobieństwo do funkcja mieszania djb2 ... a = 33, M = 2^32. W rezultacie, aby LCG mieć „pełny okres” (tj losowo, ponieważ może być) muszą mieć pewne właściwości:

• A-1 jest podzielna przez czynniki-M (A 1 to 32, która jest dzielona przez 2, jedynym głównym czynnikiem 2^32)
• a-1 jest wielokrotnością 4 jeśli M jest wielokrotnością 4 (tak i tak)

Dodatkowo , c i M mają być względnie pierwsze (co będzie prawdziwe w przypadku nieparzystych wartości c).

Jak widać, ta funkcja hash przypomina nieco dobrą LCG.A jeśli chodzi o funkcje mieszania, potrzebujesz takiego, który tworzy "losowy" rozkład wartości skrótu, biorąc pod uwagę realistyczny zestaw ciągów wejściowych.

Co do tego, dlaczego ta funkcja hash jest dobra dla łańcuchów, myślę, że ma dobrą równowagę bycia niezwykle szybkim, a jednocześnie zapewnia rozsądną dystrybucję wartości skrótu. Ale widziałem wiele innych funkcji mieszania, które twierdzą, że mają znacznie lepsze właściwości wyjściowe, ale zaangażowane w wiele innych linii kodu. Na przykład zobacz: this page about hash functions

EDYCJA: This good answer wyjaśnia, dlaczego 33 i 5381 zostały wybrane z przyczyn praktycznych.

Answer 4

33 został wybrany, ponieważ:

1) Jak wspomniano powyżej, mnożenie jest łatwo obliczyć stosując przesunięcie uzupełnienia.

2) Jak widać z przesunięcia i dodania implementacji, użycie 33 powoduje wykonanie dwóch kopii większości bitów wejściowych w mieszalniku mieszającym, a następnie rozdziela te bity stosunkowo daleko od siebie. Pomaga to uzyskać dobre avalanching. Zastosowanie większej zmiany spowodowałoby powielenie mniejszej liczby bitów, użycie mniejszej zmiany spowodowałoby, że interakcje bitów stałyby się bardziej lokalne i wydłużenie interakcji trwa dłużej.

3) Przesunięcie 5 jest względnie pierwsze do 32 (liczba bitów w rejestrze), co pomaga w lawinowaniu. Mimo że w łańcuchu znaków jest wystarczająco dużo znaków, każdy bit bajtu wejściowego będzie w końcu wchodził w interakcje z każdym poprzednim bitem wejściowym.

4) Przesunięcie o 5 jest dobrą wartością przesunięcia przy rozważaniu danych znakowych ASCII. Znak ASCII może być traktowany jako 4-bitowy selektor typu i 4-bitowy selektor typu znakowego. Na przykład. wszystkie cyfry mają 0x3 w pierwszych 4 bitach. Tak więc 8-bitowa zmiana spowodowałaby, że bity o pewnym znaczeniu w większości oddziaływałyby z innymi bitami, które mają to samo znaczenie. Przesunięcie 4-bitowe lub 2-bitowe w podobny sposób wytworzy silne interakcje między podobnie myślącymi bitami. 5-bitowe przesunięcie powoduje, że wiele z czterech bitów niskiego rzędu danej postaci silnie oddziałuje z wieloma 4-wyższymi bitami tej samej postaci.

Jak podano w innym miejscu, wybór 5381 nie jest zbyt ważny i wiele innych opcji również powinno tu działać.

Nie jest to szybka funkcja mieszająca, ponieważ przetwarza ją wprowadzając znak na raz i nie próbuje używać paralelizmu na poziomie instrukcji. Łatwo jest jednak pisać. Jakość wyniku podzielona przez łatwość pisania kodu prawdopodobnie trafi w słodkie miejsce.

Na współczesnych procesorach mnożenie jest znacznie szybsze niż w chwili opracowania tego algorytmu, a inne czynniki mnożenia (np. 2^13 + 2^5 + 1) mogą mieć podobną wydajność, nieco lepszą wydajność i być nieco łatwiejsze pisać.

W przeciwieństwie do powyższej odpowiedzi, dobra funkcja kryptograficzna nie kryptograficzna nie chce generować losowego wyniku. Zamiast tego, biorąc pod uwagę dwa wejścia, które są prawie identyczne, chce produkować bardzo różne wyjścia. Jeśli twoje wartości wejściowe są losowo rozdzielone, nie potrzebujesz dobrej funkcji skrótu, możesz po prostu użyć dowolnego zestawu bitów ze swojego wejścia. Niektóre z nowoczesnych funkcji skrótu (Jenkins 3, Murmur, prawdopodobnie CityHash) dają lepszą dystrybucję wyników niż losowe dane wejściowe, które są bardzo podobne.