Pour écrire cette courte note, j'ai été invité par plusieurs entretiens récents pour le poste de développeur principal dans notre entreprise. Il s'est avéré que certains candidats ne connaissent pas bien le type de mécanisme utilisé, le dictionnaire, et la manière dont il devrait être utilisé. Je suis même tombé sur une opinion très radicale: ils disent que le dictionnaire fonctionne très lentement, et du fait que lorsqu'il est immédiatement placé sur le tas de gros objets (LOH), il ne peut pas être utilisé dans le code et il est préférable d'appliquer des requêtes à des collections régulières à l'aide de filtres LINQ !
Bien sûr, ce ne sont pas des déclarations entièrement vraies. Un dictionnaire en tant que mécanisme est très souvent demandé à la fois pour la création de code très chargé et pour l'implémentation d'une logique métier. Le développeur doit imaginer comment le dictionnaire est organisé, comment il fonctionne avec la mémoire, combien il est cher, combien de «traces» il laissera dans les générations et LOH, provoquant une charge inutile sur le garbage collector; comment l'initialiser mieux, auquel cas il vaut mieux utiliser une collection de paires clé-valeur à la place, dans laquelle une collection triée, etc.
Dans cet article, nous allons essayer de traiter certains de ces problèmes.
L'implémentation du dictionnaire de Microsoft est basée, comme chacun le sait, sur le mécanisme de la table de hachage. Cela donne dans certains scénarios l'inaccessible pour d'autres algorithmes de complexité constante idéale O (1) pour les opérations d'insertion, de recherche et de suppression. Dans certains scénarios, le refus d'utiliser ce mécanisme se heurte à des problèmes importants de performances et de consommation de mémoire.
Une caractéristique importante de l'architecture est que le stockage des données est organisé à l'aide de deux tableaux de même taille:
int[] _buckets = new int[size];
Entry[] _entries = new Entry[size];
Ces tableaux stockent des données et des éléments de service utiles pour y accéder rapidement. Les tableaux sont créés avec une marge, c'est-à-dire qu'ils sont presque toujours vides.
L'entité d'aide à l'entrée qui encapsule chaque paire clé-valeur est un type significatif:
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>.
.
, .
: , . .
Dans tous les exemples présentés, il convient de garder à l'esprit que de petites données sont utilisées dans la configuration de test; par conséquent, la surcharge pour les informations de service est relativement élevée.
Les projets de test peuvent être trouvés ici .