Dictionary, List or Array? [closed]

Question

I'm writing a service where performance is essential, and I'm not sure what is the fastest thing. I have a few Objects (50-200) which each have an ID in them (ints, e.g. 84397 or 23845). Would it be faster to have a Dictionary, a List of KeyValue Pairs or a List with the indexes set to the IDs with the rest having null values or an array with the same idea?

Answer 1

It depends on which operation you want to execute. Let's assume that you want to find an object with a given ID.

• The huge array approach is fastest: Accessing myArray[84397] is a constant-time operation O(1). Of course, this approach requires the most memory.
• The dictionary is almost as fast but requires less memory, since it uses a hash table internally.
• The list of pairs approach is the slowest, since you might have to traverse the whole list to find your entry, which yields O(n) complexity.

Thus, in your situation, I would choose the dictionary, unless the marginally better performance of the huge array is really relevant in your case.

Answer 2

Dictionary<TKey, TValue> uses a hash table internally so I think it would be the fastest one.

Answer 3

Dictionary versus List Lookup time

Also, for a more detailed explaination of the different collections, check out this question.