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ć
Odpowiedzi:
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 3 , 5 3 ) i faktoryzacja 2000 (2 4 , 5 3 ) 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.
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
2
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
2
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
3
@Thilo potrzebowałbyś wielokrotności 1231 * 1237 = 1522,747 łyżek, zanim się zderzą, to jest wystarczająco duże
zapadkowy freak
2
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
2
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;
Odpowiedzi:
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 % Nwzgl2000 % N(gdzieNjest liczba segmentów).Teraz zauważ to
1000 % 8to samo wiadro co2000 % 81000 % 10to samo wiadro co2000 % 101000 % 20to samo wiadro co2000 % 20innymi słowy, doprowadziłoby to do wielu kolizji .
Dzieje się tak, ponieważ faktoryzacja 1000 (2 3 , 5 3 ) i faktoryzacja 2000 (2 4 , 5 3 ) 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:
źródło
2*1231 = 2462zasobników. Czy w takiej sytuacji kolizje są problemem?Oprócz wszystkiego, co zostało powiedziane powyżej, może to być również małe jajko wielkanocne od programistów:
7 - to szczęśliwa liczba w europejskich tradycjach;
13 (aka Devil's tuzin) - pechowa liczba.
źródło