28

I need a list of strings and a way to quickly determine if a string is contained within that list.

To enhance lookup speed, I considered SortedList and Dictionary; however, both work with KeyValuePairs when all I need is a single string.

I know I could use a KeyValuePair and simply ignore the Value portion. But I do prefer to be efficient and am just wondering if there is a collection better suited to my requirements.

7 Answers 7

38

If you're on .NET 3.5 or higher, use HashSet<String>.

Failing that, a Dictionary<string, byte> (or whatever type you want for the TValue type parameter) would be faster than a SortedList if you have a lot of entries - the latter will use a binary search, so it'll be O(log n) lookup, instead of O(1).

3
  • @Jonathan: Agreed - such is life though. In .NET 4 there's an interface to represent sets (ISet<T>) and also another option in SortedSet<T> (which again wouldn't be particularly useful in this case).
    – Jon Skeet
    Apr 3, 2011 at 17:37
  • I was just looking back at this. A O(1) lookup is fast indeed. However, I'm guessing this collection implements some sort of hashing. So doesn't O(1) assume no collisions? (BTW, I'm working my way through your book.) Jun 16, 2011 at 16:13
  • @Jonathan: It's O(1) if the hash is reasonable, so there aren't too many collisions.
    – Jon Skeet
    Jun 16, 2011 at 16:14
10

If you just want to know if a string is in the set use HashSet<string>

5

This sounds like a job for

 var keys = new HashSet<string>();

Per MSDN: The Contains function has O(1) complexity.

But you should be aware that it does not give an error for duplicates when adding.

1
  • 3
    To be more precise the Add method does not throw an exception but it does return true if the key was added and false if it was already present. Apr 3, 2011 at 17:35
3

HashSet<string> is like a Dictionary, but with only keys.

1

If you feel like rolling your own data structure, use a Trie. http://en.wikipedia.org/wiki/Trie

worst-case is if the string is present: O(length of string)

1

I know this answer is a bit late to this party, but I was running into an issue where our systems were running slow. After profiling we found out there was a LOT of string lookups happening with the way we had our data structures structured.

So we did some research, came across these benchmarks, did our own tests, and have switched over to using SortedList now.

if (sortedlist.ContainsKey(thekey))
{   
//found it.
}

Even though a Dictionary proved to be faster, it was less code we had to refactor, and the performance increase was good enough for us.

Anyway, wanted to share the website in case other people are running into similar issues. They do comparisons between data structures where the string you're looking for is a "key" (like HashTable, Dictionary, etc) or in a "value" (List, Array, or in a Dictionary, etc) which is where ours are stored.

1

I know the question is old as hell, but I just had to solve the same problem, only for a very small set of strings(between 2 and 4).

In my case, I actually used manual lookup over an array of strings which turned up to be much faster than HashSet<string>(I benchmarked it).

for (int i = 0; i < this.propertiesToIgnore.Length; i++)
{
    if (this.propertiesToIgnore[i].Equals(propertyName))
    {
        return true;
    }
}

Note, that it is better than hash set for only for tiny arrays!

EDIT: works only with a manual for loop, do not use LINQ, details in comments

2
  • Yes, HashSet<> has some overhead. I would only recommend it when searching larger collections. BTW, your code could be shortened to something like return PropertiesToIgnore.Any(p => p.Equals(propertyName)) Jan 14, 2018 at 16:12
  • Unfortunately, using Linq slows down execution by a factor of 10! Benchmark results ArrayManualLoop: 6.018 ns ArrayLinq: 59.171 ns. Linq thorns the processor cache apart, and all the possible gains are lost. Jan 14, 2018 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.