Wörterbuch <,> Größe, GetHashCode und Primzahlen?

Question

Ich habe viel über dieses interessante Thema (IMO) gelesen. aber ich bin nicht ganz verstehen eins:

Wörterbuch Größe erhöht seine Kapazität (verdoppelt sich auf die nächste Primzahl) zu einer Primzahl (wenn Neuzuteilung): weil:

int index = hashCode % [Dictionary Capacity]; 

• So können wir sehen, dass Primzahlen hier für [Dictionary Capacity] verwendet werden, weil ihre GreatestCommonFactor1 ist. und dieses hilft, um Kollisionen zu vermeiden.

Zusätzlich

ich viele Proben der Umsetzung der GetHashCode() gesehen habe:

Hier ist ein Beispiel von Jon Skeet:

public override int GetHashCode() 
{ 
    unchecked 
    { 
     int hash = 17; 
     // Suitable nullity checks etc, of course :) 
     hash = hash * 23 + field1.GetHashCode(); 
     hash = hash * 23 + field2.GetHashCode(); 
     hash = hash * 23 + field3.GetHashCode(); 
     return hash; 
    } 
} 

Ich verstehe nicht:

Frage Dictionary capacity und bei der Erzeugung von getHashCode: auf

Hat sind Primzahlen sowohl in verwendet?

Da oben in dem Code, gibt es eine gute Chance, dass der Rückgabewert wird nicht eine Primzahl [bitte korrigiert mich wenn ich falsch bin] wegen der

• Multiplikation mit 23
• Addition der GetHashCode() Wert für jedes Feld.

zum Beispiel: (11,17,173 sind Primzahlen)

 int hash = 17; 
     hash = hash * 23 + 11; //402 
     hash = hash * 23 + 17; //9263 
     hash = hash * 23 + 173 //213222 
     return hash; 

213222 keine Primzahl ist.

Auch gibt es keine mathematische Regel, den Staat:

(not a prime number) + (prime number) = (prime number)

noch

(not a prime number) * (prime number) = (prime number)

noch

(not a prime number) * (not a prime number) = (prime number)

So was fehlt mir??

Answer 1

Es spielt keine Rolle, was das Ergebnis von GetHashCode ist (es muss überhaupt nicht prim sein), solange das Ergebnis für zwei Objekte gleich ist, die als gleich betrachtet werden. Es ist jedoch nice (aber nicht erforderlich) zu haben GetHashCode einen anderen Wert für zwei Objekte zurückgegeben, die als unterschiedlich angesehen werden (aber immer noch nicht unbedingt Prime).

Gegeben zwei Zahlen ein und b, wenn Sie sie Sie c = a * b bekommen multiplizieren. Es gibt normalerweise mehrere unterschiedliche Paare von , und b, die das gleiche Ergebnis c ergeben. Zum Beispiel 6 * 2 = 12 und 4 * 3 = 12. Wenn jedoch eine eine prime Nummer ist, gibt es viel weniger Paare, die das gleiche Ergebnis geben. Dies ist praktisch für die Eigenschaft, dass der Hash-Code für verschiedene Objekte unterschiedlich sein sollte.

Im Wörterbuch gilt das gleiche Prinzip: Die Objekte werden je nach Hash in Buckets abgelegt. Da die meisten Ganzzahlen nicht durch eine Primzahl getrennt sind, erhalten Sie eine schöne Verteilung Ihrer Objekte in den Eimern. Im Idealfall möchten Sie nur einen Eintrag in jedem Bucket für eine optimale Wörterbuchleistung.

---

Slightly Off-Topic: Cicada (das ist ein Insekt) use prime numbers, um zu bestimmen, nach wie vielen Jahren sie gehen und wieder paaren. Da dieser Paarungszyklus eine Anzahl von Jahren ist, sind die Chancen, dass die Paarung kontinuierlich mit den Lebenszyklen eines ihrer Feinde zusammenfällt, gering.