Diese beiden Zahlen sind ausreichend große Primzahlen. Bitte lesen Sie den Artikel auf Hash Table auf Wikipedia für weitere Informationen.
Boris Pavlović
Antworten:
139
1231 und 1237 sind nur zwei (ausreichend große) beliebige Primzahlen . Alle anderen zwei großen Primzahlen würden gut tun.
Warum Primzahlen?
Angenommen, wir haben für eine Sekunde zusammengesetzte Zahlen (Nicht-Primzahlen) ausgewählt, z. B. 1000 und 2000. Wenn Boolesche Werte in eine Hash-Tabelle eingefügt werden, werden true und false in den Bucket 1000 % Nbzw. in den Bucket 2000 % N(wo Nist die Anzahl der Buckets) eingegeben .
Beachten Sie jetzt das
1000 % 8 gleicher Eimer wie 2000 % 8
1000 % 10 gleicher Eimer wie 2000 % 10
1000 % 20 gleicher Eimer wie 2000 % 20
....
Mit anderen Worten, es würde zu vielen Kollisionen führen .
Dies liegt daran, dass die Faktorisierung von 1000 (2 3 , 5 3 ) und die Faktorisierung von 2000 (2 4 , 5 3 ) so viele gemeinsame Faktoren haben. Daher werden Primzahlen gewählt, da es unwahrscheinlich ist, dass sie gemeinsame Faktoren mit der Schaufelgröße haben.
Warum große Primzahlen? Würden 2 und 3 nicht tun?
Bei der Berechnung von Hash-Codes für zusammengesetzte Objekte werden häufig die Hash-Codes für die Komponenten hinzugefügt. Wenn in einem Hash-Set mit einer großen Anzahl von Buckets zu kleine Werte verwendet werden, besteht die Gefahr, dass Objekte ungleichmäßig verteilt werden.
Sind Kollisionen wichtig? Boolesche Werte haben sowieso nur zwei verschiedene Werte?
Karten können zusammen mit anderen Objekten Boolesche Werte enthalten. Wie von Drunix hervorgehoben, besteht eine übliche Methode zum Erstellen von Hash-Funktionen von zusammengesetzten Objekten darin, die Hash-Code-Implementierungen der Unterkomponenten wiederzuverwenden. In diesem Fall ist es gut, große Primzahlen zurückzugeben.
Ich nehme an, diese sind ausreichend groß. Um eine GCD größer als 1 zu erhalten, benötigen Sie mindestens 2*1231 = 2462Eimer. Sind Kollisionen in einer solchen Situation ein Problem?
Aioobe
2
Interessant ist jedoch, dass sie nicht wirklich "ziemlich groß" sind, wenn man bedenkt, was in einen Int passen kann. Ich nehme an, sie sind gerade groß genug, um mit der JDK-Hashtabelle gut zu funktionieren, aber immer noch klein genug, um die Berechnungskosten zu minimieren.
Thilo
2
Ja, es ist mir auch aufgefallen, dass sie nicht so groß sind. Aber glauben Sie, dass es bei größeren Primzahlen höhere Kosten gibt?
Aioobe
3
@Thilo Sie würden ein Vielfaches von 1231 * 1237 = 1.522.747 Eimern benötigen, bevor sie kollidieren würden, das ist groß genug
Ratschenfreak
2
Ich würde sagen, dass das Führen zu Kollisionen mit der Bucket-Anzahl kein wirkliches Problem mit Booleschen Werten ist, sondern eher die übliche Konstruktion, wie wir den Hascode eines zusammengesetzten Objekts erhalten, nämlich indem die Hashcodes der Komponenten mit einigen Konstanten multipliziert und addiert werden.
Drunix
2
Zusätzlich zu allem, was oben gesagt wurde, kann es auch ein kleines Osterei von Entwicklern sein:
true: 1231 => 1 + 2 + 3 + 1 = 7
7 - ist eine Glückszahl in europäischen Traditionen;
false: 1237 => 1 + 2 + 3 + 7 = 13
13 (auch bekannt als Devil's Dutzend) - unglückliche Zahl.
Antworten:
1231 und 1237 sind nur zwei (ausreichend große) beliebige Primzahlen . Alle anderen zwei großen Primzahlen würden gut tun.
Warum Primzahlen?
Angenommen, wir haben für eine Sekunde zusammengesetzte Zahlen (Nicht-Primzahlen) ausgewählt, z. B. 1000 und 2000. Wenn Boolesche Werte in eine Hash-Tabelle eingefügt werden, werden true und false in den Bucket
1000 % Nbzw. in den Bucket2000 % N(woNist die Anzahl der Buckets) eingegeben .Beachten Sie jetzt das
1000 % 8gleicher Eimer wie2000 % 81000 % 10gleicher Eimer wie2000 % 101000 % 20gleicher Eimer wie2000 % 20Mit anderen Worten, es würde zu vielen Kollisionen führen .
Dies liegt daran, dass die Faktorisierung von 1000 (2 3 , 5 3 ) und die Faktorisierung von 2000 (2 4 , 5 3 ) so viele gemeinsame Faktoren haben. Daher werden Primzahlen gewählt, da es unwahrscheinlich ist, dass sie gemeinsame Faktoren mit der Schaufelgröße haben.
Warum große Primzahlen? Würden 2 und 3 nicht tun?
Bei der Berechnung von Hash-Codes für zusammengesetzte Objekte werden häufig die Hash-Codes für die Komponenten hinzugefügt. Wenn in einem Hash-Set mit einer großen Anzahl von Buckets zu kleine Werte verwendet werden, besteht die Gefahr, dass Objekte ungleichmäßig verteilt werden.
Sind Kollisionen wichtig? Boolesche Werte haben sowieso nur zwei verschiedene Werte?
Karten können zusammen mit anderen Objekten Boolesche Werte enthalten. Wie von Drunix hervorgehoben, besteht eine übliche Methode zum Erstellen von Hash-Funktionen von zusammengesetzten Objekten darin, die Hash-Code-Implementierungen der Unterkomponenten wiederzuverwenden. In diesem Fall ist es gut, große Primzahlen zurückzugeben.
Verwandte Fragen:
quelle
2*1231 = 2462Eimer. Sind Kollisionen in einer solchen Situation ein Problem?Zusätzlich zu allem, was oben gesagt wurde, kann es auch ein kleines Osterei von Entwicklern sein:
7 - ist eine Glückszahl in europäischen Traditionen;
13 (auch bekannt als Devil's Dutzend) - unglückliche Zahl.
quelle