Boolean.hashCode ()

122

hashCode()Metoda klasy Boolean jest realizowany w ten sposób:

public int hashCode() {
    return value ? 1231 : 1237;
}

Dlaczego używa 1231 i 1237? Dlaczego nie coś innego?

java boolean hashcode

— user471011
źródło

Te dwie liczby są wystarczająco dużymi liczbami pierwszymi. Aby uzyskać więcej informacji, przeczytaj artykuł na temat Hash Table w Wikipedii.

— Boris Pavlović

140

1231 i 1237 to tylko dwie (wystarczająco duże) dowolne liczby pierwsze . Jakiekolwiek inne dwie duże liczby pierwsze byłyby w porządku.

Dlaczego liczby pierwsze?
Załóżmy na sekundę, że wybraliśmy liczby złożone (inne niż liczby pierwsze), powiedzmy 1000 i 2000. Podczas wstawiania wartości logicznych do tablicy haszującej, prawda i fałsz trafiałyby do zasobnika 1000 % Nwzgl 2000 % N(gdzie Njest liczba segmentów).

Teraz zauważ to

1000 % 8 to samo wiadro co 2000 % 8
1000 % 10 to samo wiadro co 2000 % 10
1000 % 20 to samo wiadro co 2000 % 20
....

innymi słowy, doprowadziłoby to do wielu kolizji .

Dzieje się tak, ponieważ faktoryzacja 1000 (2 ³ , 5 ³ ) i faktoryzacja 2000 (2 ⁴ , 5 ³ ) mają tak wiele wspólnych czynników. W ten sposób wybiera się liczby pierwsze, ponieważ jest mało prawdopodobne, aby miały jakieś wspólne czynniki związane z rozmiarem łyżki.

Dlaczego duże liczby pierwsze. Czy 2 i 3 nie zrobiłyby?
Podczas obliczania kodów skrótów dla obiektów złożonych często dodaje się kody skrótów dla komponentów. Jeśli w zestawie skrótów z dużą liczbą segmentów zostaną użyte zbyt małe wartości, istnieje ryzyko, że skończy się to nierównomiernym rozmieszczeniem obiektów.

Czy kolizje mają znaczenie? Booleany mają po prostu dwie różne wartości?
Mapy mogą zawierać wartości logiczne razem z innymi obiektami. Ponadto, jak zauważył Drunix, powszechnym sposobem tworzenia funkcji skrótu obiektów złożonych jest ponowne użycie implementacji kodu skrótu składowego, w którym to przypadku dobrze jest zwrócić duże liczby pierwsze.

Powiązane pytania:

— aioobe
źródło

Przypuszczam, że te są wystarczająco duże. Aby uzyskać GCD większe niż 1, potrzebujesz przynajmniej 2*1231 = 2462zasobników. Czy w takiej sytuacji kolizje są problemem?

— aioobe

Ciekawe jednak, że nie są one tak naprawdę „dość duże”, biorąc pod uwagę, co można zmieścić w int. Przypuszczam, że są po prostu wystarczająco duże, aby dobrze współpracować z JDK Hashtable, ale nadal wystarczająco małe, aby zminimalizować koszty obliczeń.

— Thilo

Tak, uderzyło mnie też, że nie są tak duże. Ale czy sądzisz, że przy większych liczbach pierwszych koszt jest wyższy?

— aioobe

@Thilo potrzebowałbyś wielokrotności 1231 * 1237 = 1522,747 łyżek, zanim się zderzą, to jest wystarczająco duże

— zapadkowy freak

Powiedziałbym, że doprowadzenie do kolizji z liczbą zasobników nie jest tak naprawdę problemem w przypadku wartości logicznych, ale bardziej powszechną konstrukcją dotyczącą tego, w jaki sposób otrzymujemy kod hasłowy obiektu złożonego, mianowicie przez pomnożenie kodów hashcodes komponentów za pomocą pewnych stałych i zsumowanie ich.

— Drunix

Oprócz wszystkiego, co zostało powiedziane powyżej, może to być również małe jajko wielkanocne od programistów:

prawda: 1231 => 1 + 2 + 3 + 1 = 7

7 - to szczęśliwa liczba w europejskich tradycjach;

fałsz: 1237 => 1 + 2 + 3 + 7 = 13

13 (aka Devil's tuzin) - pechowa liczba.

— bvp
źródło