List<T>.Contains() is very slow?

Question

Could anyone explain me why the generics List.Contains() function is so slow?

I have a List<long> with about a million numbers, and the code that is constantly checking if there's a specific number within these numbers.

I tried doing the same thing using Dictionary<long, byte> and the Dictionary.ContainsKey() function, and it was about 10-20 times faster than with the List.

Of course, I don't really want to use Dictionary for that purpose, because it wasn't meant to be used that way.

So, the real question here is, is there any alternative to the List<T>.Contains(), but not as whacky as Dictionary<K,V>.ContainsKey() ?

Answer 1

If you are just checking for existence, HashSet<T> in .NET 3.5 is your best option - dictionary-like performance, but no key/value pair - just the values:

    HashSet<int> data = new HashSet<int>();
    for (int i = 0; i < 1000000; i++)
    {
        data.Add(rand.Next(50000000));
    }
    bool contains = data.Contains(1234567); // etc