djb2 Hash Function

Question

Używam algorytm djb2 do wygenerowania klucza mieszania dla ciąg brzmi następująco

hash(unsigned char *str) 
{ 
    unsigned long hash = 5381; 
    int c; 

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

    return hash; 
} 

Teraz z każdej pętli nie jest mnożenie dwóch dużych liczb, Po pewnym czasie z 4 5th charakteru łańcucha jest przepełnienie jako wartość hash staje ogromny

Jaka jest prawidłowa droga byłaby tak że wartość hash nie przepełnić i mieszania się dzieje również prawidłowo

Answer 1

obliczeń hash często przepełnienia. Generalnie nie stanowi to problemu, o ile masz gwarancje, co się stanie, gdy przepełnienie zostanie przekroczone. Nie zapominaj, że punktem hash nie jest numer, który oznacza coś w kategoriach magniture itp. - to tylko sposób na wykrycie równości. Dlaczego przepełnienie przeszkadza w tym?

Answer 2

Nie powinieneś tego robić. Ponieważ nie ma modulo, przekroczenie liczby całkowitej jest oczekiwanym zachowaniem dla funkcji (i zostało zaprojektowane z myślą o niej). Dlaczego chcesz to zmienić?

Answer 3

Wydaje mi się, że używasz analizatora statycznego/uruchomieniowego do ostrzegania przed przepełnieniem całkowitym? To jeden z tych przypadków, w których można zignorować ostrzeżenie. Funkcje skrótu są przeznaczone dla określonych typów właściwości, więc nie martw się ostrzeżeniami z analizatora. Po prostu nie próbuj samodzielnie tworzyć funkcji mieszania!

Answer 4

powrót (hash & 0xFFFFFFFF); // lub jakakolwiek maska, którą chcesz, nie ma znaczenia, o ile zachowasz spójność.