Gemäß this question ändert ein .Net-Wörterbuch seinen zugewiesenen Speicherplatz auf Primzahlen, die mindestens doppelt so groß sind wie die aktuelle Größe. Warum ist es wichtig, Primzahlen zu verwenden und nicht nur die doppelte Größe? (Ich versuchte, meine google-fu-Kräfte zu verwenden, um eine Antwort zu finden, aber ohne Erfolg)Warum .Net-Wörterbücher auf Primzahlen umstellen?
Es handelt sich um ein Algorithmusimplementierungsdetail, das sich auf choosing a good hashing function bezieht und eine gleichmäßige Verteilung bietet. Eine ungleichmäßige Verteilung erhöht die Anzahl der Kollisionen und die Kosten für deren Lösung.
Die Wahl der Primzahl bewirkt ** nicht ** eine gleichmäßige Verteilung, keine Vereinfachung. Mit hashsize = prime_number haben Sie absolut die gleiche Chance, Kollisionen zu bekommen wie bei hashsize = 2^k' oder anderen. Es ist nur so, dass einige Hashgrößen dazu führen, dass Kollisionen "unvorhersehbar", "zufällig" oder "gleichmäßig verteilt" aussehen. Auf der anderen Seite würde "hashsize = 2^k" bedeuten, dass jede auf xor basierende Hash-Funktion lutschen wird. –
Wegen der Mathematik der Primzahlen.Sie können nicht in verschiedene kleinere Zahlen faktorisiert werden. Wenn Sie die Hash-Nummer von den gespeicherten Elementen trennen, erhalten Sie eine gleichmäßige Verteilung. Wenn Sie keine Primzahl haben, ist die Verteilung abhängig von den Objekten möglicherweise nicht gerade.
Der Bucket, in dem ein Element platziert wird, wird durch bestimmt. Dies 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, ...) base und capacity nicht koprämieren (größter gemeinsamer Teiler> 1) einige Slots über verwendet werden, und einige nie benutzt. Da Primzahlen eine Nummer neben sich selbst sind, haben sie relativ gute Chancen, eine gute Verteilung zu erreichen.
Eine besonders nette Eigenschaft davon ist, dass für capacity > 30 der Beitrag jedes Bits zum Hashcode unterschiedlich ist. Wenn also die Variation des Hash in nur wenigen Bits konzentriert ist, wird es immer noch zu einer guten Verteilung führen. 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 nicht so unwahrscheinlich.
Ich persönlich denke, dass sie diese Funktion schlecht wählen. Es enthält eine teure Modulo-Operation, und wenn die Einträge Vielfache der Primzahl-Kapazität sind, bricht seine Leistung zusammen. Aber es scheint für die meisten Anwendungen gut genug zu sein.
als eine Nebenidee zu Ihnen Frage, kennt jemand eine Baum-wie ausgeglichene Datenstruktur, die Größe zu prime Größen ändert? vielleicht sollte ich eine andere Frage –
postulieren, was ist die Struktur der Baumstruktur hinter .NET-Wörterbuch dann? –
Ich stellte die Frage hier http://stackoverflow.com/questions/4639122/balanced-tree-like-data-structure-that-resizes-to-prime-sizes –