Amélioration des performances du dictionnaire

Question

J'essaie d'améliorer un code qui a été écrit il y a longtemps. la fonction est assez importante pour la fonctionnalité de base du système, donc je suis prudent à propos d'une refonte drastique.

J'utilise un dictionnaire pour tenir des objets

Dictionary<Node, int> dConnections 

L'objet Node est en soi un objet complexe contenant de nombreux attributs et des listes. Ce dictionnaire peut devenir assez volumineux avec environ 100 entrées ou plus.

Actuellement, le dictionnaire est en cours de vérification si elle contient un noeud comme

dConnections.ContainsKey(Node) 

donc je présume que (pour vérifier si ce noeud est dans le dictionnaire) le dictionnaire devra vérifier si le nœud entier et ses attributs correspondent à un nœud dans le dictionnaire (il continuera à parcourir le dictionnaire jusqu'à ce qu'il trouve une correspondance) et cela aura un impact majeur sur les performances? Je ferais mieux de ne pas utiliser un objet dans le dictionnaire et d'utiliser plutôt l'identifiant d'objet.

Answer 1

Le dictionnaire .NET est une hashtable dans l'intérieur. Cela signifie que si Node ne remplace pas les méthodes GetHashCode et Equals, lorsque vous appelez ContainsKey, il sera comparé à:

Avertissement: C'est un résumé. Les choses sont un peu plus compliquées. S'il vous plaît, ne m'appelez pas parce que j'ai trop simplifié.

1. une partition du code de hachage de l'adresse de référence de l'objet noeud. Le nombre de partitions dépend du nombre de compartiments de la table de hachage (en fonction du nombre total de clés dans le dictionnaire)
2. l'adresse de référence exacte si plus d'un nœud se trouve dans le même compartiment.

Cet algorithme est très efficace. Quand vous dites que vous avez 100 entrées ou plus dans le dictionnaire, ce n'est pas "beaucoup". C'est un peu. Cela signifie également que le contenu de l'objet Node n'a rien à voir avec la façon dont ContainsKey va correspondre. Il va correspondre exactement à la même référence, et seulement contre cette référence.

Si vous implémentez GetHashCode et que vous êtes égaux, sachez que ces valeurs de retour de méthode ne doivent pas changer lorsque la propriété de l'instance change (être immuable). Sinon, vous pourriez bien avoir des clés dans le mauvais compartiment, et donc complètement inaccessible (sans énumérer le dictionnaire entier).

Answer 2

il continuera à parcourons le dictionnaire jusqu'à ce qu'il trouve une correspondance

Non, dictionnaires ne trouvent pas les correspondances par itérer tous les nœuds; le code de hachage est obtenue en premier lieu, et est utilisé pour limiter les candidats à un, peut-être un peu (selon la qualité de votre méthode de hachage est, et le seau taille)

donc je présume que (à vérifier si ce nœud est dans le dictionnaire) le dictionnaire devra vérifier si le nœud entier et ses attributs correspondent à un nœud dans le dictionnaire

Non, pour chaque candidat, il vérifie d'abord le code de hachage, qui est destiné à être un raccourci pour détecter non -equality vs possible -égalité très rapidement

Donc la clé ici est: la méthode de hachage de votre Node, aka GetHashCode. Si cela est complexe, puis une autre astuce consiste à ce cache la première fois que vous avez besoin, à savoir

int cachedHashCode; 
public override int GetHashCode() { 
    if(cachedHashCode == 0) { 
     cachedHashCode = /* some complex code here */ 
     if(cachedHashCode == 0) { 
      cachedHashCode = -45; // why not... just something non-zero 
     } 
    } 
    return cachedHashCode; 
} 

Notez qu'il ne utilise encore Equals aussi, comme la finale « sont-ils les mêmes », de sorte que vous évidemment vouloir Equals être aussi rapide que possible aussi - mais Equals sera appelé relativement rarement.