Dlaczego w zastępowaniu ReSharper GetHashCode jest używany numer „397”?

150

Podobnie jak wielu z was, używam ReSharper, aby przyspieszyć proces tworzenia. Kiedy używasz go do przesłonięcia członków równości klasy, kod-gen, który tworzy dla GetHashCode () wygląda następująco:

    public override int GetHashCode()
    {
        unchecked
        {
            int result = (Key != null ? Key.GetHashCode() : 0);
            result = (result * 397) ^ (EditableProperty != null ? EditableProperty.GetHashCode() : 0);
            result = (result * 397) ^ ObjectId;
            return result;
        }
    }

Oczywiście mam tam kilku swoich członków, ale chcę wiedzieć, dlaczego 397?

  • EDYCJA: Więc moje pytanie byłoby lepiej sformułowane, ponieważ czy jest coś „specjalnego” w liczbie pierwszej 397 poza tym, że jest liczbą pierwszą?
programista
źródło

Odpowiedzi:

166

Prawdopodobnie dlatego, że 397 jest liczbą pierwszą o wystarczającym rozmiarze, aby spowodować przepełnienie zmiennej wynikowej i pewne wymieszanie bitów skrótu, zapewniając lepszą dystrybucję kodów skrótu. W 397 nie ma nic szczególnego, co odróżnia go od innych liczb pierwszych tej samej wielkości.

Nick Johnson
źródło
73
397 jest szczęśliwy. Czy nie wszyscy po prostu chcemy być szczęśliwi?
Russell B
2
Dobrze, ale dlaczego musi być liczbą pierwszą i dlaczego musi być dokładnie tej wielkości? Jeśli ma być liczbą pierwszą, dlaczego nie 2 lub 2147483647? Myślę, że aby uzyskać ładną mutację (a jedynym powodem tego mnożenia jest mutacja), nie potrzebujemy liczby, aby była liczbą pierwszą. Potrzebujemy mnożnika, aby miał stosunkowo tę samą liczbę lub zera i jedynki, najlepiej bez wyraźnych wzorców. 397 = 110001101b spełnia. Nadal nie jestem pewien co do wielkości.
Andriy K
5
Jak powiedział Nick, nie ma w tym nic szczególnego. Nie MUSI mieć takiego rozmiaru, to tylko liczba, która jest na tyle duża, że ​​podczas obliczania skrótu wynik będzie przepełniony (ponieważ GetHashCode () zwraca Int32). Wybór liczby pierwszej jest po prostu pomocny przy rozkładaniu, nie mam stopnia z matematyki, więc nie zamierzam tego wyjaśniać, ale mnożenie przez liczbę pierwszą da wynik, który będzie lepiej rozłożony niż mnożenie przez jakąkolwiek inną dowolną liczbę.
Ben Randall,
16

Hash, którego używa resharper, wygląda jak wariant skrótu FNV . FNV jest często implementowane z różnymi liczbami pierwszymi. Dyskusja na temat właściwego doboru liczb pierwszych dla FNV jest tutaj .

kybernetikos
źródło