Complexity of searching in a list and in a dictionary

Let's say I have a class:

class C
{
    public int uniqueField;
    public int otherField;
}

This is very simplified version of the actual problem. I want to store multiple instances of this class, where "uniqueField" should be unique for each instance.

What is better in this case?

a) Dictionary with uniqueField as the key

Dictionary<int, C> d;

or b) List? 

List<C> l;

In the first case (a) the same data would be stored twice (as the key and as the field of a class instance). But the question is: Is it faster to find an element in dictionary than in list? Or is the equally fast?

a)

d[searchedUniqueField]

b)

l.Find(x=>x.uniqueField==searchedUniqueField);
Jon Skeet
people
quotationmark

Assuming you've got quite a lot of instances, it's likely to be much faster to find the item in the dictionary. Basically a Dictionary<,> is a hash table, with O(1) lookup other than due to collisions.

Now if the collection is really small, then the extra overhead of finding the hash code, computing the right bucket and then looking through that bucket for matching hash codes, then performing a key equality check can take longer than just checking each element in a list.

If you might have a lot of instances but might not, I'd usually pick the dictionary approach. For one thing it expresses what you're actually trying to achieve: a simple way of accessing an element by a key. The overhead for small collections is unlikely to be very significant unless you have far more small collections than large ones.

people

See more on this question at Stackoverflow