Hashcode obliczenie dlaczego pomnożyć i ignorować bity przepełnienia?

Question

To pytanie nie dotyczy tego, dlaczego mnoży się, co jest dość oczywiste - chodzi o dystrybucję.

Why use a prime number in hashCode?

Ale raczej jest to więcej o jedną właściwość rozmnażania, że ​​staje się ważniejsza im więcej czynników są zawarte w formule obliczania hashcode.

Proste obliczenie oczywiście może spowodować przelanie, ale to ma niewielkie znaczenie.

a * 31 + b 

Prawdziwy problem jest demonstrowany, gdy wiele elementów znajduje się we wzorze.

((a * 31) + b) * 31 ... 6n. 

Gdy więcej niż 5 lub 6 terminy mają obejmować wartości pierwszego wyrazu jest utracone bitami ma przelew do czasu wartość hashcode wynosi do w tym określenie 5+. Korzystając z tego systemu, tylko ostatnie 5 takich określeń jest naprawdę znaczącym czynnikiem przyczyniającym się do ostatecznej wartości.

31^7 > Integer.MAX_VALUE 

Dlaczego więc większość obliczeń nie obraca bitów, które przelewają się z powrotem i Xor w/dolnych bitów wyniku. Rozumiem, że wymaga to trochę błahotu, a obliczenia muszą być wykonywane przy użyciu longów (64-bitowych), aby 32-bitowe 32-bitowe mogły być XOR-ami z wynikiem całkowitym, ale co najmniej żadne bity nie zostałyby utracone.

Czy istnieje jakiś szczególny powód, dla którego przepełnienie jest ignorowane? Nie jest to tak kosztowne, aby używać tak długo, jak opisano wcześniej.

EDIT

100000*31^7=   2751261411100000  0x9C641F717C560 
6553600000*31^7 180306667837849600000 0xC641F717C5600000 

Zauważ, że ta ostatnia wartość jest dokładnie 65536 razy większy niż poprzedni, co oznacza również, że jego odpowiedź jest 16 bitów większe. Zauważ, że całkowita wartość 0xC641F717C5600000 to 0xC5600000, rzeczywiste znaczące wartości są tracone z 16-bitowej wartości.

*SAMPLE A* 
65536*4096*27512614111 

=7385361114638319616 
=0x667E12CDF0000000 
    12345678 
=0xF0000000 

*SAMPLE B* 
9*65536*4096*27512614111 

=66468250031744876544 
=0x9A6EA93D70000000 
    12345678 
=0x70000000 

Zauważmy, że górna najbardziej bit Próbka B który jest dokładnie 9x próbka A sprawia, że ​​niemal absolutną żadnej różnicy w wartości końcowej 32 bit - gdybym zmienił 9x na 17x następnie dolne bity byłoby identyczny. Jednak jeśli najwyższe bity nie zostały "utracone" z powodu przepełnienia i xordu z niższymi 32 bitami, wówczas wartość byłaby inna.

Answer 1

Czy istnieje jakiś szczególny powód, dla którego przepełnienie jest ignorowane? Nie jest to tak kosztowne, aby używać tak długo, jak opisano wcześniej.

Ale prawie na pewno nie ma z tego korzyści. Ta metodologia zazwyczaj daje dobry rozkład wartości na samym początku.

Answer 2

Jest to korzyść z pomnażania przez nieparzystą liczbę; wcześniejsze liczby nigdy całkowicie nie spadną z końca liczby całkowitej. Aby element został utracony, 31^n musiałaby być potęgą 2, a to nie może się zdarzyć. W twoim przypadku, na przykład 31^7, otrzymasz numer 0x67E12CDF dla numeru 32-bitowego; w ten sposób element wejściowy pomnożony przez tę wartość nadal będzie przyczyniał się do wyniku, pomimo przepełnienia.

Answer 3

Nie widzę punktu w przykładach. Wydają mi się niezwiązane ze sposobem, w jaki obliczasz kody hash: a * 31 + b.

Być może możesz znaleźć kod a i b, który dałby ten sam kod skrótu (ale gdzie wysokie bity są różne). W takim razie sensowne byłoby ponowne wpisanie wysokich bitów z powrotem do hashcode.

Innym przykładem może być ((a * 31) + b)*31 + ... + z. Następnie znajdź pewną liczbę, która nie jest już zależna od a. Tak więc a nie będzie znaczącym współpracownikiem.

Oczywiście, jeśli zmienisz 31 przez 65536, to jest dość łatwe do znalezienia tych a, ..., z. Każda wartość będzie działać, wszystkie bity a po prostu odpadają, a zostaje przesunięty w lewo i odcięty. Ale czy możesz to zrobić dla 31? Lub podobnie, możesz z powrotem przywrócić wysokie bity. Ale dlaczego? Czy możesz znaleźć przypadek, w którym to pomaga?

Problem z 65536 polega na tym, że w plikach binarnych wygląda to tak: 10000000000000000. Tak więc, gdy pomnożysz liczbę przez niego, w systemie binarnym ponownie uzyska te 16 zer. Dla 31, 11111 w binarnym, to się nie stanie.

Och, nie chodzi mi o to, że te przykłady nie istnieją, ponieważ tak jest (to po prostu hash mimo wszystko). Ale nie znajdziesz wielu podobnych przykładów.