Um diese kurze Notiz zu schreiben, wurde ich kürzlich von mehreren Interviews zur Position des Hauptentwicklers in unserem Unternehmen aufgefordert. Wie sich herausstellte, wissen einige Bewerber nicht genau, um welchen Mechanismus es sich handelt, um ein Wörterbuch und wie es verwendet werden sollte. Ich bin sogar auf eine sehr radikale Meinung gestoßen: Sie sagen, dass das Wörterbuch sehr langsam arbeitet und aufgrund der Tatsache, dass es, wenn es sofort in den Haufen großer Objekte (LOH) gelegt wird, nicht im Code verwendet werden kann und es besser ist, Abfragen mit LINQ-Filtern auf reguläre Sammlungen anzuwenden !
Dies sind natürlich keine ganz wahren Aussagen. Ein Wörterbuch als Mechanismus ist sehr häufig gefragt, sowohl beim Erstellen von hoch geladenem Code als auch bei der Implementierung von Geschäftslogik. Der Entwickler muss sich vorstellen, wie das Wörterbuch organisiert ist, wie es mit dem Speicher funktioniert, wie teuer es ist, wie viele „Spuren“ es in Generationen und LOH hinterlässt und den Garbage Collector unnötig belastet. wie man es besser initialisiert, in welchen Fällen es besser ist, stattdessen eine Sammlung von Schlüssel-Wert-Paaren zu verwenden, in denen eine sortierte Sammlung usw.
In diesem Artikel werden wir versuchen, einige dieser Probleme zu lösen.
Die Implementierung des Wörterbuchs von Microsoft basiert bekanntlich auf dem Hash-Tabellenmechanismus. Dies gibt in einigen Szenarien die für andere Algorithmen unerreichbare ideale konstante Komplexität O (1) für Einfüge-, Such- und Löschoperationen. In einigen Szenarien ist die Weigerung, diesen Mechanismus zu verwenden, mit erheblichen Problemen hinsichtlich Leistung und Speicherverbrauch verbunden.
Ein wichtiges Merkmal der Architektur ist, dass die Datenspeicherung mit zwei Arrays gleicher Größe organisiert wird:
int[] _buckets = new int[size];
Entry[] _entries = new Entry[size];
Diese Arrays speichern nützliche Daten und Serviceelemente für den schnellen Zugriff auf sie. Arrays werden mit einem Rand erstellt, dh sie sind fast immer leer.
Die Entry-Hilfsentität, die jedes Schlüssel-Wert-Paar umschließt, ist ein signifikanter Typ:
private struct Entry
{
public uint hashCode;
public int next;
public TKey key;
public TValue value;
}
, , , _entries. , ConcurrentDictionary, . ( 64 16 8 ) , .
_entries Dictionary 85000 LOH (, , 64 3372 , 1932). , , .
Microsoft _entries , Entry? LOH (, , ). , , .
, . 12 (4 _buckets 4 hashCode next Entry). , , , 12 . ? .
Dictionary . . Dictionary<int, int> ( ). , – ( ). 500 . 13 . 500 .
, . , , , .
, _buckets _entries , «», . LOH, .
, 746 3 .
, Dictionary . , , , .NET Core TrimExcess, .
:
- , EnsureCapacity. .
- , 400 10. (80 ). new Dictionary<int, int>(10001000), 190. , , .
- , Dictionary EnsureCapacity(capacity*), . , _buckets _entries . . , EnsureCapacity(0).
- , ( ) , , Dictionary: . , . , ( ).
- TrimExcess. LOH . .
Dictionary. , Dictionary<Key, Value>, :
public class Key
{
public int Item { get; set; }
public Key(int item)
{
Item = item;
}
public override bool Equals(object obj)
{
return Item.Equals(obj);
}
public override int GetHashCode()
{
return Item.GetHashCode();
}
}
public class Value
{
public int Item { get; set; }
public Value(int item)
{
Item = item;
}
}
.
?
:
- 64 (8 ) (8 ).
- , , 8 «» .
- Item Key Value 8 , , Item 4 .
20 76 .
:
, . ? , ( 10-20-30 ) . ?
. , Dictionary<int, int>(int count) :
struct Entry<TValue>
{
public int[] Keys;
public TValue[] Values;
public Entry(int count)
{
Keys = new int[count];
Values = new TValue[count];
}
public bool TryGetValue(int key, out TValue value)
{
for (int j = 0; j < Keys.Length; ++j)
{
if (Keys[j] == key)
{
value = Values[j];
return true;
}
}
value = default(TValue);
return false;
}
}
count – -, .
.
, 18 count=10 134 count=190 ( 50 . ). ( – 29 ), ( 150) , (, ).
, (, , Entry , ).
, (callvirt GetHashCode Equals). – . , , , (generic) . .
SortedList<int, int>.
.
, .
: , . .
Bei allen vorgestellten Beispielen sollte berücksichtigt werden, dass in der Testkonfiguration kleine Daten verwendet werden, weshalb der Overhead für Serviceinformationen relativ hoch ist.
Testprojekte finden Sie hier .