5

What is the best data structure in .Net with high performance lookup, like a binary tree implementation, but to store only the keys (string keys) ?

We need only to check if a certain key is present in the collection. Like:

Dictonary<string, object> myKeys;
myKeys.Add("key1", null);
myKeys.Add("key2", null);
// Dozens or hundreds keys

Assert.IsTrue(myKeys.Contains("key1"));
Mitch Wheat
  • 295,962
  • 43
  • 465
  • 541
Luciano
  • 2,695
  • 6
  • 38
  • 53

1 Answers1

17

A HashSet (in System.Collections.Generic):

HashSet is an unordered collection containing unique elements. It has the standard collection operations Add, Remove, Contains, but since it uses a hash-based implementation, these operation are O(1).

e.g.

    HashSet<int> evenNumbers = new HashSet<int>();
    HashSet<int> oddNumbers = new HashSet<int>();

    for (int i = 0; i < 5; i++)
    {
        // Populate numbers with just even numbers.
        evenNumbers.Add(i * 2);

        // Populate oddNumbers with just odd numbers.
        oddNumbers.Add((i * 2) + 1);
    }

    if (evenNumbers.Contains(2))
    {
        Console.WriteLine("2 is even.");
    }
Community
  • 1
  • 1
Mitch Wheat
  • 295,962
  • 43
  • 465
  • 541
  • HashSet documentation (http://goo.gl/wu9xlh) just says it's a "a set of values", nothing more in remarks, nothing about the algorithm. Although we could assume its implementation as a "hash-based" by its name, so it could be O(1) if well implemented, why are you sure about this ? How to get and be sure about this ? Disassembling ? – Luciano Dec 10 '13 at 13:40
  • 2
    @Luciano: If you check the documentation for [HashSet.Add](http://msdn.microsoft.com/en-us/library/bb353005.aspx) and [HashSet.Contains](http://msdn.microsoft.com/en-us/library/bb356440.aspx) (and the rest of the methods), you'll see remarks describing the algorithmic complexity. In particular, `Contains` is O(1), and `Add` is O(1) as long as the internal array doesn't have to be resized. – Jim Mischel Dec 10 '13 at 16:39
  • @JimMischel: Diffuse but sure, is there. Thanks by the help. – Luciano Dec 10 '13 at 16:57