Collection 'correcte' à utiliser pour obtenir des objets en O (1) en C# .NET?

Question

Quelque chose que je fais souvent si je stocker un tas de valeurs de chaîne et je veux être en mesure de les trouver dans O (1) plus tard est-:

foreach (String value in someStringCollection) 
{ 
    someDictionary.Add(value, String.Empty); 
} 

De cette façon, je peux facilement effectuer constante -Temps sur ces valeurs lookups de chaîne plus tard sur, tels que:

if (someDictionary.containsKey(someKey)) 
{ 
    // etc 
} 

Cependant, je me sens comme je triche en faisant la valeur String.Empty. Y a-t-il une collection .NET plus appropriée que je devrais utiliser?

Answer 1

Si vous utilisez .Net 3.5, essayez HashSet. Si vous n'utilisez pas .Net 3.5, essayez C5. Sinon, votre méthode actuelle est ok (bool que @leppie suggère est mieux, ou pas comme @JonSkeet suggère, dun dun dun!).

HashSet<string> stringSet = new HashSet<string>(someStringCollection); 

if (stringSet.Contains(someString)) 
{ 
    ... 
} 

Answer 2

Vous pouvez utiliser HashSet<T> dans .NET 3.5, sinon je voudrais juste coller à vous méthode actuelle (en fait, je préférerais Dictionary<string,bool> mais on n'a pas toujours ce luxe).

Answer 3

Quelque chose que vous pourriez vouloir ajouter est une taille initiale à votre hachage. Je ne suis pas sûr que C# soit implémenté différemment de Java, mais il a généralement une taille par défaut, et si vous ajoutez plus que cela, il étend l'ensemble. Cependant, un hachage correctement dimensionné est important pour atteindre le plus possible O (1). Le but est d'obtenir exactement 1 entrée dans chaque seau, sans le rendre vraiment énorme. Si vous effectuez une recherche, je sais qu'il existe un ratio suggéré pour le dimensionnement de la table de hachage, en supposant que vous sachiez à l'avance combien d'éléments vous allez ajouter. Par exemple, quelque chose comme "le hachage doit être dimensionné à 1,8 fois le nombre d'éléments à ajouter" (pas le ratio réel, juste un exemple).

De Wikipedia:

Avec une bonne fonction de hachage, une table de hachage peut généralement contenir environ 70% -80% autant d'éléments comme il le fait fentes de table et effectuer encore bien. En fonction de la résolution de collision mécanisme, les performances peuvent commencer à souffrir soit progressivement ou de façon spectaculaire que plus d'éléments sont ajouté. Pour traiter cela, lorsque le facteur de charge dépasse un certain seuil, il est nécessaire d'allouer une nouvelle table plus grande, , et d'ajouter tout le contenu de la table originale à cette nouvelle table. Dans la classe HashMap de Java, par exemple, le seuil du facteur de charge par défaut est de 0,75.

Answer 4

Je devrais probablement faire une question, parce que je vois le problème si souvent. Qu'est-ce qui vous fait penser que les dictionnaires sont O (1)? Techniquement, la seule chose susceptible d'être quelque chose comme O (1) est l'accès à un tableau fixe lié par un entier standard utilisant une valeur d'index entière (il n'y a pas de recherche dans les tableaux implémentés de cette façon).

La présomption que si elle ressemble à un tableau de référence, il est O (1) lorsque le « index » est une valeur qui doit être recherché en quelque sorte, mais dans les coulisses, signifie qu'il est peu probable d'O (1) sauf si vous avez la chance d'obtenir une fonction de hachage avec des données sans collisions (et probablement beaucoup de cellules gaspillées).

Je vois ces questions et je vois même des réponses qui prétendent O (1) [pas sur cette question particulière, mais je les vois autour], sans justification ou explication de ce qui est nécessaire pour s'assurer O (1) est effectivement atteint.

Hmm, je suppose que c'est une question décente. Je le ferai après avoir posté cette remarque ici.