Die Beschreibung von System.Collection.Specialized.HybridDictionary lautet wie folgt:
Implementiert IDictionary mit a System.Collections.Specialized.ListDictionary während die Sammlung klein ist, und dann zu a wechseln System.Collections.Hashtable, wenn der Sammlung wird groß.
Gibt es eine äquivalente generische Implementierung?
Nicht, dass ich davon weiß. Gibt es jedoch ein erwiesenes Bedürfnis? Hash-Tabellen haben keinen großen Overhead, selbst für sehr kleine N sollte es schneller sein, nur die normale Hash-Tabelle zu verwenden, als linear zu suchen.
BEARBEITEN Ich habe keinen Benchmark, um es zu beweisen, aber nur durch den Vergleich der Algorithmen komme ich zu dem Schluss, dass Hashtabellen schneller sein sollten als lineare Suche, sobald N & gt ; 6 im Durchschnitt (für Zeichenfolgenschlüssel oder ähnliche nichttriviale Hashes), so gibt es wirklich keinen Grund für eine hybride Implementierung.
Das Argument lautet wie folgt. Bei der linearen Suche muss im Durchschnitt die Hälfte der Elemente mit Ihrer Eingabe verglichen werden, dh N / 2. In einer Hash-Tabelle ist bekannt, dass die erwartete Anzahl von Vergleichen unabhängig von der Eingabegröße 2 ist (Für sehr kleine Hash-Tabellen mit einem Auslastungsfaktor von weniger als 0,1 nähert sich dies tatsächlich 1). Zusätzlich muss der Hash berechnet werden. Dies führt zu 3 Operationen bei Ihrer Eingabe und einem sehr geringen Overhead, der vernachlässigt werden kann. Daher suchen wir nach dem N , dass 3 & gt; N / 2, was trivial ist N <& empty; & gt; 6.
Beachten Sie, dass die obige Berechnung tatsächlich falsch ist, da für diese kleine Anzahl von Elementen der Ladefaktor von .NET Dictionary viel kleiner als 0,1 ist. Der Kipppunkt ist daher tatsächlich noch niedriger.
Tags und Links .net