À quelle vitesse l’opération sur KeyCollection est-elle renvoyée par Dictionary.Keys? (.NET)

IDictionary définit la méthode IDictionary.ContainsKey(in TK) et la propriété IDictionary.Keys (de type ICollection ). Je suis intéressé par la complexité (asymptotique) de cette méthode et de cette propriété dans l’implémentation de Dictionary d’ IDictionary .

Considérer les définitions

 IDictionary dict = new Dictionary(); int k = new Random().Next();

et considérons que nous avons ajouté au dictionnaire dict n KeyValuePair s unique.

Quelle est la complexité attendue (asymptotique) d’un appel dict.ContainsKey(k) ? J’espère que c’est dans O(1) mais je ne l’ai pas trouvé dans la documentation de Dictionary.ContainsKey .

Quelle est la complexité attendue (asymptotique) de l’appel dict.Keys.Contains(k) ? J’espère que c’est dans O(1) mais je ne l’ai pas trouvé dans la documentation de Dictionary.Keys ni dans la documentation de Dictionary.KeyCollection . Si c’est dans O(1) je ne comprends pas pourquoi le type de propriété IDictionary.Keys est ICollection et non ISet (comme en Java par exemple).

Comme IDictionary n’est qu’une interface et non une implémentation, il ne fournit aucune garantie de performances.

Pour le type de Dictionary intégré Dictionary , la méthode ContainsKey doit être O (1):

Cette méthode est proche d’une opération O (1).

La méthode Keys.Contains appelle en fait la méthode ContainsKey du dictionnaire parent. Elle doit donc également être O (1):

Cette méthode est une opération O (1).

(Les deux citations sont extraites de la section “Remarques” des pages de documentation correspondantes.)

Le premier lien que vous avez fourni indique, dans les remarques:

Cette méthode est proche d’une opération O (1).

De plus, si vous cliquez sur la méthode Contains , vous verrez la même chose dans les remarques:

Cette méthode est une opération O (1).