Le Dictionnaire est souvent utilisé pour obtenir une collection à accès rapide identique presque identique via une clef.
Mais comment marche t-il ?
Grâce aux nombres premiers !
Pour ceux qui ne connaissent pas, les nombres premiers ne se divise que par 1 ou par eux même. Ceux-ci vont nous permettre de calculer les index de positionnement de nos valeurs dans la collection.
Rappelons qu’une List<T> se base à l’origine sur un tableau T[] et que la List<T> s’occupe de gérer la taille de ce tableau et l’agrandir au besoin.
Un dictionnaire fonctionne de la même manière qu’une List<T> en utilisant une structure pour stocker Clef/Valeur, appelée Entry<TKey,TValue> dans le framework :
Disons que notre structure contient pour le moment ceci :
public struct Entry<TKey, TValue>
{
public TKey key;
public TValue value;
}
La différence avec une List<T>, c’est que le dictionnaire possède un index permettant un filtrage des données lors de leurs récupérations.
Cet index est un tableau d’entier de la même taille que le tableau de valeur :
public class Dictionary
{
private int[] buckets;
private Entry<TKey,TValue> entries;
}
Les tailles des deux tableaux sont égales entre elle et à un nombre premier.
Lors de l’ajout d’un item au tableaux “entries”, voici ce qui est effectué :
- On récupère le HashCode de la clef pour obtenir un entier :
int hashCode = key.GetHashCode(); - On récupère le reste de la division par le nombre premier utilisé pour la taille des tableaux :
int index = hashCode % entries.Length;
On obtient ainsi un nombre strictement inférieur à la taille de la collection. Ce nombre correspondra à un index dans le tableau d’index “buckets”. À cette position, on y stockera un index du tableau “entries” correspondant à l’index de la dernière clef dont la division du HashCode retourne la même valeur.
Le problème est que maintenant, on ne peut que récupérer le dernier enregistrement ajouté. Il nous suffit alors de stocké ce lui du précédent dans notre structure “Entry” :
public struct Entry<TKey, TValue>
{
public TKey key;
public TValue value;
public int previous; // Appelé next dans le framework
public int hasCode;
}
En simplifiant le code d’ajout d’item, on obtient ceci :
public void Add(TKey key, TValue value)
{
// Calcul d'un hashcode (positif)
int hashCode = key.GetHashCode() & int.MaxValue;
// Reste de la division
int index = hashCode % this.buckets.Length;
// Positionnement dans le tableau de valeur
int freeEntry = this.count;
this.count++;
this.entries[freeEntry].hashCode = hashCode;
// Récupération de l'index de l'ancienne clef vu en premier
this.entries[freeEntry].next = this.buckets[index];
this.entries[freeEntry].key = key;
this.entries[freeEntry].value = value;
// Définition de la nouvelle entrée vu en premier
this.buckets[index] = freeEntry;
}
Code très simplifié (la suppression, la présence de la clef et l’augmentation de taille ne son pas gérés).
On récupèrera donc la valeur ainsi :
public TValue Get(TKey key)
{
int hashCode = key.GetHashCode() & int.MaxValue;
int index = hashCode % this.buckets.Length;
for (int i = this.buckets[index]; i >= 0; i = this.entries[i].next)
{
if (this.entries[i].hashCode == hashCode)
{
return this.entries[i].value;
}
}
return default(TValue);
}
La principale source de gains de performance vient à l’initialisation du dictionnaire, ce qui est aussi le cas des List<T> : La taille de départ. Celle ci est d’autant plus importante que le dictionnaire doit, en plus de la copie mémoire des tableaux, recalculer les index avec la nouvelle taille.
