Devrais-je utiliser un dictionnaire C # si je n'ai besoin que d'une recherche rapide des clés et que les valeurs ne sont pas pertinentes?

Question

J'ai besoin d'un type de données capable d'insérer des entrées, puis de déterminer rapidement si une entrée a déjà été insérée. A Dictionary semble répondre à ce besoin (voir exemple). Cependant, je n'ai aucune utilité pour le dictionnaire values . Devrais-je toujours utiliser un dictionnaire ou existe-t-il un autre type de données mieux adapté?

 public class Foo
{
    private Dictionary<string, bool> Entities;

    ...

    public void AddEntity(string bar)
    {
        if (!Entities.ContainsKey(bar))
        {
            // bool value true here has no use and is just a placeholder
            Entities.Add(bar, true);
        }
    }

    public string[] GetEntities()
    {
        return Entities.Keys.ToArray();
    }

}
 

Answer 1

Vous pouvez utiliser HashSet<T> .

La classe HashSet<T> fournit des opérations d'ensemble hautement performantes. Un ensemble est une collection qui ne contient aucun élément en double et dont les éléments ne sont dans aucun ordre particulier .

Answer 2

Habib de réponse est excellent, mais pour les environnements multi-threads si vous utilisez un HashSet<T> puis par conséquent, vous devez utiliser locks pour protéger l'accès. Je me trouve plus enclins à créer des blocages avec lock des déclarations. Aussi, locks rendement pire speedup par la loi d'Amdahl car l'ajout d'un lock déclaration permet de réduire le pourcentage de votre code qui est en fait parallèle.

Pour ces raisons, un ConcurrentDictionary<T,object> correspond à la facture dans les environnements multi-threadés. Si vous vous retrouvez à l'aide de l'un, puis l'envelopper comme vous l'avez fait dans votre question. Juste new jusqu' objects à jeter dans les valeurs que nécessaire, car les valeurs ne sera pas important. Vous pouvez vérifier qu'il n'existe pas lock états dans son code source.

Si vous n'avez pas besoin de la mutabilité de la collection puis ce serait discutable. Mais votre question implique que vous n'en avez pas besoin, puisque vous avez un AddEntity méthode.

Pour plus d'infos, 2017-05-19 - en fait, ConcurrentDictionary n' utiliser des verrous à l'interne, bien que non lock des déclarations en soi--il utilise Monitor.Enter (découvrez l' TryAddInternal méthode). Cependant, il semble verrouillage sur certains des seaux dans le dictionnaire, ce qui signifie qu'il y aura moins de demande que de mettre toute chose en lock déclaration.

Donc dans l'ensemble, ConcurrentDictionary est souvent mieux pour les environnements multithreads.

C'est en fait assez difficile (impossible?) pour faire une concurrente de hachage en n'utilisant que le Contrefil méthodes. J'ai essayé sur mon propre et restent en cours d'exécution dans le problème d'avoir à modifier deux choses en même temps, quelque chose que seul le verrouillage peut faire en général. Une solution de contournement que j'ai trouvé est d'utiliser liée individuellement des listes pour le hachage de seaux et de créer intentionnellement des cycles d'une liste lorsqu'un thread pour opérer sur un nœud sans interférence avec d'autres threads, ce qui amènerait à d'autres threads pour se faire prendre la filature dans le même endroit jusqu'à ce que le thread a été fait avec son nœud et défit le cycle. Bien sûr, techniquement il n'a pas utiliser des verrous, mais il n'a pas à l'échelle.