Quelle est la complexité du temps de consultation de HashSet<T>(IEqualityComparer<T>) ?

Question

En C#.NET, j'aime utiliser les HashSets en raison de leur complexité temporelle O(1) supposée pour les recherches. Si j'ai un grand ensemble de données qui va être interrogé, je préfère souvent utiliser un HashSet plutôt qu'une liste, car il a cette complexité temporelle.

Ce qui me perturbe, c'est le constructeur du HashSet, qui prend IEqualityComparer comme argument :

http://msdn.microsoft.com/en-us/library/bb359100.aspx

Dans le lien ci-dessus, les remarques indiquent que le "constructeur est une opération O(1)", mais si c'est le cas, je suis curieux de savoir si la recherche est toujours O(1).

En particulier, il me semble que si j'écrivais un Comparer à passer dans le constructeur d'un HashSet, à chaque fois que j'effectue une recherche, le code du Comparer devrait être exécuté sur chaque clé pour vérifier s'il y a une correspondance. Ce ne serait pas O(1), mais O(n).

L'implémentation construit-elle en interne une table de recherche au fur et à mesure que des éléments sont ajoutés à la collection ?

D'une manière générale, comment puis-je obtenir des informations sur la complexité des structures de données .NET ?

Answer 1

A HashSet fonctionne par hachage (via IEqualityComparer.GetHashCode ) les objets que vous insérez et les jette dans les godets en fonction du hachage. Les godets eux-mêmes sont stockés dans un tableau, d'où la partie O(1).

Par exemple (ce n'est pas nécessairement la façon dont l'implémentation C# fonctionne, cela donne juste une idée), il prend le premier caractère du hachage et jette tout ce qui a un hachage commençant par 1 dans le seau 1. Le hash de 2, le seau 2, et ainsi de suite. À l'intérieur de ce seau se trouve un autre tableau de seaux qui se divise en fonction du deuxième caractère du hachage. Ainsi, pour chaque caractère du hachage....

Désormais, lorsque vous recherchez quelque chose, le système l'analyse et le fait passer par les catégories appropriées. Il doit effectuer plusieurs recherches dans le tableau (une pour chaque caractère du hachage) mais ne croît pas en fonction de N, le nombre d'objets que vous avez ajoutés, d'où la notation O(1).

Pour répondre à votre autre question, voici un billet de blog présentant la complexité de certaines opérations de collecte : http://c-sharp-snippets.blogspot.com/2010/03/runtime-complexity-of-net-generic.html

Answer 2

si je devais écrire un Comparer à passer dans le constructeur d'un HashSet, à chaque fois que j'effectue une recherche, le code du Comparer devrait être exécuté sur chaque clé pour vérifier s'il y a une correspondance. Ce ne serait pas O(1), mais O(n).

Appelons la valeur recherchée la valeur "requête".

Pouvez-vous expliquer pourquoi vous pensez que le comparateur doit être exécuté sur chaque clé pour voir si elle correspond à la requête ?

Cette croyance est fausse. (Sauf bien sûr si le code de hachage fourni par le comparateur est le même pour chaque clé !) L'algorithme de recherche exécute le comparateur d'égalité sur chaque clé dont le code de hachage correspond au code de hachage de la requête, modulo le nombre de godets dans la table de hachage. C'est ainsi que les tables de hachage ont un temps de consultation de O(1).

L'implémentation construit-elle en interne une table de recherche au fur et à mesure que des éléments sont ajoutés à la collection ?

Oui.

D'une manière générale, comment puis-je obtenir des informations sur la complexité des structures de données .NET ?

Lire la documentation.

Answer 3

En fait, le temps de consultation d'un HashSet<T> n'est pas toujours O(1).

Comme d'autres l'ont déjà mentionné, un HashSet utilise IEqualityComparer<T>.GetHashCode() .
Considérons maintenant une structure ou un objet qui renvoie toujours le même code de hachage x .

Si vous ajoutez n éléments à votre HashSet, il y aura n éléments avec le même hash (tant que les objets ne sont pas égaux).
Ainsi, si vous deviez vérifier si un élément avec le code de hachage x existe dans votre HashSet, il effectuera des contrôles d'égalité pour tous les objets ayant le code de hachage x pour tester si le HashSet contient l'élément

Answer 4

Cela dépend de la qualité de la fonction de hachage ( GetHashCode() ) votre IEqualityComparer La mise en œuvre de la politique de l'UE en matière d'éducation et de formation est une priorité. La fonction de hachage idéale devrait fournir un ensemble aléatoire bien réparti de codes de hachage. Ces codes de hachage seront utilisés comme un index qui permet de faire correspondre une clé à une valeur, de sorte que la recherche d'une valeur par clé devient plus efficace, en particulier lorsque la clé est un objet ou une structure complexe.

le code Comparer devrait être exécuté sur chaque touche pour vérifier que s'il y a une correspondance. Ce ne serait pas O(1), mais O(n).

Ce n'est pas ainsi que fonctionne hashtable, il s'agit d'une sorte de recherche brute directe. Dans le cas de la table de hachage, l'approche est plus intelligente et utilise la recherche par index (code de hachage).

Answer 5

La recherche est toujours O(1) si vous passez un IEqualityComparer. L'ensemble de hachage utilise toujours la même logique que si vous ne passe un IEqualityComparer ; il utilise simplement les implémentations de GetHashCode et Equals de l'IEqualityComparer au lieu des méthodes d'instance de System.Object (ou des surcharges fournies par l'objet en question).