Nach Angaben von diese Frage ein .Net-Wörterbuch seinen zugewiesenen Speicherplatz an Primzahlen anpasst, die mindestens das Doppelte der aktuellen Größe betragen. Warum ist es wichtig, Primzahlen zu verwenden und nicht nur das Doppelte der aktuellen Größe? (Ich habe versucht, mit meinen Google-Fähigkeiten eine Antwort zu finden, aber ohne Erfolg)
Antworten
Zu viele Anzeigen?
CodesInChaos
Punkte
103089
Der Eimer, in den ein Element gelegt wird, wird bestimmt durch (hash & 0x7FFFFFF) % capacity . Diese muss gleichmäßig verteilt sein. Daraus folgt, dass wenn mehrere Einträge, die ein Vielfaches einer bestimmten Basis sind ( hash1 = x1 * base , hash2 = x2 * base ,...) wobei base y capacity nicht koprim sind (größter gemeinsamer Teiler > 1), werden einige Slots überbelegt und einige nie genutzt. Da Primzahlen zu jeder Zahl außer sich selbst koprim sind, haben sie relativ gute Chancen, eine gute Verteilung zu erreichen.
Eine besonders schöne Eigenschaft ist, dass für capacity > 30 der Beitrag der einzelnen Bits zum Hashcode ist unterschiedlich. Wenn sich also die Variation des Hashcodes auf nur wenige Bits konzentriert, führt dies immer noch zu einer guten Verteilung. Dies erklärt, warum Kapazitäten, die Potenzen von zwei sind, schlecht sind: Sie verdecken die hohen Bits. Eine Reihe von Zahlen, bei denen nur die hohen Bits unterschiedlich sind, ist gar nicht so unwahrscheinlich.
Ich persönlich denke, dass sie diese Funktion schlecht gewählt haben. Sie enthält eine teure Modulo-Operation, und wenn die Einträge ein Vielfaches der Primzahl-Kapazität sind, bricht die Leistung ein. Aber für die meisten Anwendungen scheint sie gut genug zu sein.
Es handelt sich um ein Detail der Algorithmusimplementierung im Zusammenhang mit Auswahl einer guten Hashing-Funktion und die eine gleichmäßige Verteilung gewährleistet. Eine ungleichmäßige Verteilung erhöht die Anzahl der Kollisionen und die Kosten für ihre Behebung.
TomTom
Punkte
1
Aufgrund der Mathematik der Primzahlen können diese nicht in verschiedene kleinere Zahlen zerlegt werden. Wenn Sie die Hash-Zahl durch die gespeicherten Elemente teilen, erhalten Sie also eine Gleichverteilung. Hätten Sie keine Primzahl, wäre die Verteilung je nach Objekt möglicherweise nicht gleichmäßig.
