Dictionary
Initialiseur
Incrémenter la valeur
|
var monDictionnaire = new Dictionary<string, int>();
int value;
if (!monDictionnaire.TryGetValue(key, out value))
monDictionnaire.Add(key, 1);
else
monDictionnaire[key] = ++value;
|
Aplanir dans une List
|
|
var list = dictionary.SelectMany(kvp => kvp.Value); // IEnumerable
var list = dictionary.Values // To get just the List<string>
.SelectMany(x => x) // Flatten
.ToList(); // Listify
|
GetHashCode
Par défaut le hash code est calculé à partir de la référence de l'objet. Ainsi pour une même référence on obtiendra le même hash code.
Si l'on souhaite surcharger Equals, il faut aussi surcharger GetHashCode. Ce code sera notamment utilisé par les clés des dictionnaires.
Règles d'écriture de la méthode GetHashCode :
- Si deux objets sont égaux (Equals(...) == true), ils doivent avoir le même hash code.
- Deux objets ayant le même hash code ne sont pas forcément égaux, il peut s'agir d'une collision. La méthode Equals devra être appelée pour vérifier l'égalité.
- Le hash code d'un objet doit être constant tout au long de la vie de l'objet, car il est calculé à partir de sa référence.
|
|
class MyClass
{
public int MyIntProperty { get; set; }
public string MyStringProperty { get; set; }
public override bool Equals(object obj)
{
MyClass myClass = obj as MyClass;
return (myClass != null &&
myClass.MyIntProperty == this.MyIntProperty &&
myClass.MyStringProperty == this.MyStringProperty);
}
public override int GetHashCode()
{
return MyIntProperty.GetHashCode() ^ MyStringProperty.GetHashCode();
int hash = 17;
hash = hash * 23 + MyIntProperty.GetHashCode();
hash = hash * 23 + MyStringProperty.GetHashCode();
return hash;
}
}
|
Fonctionnement du Dictionary
La recherche d'un élément dans une liste implique de parcourir tous les éléments de cette liste.
Plus la liste contient d'éléments plus cette opération prendra du temps, elle est de complexité O(N) où N est le nombre d'éléments de la liste.
Une liste avec tous les éléments possibles
Pour réduire ce temps de recherche, on pourrait utiliser l'index de la liste comme clé.
Par exemple pour une liste de personnes on pourrait utiliser leur numéro de téléphone 00-00-00-00-00 comme index.
Ce qui donnerait une liste d'une taille de 10^10.
La recherche d'un élément dans cette liste serait de complexité O(1), car on accéderait directement à l'index.
Mais cela oblige à allouer de la mémoire pour une liste de taille 10^10 alors qu'on ne va y stocker que N personnes.
Réduire la taille de la liste avec une fonction de hashage
Afin de réduire la taille de la liste, on décide d'hasher les numéros de téléphone qui nous servent d'index, c'est à dire de réduire le nombre de combinaison possible pour l'index. Par exemple, on décide de prendre seulement les 6 derniers chiffres. On passe donc à une liste de taille 10^6.
Passer d'un ensemble de 10^10 éléments à un ensemble de 10^6 éléments ne se fait pas sans créer de collisions. C'est à dire tous les numéros de téléphone qui se termine par les même 6 chiffres mais dont les 4 premiers chiffres sont différents.
Gérer les collisions
Tant qu'il n'y a pas de collisions on insert les nouveaux éléments dans la liste.
linear probing
On essaye d'insérer l'élément à la position libre suivante.
Par exemple on insert les numéros suivants:
- 06 10 20 30 40 → Luc
- 06 11 20 30 40 → Jean
- 06 12 20 30 41 → Tom
| clé | valeur | commentaire |
|---|---|---|
| 20 30 40 | Luc | insertion à la position prévu |
| 20 30 41 | Jean | la position 20 30 40 étant déjà prise par Luc, nous avons un conflit. On insert Jean à la position libre suivante |
| 20 30 42 | Tom | la position 20 30 41 étant déjà prise par Jean, nous avons un conflit. On insert Jean à la position libre suivante |
Pour retrouver Tom, on va chercher à la position correspond au hash de son numéro de téléphone 20 30 41 et vérifié que c'est bien lui.
Si ce n'est pas le cas, on continue la recherche à la position suivante jusqu'à le trouver ou jusqu'à tomber sur une position libre, ce qui signifie qu'il n'est pas dans la liste.
Cette technique à tendance à créer des groupe car on ajoute les éléments conflictuels à la position libre suivante. Lors des recherches il faut parcourir ces groupes.
Pour des recherches rapides, les données doivent être réparties uniformément et non groupées à certains endroits.
quadratic probing
Fonctionne comme le linear probing, mais en cas de conflict, au lieu d'insérer l'élément à la prochaine place libre, il teste si la position p + 1² est libre, puis la position p - 1², ensuite p + 2², puis p - 2², puis p + 3², etc
rehasing
En cas de conflit, recalcule la position d'insertion avec la méthode de hashage suivante parmi une liste définie (H1 ... Hk ... Hn).
Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize
Utilisé par Hashtable
chaining
En cas de conflit, l'élément en collision est ajouté à la position de son hash, dans une liste chaînée d'éléments.
Utilisé par Dictionary
