fastest way to find string in C# ?

Question

What is the fastest way to implement something like this in C#:

  private List<string> _myMatches = new List<string>(){"one","two","three"};
  private bool Exists(string foo) {
      return _myMatches.Contains(foo);
  }

note, this is just a example. i just need to perform low level filtering on some values that originate as strings. I could intern them, but still need to support comparison of one or more strings. Meaning, either string to string comparison (1 filter), or if string exists in string list (multiple filters).

Answer 1

Hash tables are your friends for fast string lookups.

Have a look at a good tutorial at Working with HashTable in C# 2.0

Answer 2

You could make this faster by using a HashSet<T>, especially if you're going to be adding a lot more elements:

private HashSet<string> _myMatches = new HashSet<string>() { "one", "two", "three" };

private bool Exists(string foo)
{
    return _myMatches.Contains(foo);
}

This will beat out a List<T> since HashSet<T>.Contains is an O(1) operation.

List<T>'s Contains method, on the other hand, is O(N). It will search the entire list (until a match is found) on each call. This will get slower as more elements are added.

Answer 3

You are going to have to profile. And do you mean fastest lookup (ie, does initialization time count)?

@Elf King already mentioned Hash Tables, which I was going to point you at (specifically HashSet<T>)