Mnożenie liczby całkowitej, przepełnienie i utrata informacji

Przeczytam przez Chapter 3 z Joshua Blocha Skuteczna Java. W punkt 8: zawsze zastępują hashCode kiedy przesłonić równa, autor wykorzystuje następujące łącząc krok w swej funkcji haszowania:Mnożenie liczby całkowitej, przepełnienie i utrata informacji

result = 37 * result + c;

Potem wyjaśnia, dlaczego 37 została wybrana (podkreślenie dodane):

Mnożnik 37 został wybrany, ponieważ jest to nieparzysta liczba pierwsza. Jeśli był równy i , to mnożenie uległo przepełnieniu, informacje zostałyby utracone, ponieważ pomnożenie przez dwa jest równoznaczne z przesunięciem. Zalety korzystania z numeru pierwszego są mniej wyraźne, ale jest to typowe użycie liczb pierwszych w tym celu.

Moje pytanie brzmi, dlaczego to ma znaczenie, że czynnik łączący (37) jest dziwne? Czy przepełnienie mnożenia nie spowodowałoby utraty informacji, niezależnie od tego, czy czynnik był nieparzysty czy nawet niepoprawny?

Źródło

2011-12-20 Bill the Lizard

Zastanów się, co się dzieje, gdy dodatnia wartość jest wielokrotnie pomnożona przez dwa w reprezentacji base-2 - wszystkie ustawione bity ostatecznie marsz poza końcem, pozostawiając zero.

Mnożnik równomierny dałby kody skrótów o mniejszej różnorodności.

Z drugiej strony liczby nieparzyste mogą powodować przepełnienie, ale bez utraty różnorodności.

Źródło

2011-12-20 15:16:50

Ah, więc nie jest to po prostu odrobina utraty informacji, którą można uzyskać z przepełnienia, o które się martwimy, jest to * pełne * utrata informacji, którą można uzyskać od wyzerowania wyniku? –

@BilltheLizard: w rzeczywistości to dane z wielu właściwości emulujących się nawzajem. Zakładając trzy właściwości a, b i c, używając powyższego algorytmu 'result = 2 * (2 * a + b) + c', widać, że będzie powielanie w wielu prawdopodobnie wspólnych zestawach' a, b, c'. Jeśli używasz nieparzystej liczby pierwszej jako stałej, możliwość uzyskania zestawu o tych samych wartościach mieszania staje się znacznie mniejsza. –

Problem pojawia się, zanim całkowicie wyzerujesz wynik. Rozważ zwielokrotnienie 8-bitowego skrótu przez mnożnik dwóch tylko raz - zaczyna się od 256 możliwych wartości, a kończy 128 możliwymi wartościami. –

Celem hashcode jest mieć losowych bitów na podstawie wejścia (szczególnie dolne bity jak te są często używane więcej)

Podczas wielokrotność przez 2 najniższy bit może być tylko 0, którym brakuje losowości . Jeśli liczba mnoga jest liczbą nieparzystą, najniższy bit może być parzysty lub nieparzysty.

Podobna kwestia jest to, co ty tu dostać

public static void main(String... args) { 
    System.out.println(factorial(66)); 
} 

public static long factorial(int n) { 
    long product = 1; 
    for (; n > 1; n--) 
     product *= n; 
    return product; 
}

drukuje

Co druga liczba jest parzysta, a co czwarty wielokrotnością 4 itd

Źródło

2011-12-20 15:25:29

Sprytnie, możesz pokazać ręcznie, że przelewa się do 0. Więc żadne silniki nie są funkcjami haszującymi ... nie, żebym kiedykolwiek to zrobił. – toto2

Częścią triku jest ustalenie, dlaczego 66 jest pierwszą silnią na 0. A na przykład nie 128, która ma 64 czynniki równomierne. –

Rozwiązanie leży w Teorii Liczb i Lowest common denominator mnożnika i numerze modulo.

Przykład może pomóc. Powiedzmy, że zamiast 32-bitowego masz tylko 2-bitową reprezentację. Masz 4 numery (klasy). 0, 1, 2 i 3

przepełnienie w CPU jest taka sama jak operacja modulo

Class - x2 - mod 4 - x2 - mod 4 

0  0  0  0  0 

1  2  2  4  0 

2  4  0  0  0 

3  6  2  4  0

Po 2 operacjach Masz tylko 1 możliwa liczba (klasa) w lewo. Więc "zagubiłeś" informacje.

Class - x3 - mod 4 - x3 - mod 4 ... 

0  0  0  0  0 

1  3  3  9  1 

2  6  2  6  2 

3  9  1  3  3

To może trwać wiecznie i nadal masz wszystkie 4 klasy. Więc nie tracisz informacji.

Kluczem jest to, że ekran LCD twojego mnożnika i twoja klasa modulo wynosi 1. To jest prawdziwe dla wszystkich cyfr nieparzystych, ponieważ twój numer modulo jest obecnie zawsze potęgą 2. Nie muszą to być liczby pierwsze i one nie mają być dokładnie 37. Ale utrata informacji jest tylko jedno kryterium, dlaczego 37 jest odbierane są inne charakterystyczne rozmieszczenie wartości itp

Źródło

2011-12-20 16:06:23 Stefan

dla matematyki prosta wersja dlaczego ...

liczb służą do mieszania, aby zachować różnorodność.

Być może różnorodność jest ważniejsza z powodu implementacji zestawu i mapy. Te implementacje wykorzystują ostatnie bity liczb mieszania obiektu do indeksowania wewnętrznych tablic wpisów.

Na przykład w HashMap z wewnętrzną tabelą (tablicą) dla pozycji o rozmiarze 8 użyje 3 ostatnich bitów numerów hashowych do wpisania pozycji w tabeli.

 

    static int indexFor(int h, int length) { 
     return h & (length-1); 
    }

W rzeczywistości to nie jest, ale jeśli obiekt Integer musiałby

 

    hash = 4 * number;

większość elementów tabeli będzie pusta, ale niektóre będą zawierać zbyt wiele wpisów. Doprowadziłoby to do dodatkowych iteracji i operacji porównania podczas wyszukiwania określonego wpisu.

Domyślam się, że głównym problemem Joshua Blocha była dystrybucja liczb pełnych, aby zoptymalizować wydajność kolekcji poprzez równomierną dystrybucję obiektów w Mapach i Zestawach. Liczba pierwszych liczb intuicyjnie wydaje się być dobrym czynnikiem dystrybucji.

Źródło

2011-12-20 16:15:02 andrey

Najwyższe liczby nie są bezwzględnie konieczne, aby zapewnić różnorodność; konieczne jest, aby czynnik był względnie pierwszorzędny względem modułu.

Ponieważ moduł arytmetyki binarnej ma zawsze moc dwóch, każda liczba nieparzysta jest względnie pierwsza i wystarczająca. Gdybyś miał przyjąć moduł inny niż przez przepełnienie, pierwsza liczba nadal zapewniałaby różnorodność (zakładając, że nie wybrałeś tego samego poziomu ...).

Źródło

2011-12-20 16:27:40

Mnożenie liczby całkowitej, przepełnienie i utrata informacji

Odpowiedz

Powiązane problemy