Jaki jest sensowny prime do obliczania hashcode? [duplikat]
To pytanie ma już odpowiedź tutaj:
Eclipse 3.5 ma bardzo ładną funkcję do generowania funkcji hashCode () Javy. Generowałby np. (nieco skrócony:)
class HashTest {
int i;
int j;
public int hashCode() {
final int prime = 31;
int result = prime + i;
result = prime * result + j;
return result;
}
}
(Jeśli masz więcej atrybutów w klasie, result = prime * result + attribute.hashCode(); powtarza się dla każdego dodatkowy atrybut. Dla ints .hashCode() można pominąć.)
Jest to pytanie ogólne - więc nie chcę podawać zakresu dla i I j. ale przypuszczam, że w większości zastosowań stosunkowo małe wartości występują częściej niż duże wartości. (Jeśli masz duże wartości wybór liczby pierwszej jest prawdopodobnie nieistotny.) Może to nie robi wielkiej różnicy, ale lepszy wybór jest łatwym i oczywistym sposobem na poprawę tego - więc dlaczego nie zrobić? Commons lang HashCodeBuilder również sugeruje ciekawie małe wartości.
(Wyjaśnienie: to jest a nie duplikat dlaczego hashCode() w łańcuchu znaków używa 31 jako mnożnika?Ponieważ moje pytanie nie dotyczy historii 31 w JDK, ale na czym byłoby lepszą wartością w nowym kodzie przy użyciu tego samego podstawowego szablonu. Żadna z odpowiedzi nie próbuje na to odpowiedzieć.)
6 answers
Polecam używanie 92821. Oto dlaczego.
Aby dać sensowną odpowiedź na to pytanie, musisz wiedzieć coś o możliwych wartościach i i j. Jedyne, co mogę myśleć w ogóle jest, że w wielu przypadkach małe wartości będą bardziej powszechne niż duże wartości. (Kursy 15 pojawiające się jako wartość w twoim programie są znacznie lepsze niż, powiedzmy, 438281923.) Więc wydaje się dobrym pomysłem, aby najmniejsza kolizja hashcode była jak największa, wybierając odpowiednią prime. Dla 31 to raczej źle - już dla i=-1 i j=31 masz taką samą wartość hash jak dla i=0 i j=0.
Ponieważ jest to interesujące, napisałem mały program, który przeszukał cały zakres int dla najlepszego prime w tym sensie. Oznacza to, że dla każdego prime Szukałem minimalnej wartości Math.abs(i) + Math.abs(j) nad wszystkimi wartościami i,j, które mają ten sam hashcode co 0,0, a następnie wziąłem prime, gdzie ta minimalna wartość jest tak duża, jak to możliwe.
Drumroll : the best liczba pierwsza w tym sensie wynosi 486187739 (przy najmniejszej kolizji i=-25486, j=67194). Prawie tak dobry i dużo łatwiejszy do zapamiętania jest 92821 z najmniejszą kolizją i=-46272 and j=46016.
Jeśli nadasz "małe" inne znaczenie i chcesz być minimum Math.sqrt(i*i+j*j) dla kolizji jak największej, wyniki są trochę inne: najlepsze byłoby 1322837333 z i=-6815 and j=70091, Ale mój ulubiony 92821 (najmniejsza kolizja -46272,46016) jest ponownie prawie tak dobry, jak najlepsza wartość.
Uznaję że jest dość dyskusyjne, czy te obliczenia mają sens w praktyce. Ale uważam, że wzięcie 92821 jako prime ma o wiele większy sens niż 31, chyba że masz ku temu powody.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-04-01 11:30:00
W rzeczywistości, jeśli weźmiesz pierwiastek tak duży, że zbliży się do INT_MAX, masz ten sam problem z powodu arytmetyki modulo. Jeśli spodziewasz się hashować głównie ciągi o długości 2, Być może prime w pobliżu pierwiastka kwadratowego INT_MAX byłoby najlepsze, jeśli ciągi, które hashujesz są dłuższe, nie ma to większego znaczenia i kolizje są nieuniknione...
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-12-02 21:54:16
Kolizje mogą nie być tak dużym problemem... Głównym celem hash jest unikanie używania równych dla porównań 1: 1. Jeśli masz implementację, w której equals jest "ogólnie" bardzo tani dla obiektów, które zderzyły się z hashami, to nie jest to problem (w ogóle).
W końcu, jaki jest najlepszy sposób mieszania zależy od tego, co porównujesz. W przypadku pary int (jak w twoim przykładzie), użycie podstawowych operatorów bitowych może być wystarczające (jak użycie & lub ^).
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-12-02 23:20:52
Musisz zdefiniować zakres dla i i J. możesz użyć liczby pierwszej dla obu.
public int hashCode() {
http://primes.utm.edu/curios/ ;)
return 97654321 * i ^ 12356789 * j;
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-12-02 21:52:51
Wybrałbym 7243. Wystarczająco duże, aby uniknąć kolizji z małymi liczbami. Nie przelewa się szybko do małych liczb.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-12-02 22:11:23
Chcę tylko zaznaczyć, że hashcode nie ma nic wspólnego z prime. W implementacji JDK
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
I found if you replace 31 z 27, wynik jest bardzo podobny.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-10-15 05:25:26