C# - Searching keys of dictionary vs searching values in List

Question

In terms of speed in search, is it better to search the keys of a dictionary or the values of a list?

In other words, which of these would be most preferable?

Dictionary<tring,string> dic = new Dictionary<string,string>();
if(dic.ContainsKey("needle")){ ... }

Or

List<string> list = new List<string>();
if(list.Contains("needle")){ ... }

Deviation

In the general case a dictionary will provide faster lookup times. However it also depends on the data size and the usage patterns. To say for sure, you'd need to elaborate on those fronts. – Fungible

dictionary is o(1) whereas list is o(n) operation – Vacuva

Answer 1

If by "better" you mean "faster" then use a dictionary. Dictionary keys are organized by hash codes so lookups are significantly faster that list searches with more than just a few items in the ocllection.

With a good hashing algorithm, Dictionary searches can be close to O(1), meaning the search time is independent of the size of the dictionary. Lists, on the other hand, are O(n), meaning that the time is (on average) proportional to the size of the list.

If you just have key items (not mapping keys to values) you might also try a HashSet. It has the benefit of O(1) lookups without the overhead of the Value side of a dictionary.

(Granted the overhead is probably minimal, but why have it if you don't need it?)

Bushey

Answer 2

For lookups a dictionary is usually best because the time it takes remains constant. With a list it increases the larger the list gets.

See also: http://www.dotnetperls.com/dictionary-time

Kamacite

Answer 3

I suggest using Dictionary when the number of lookups greatly exceeds the number of insertions. It is fine to use List when you will always have fewer than four items.

For lookups, Dictionary is usually a better choice. The time required is flat, an O(1) constant time complexity. The List has an O(N) linear time complexity. Three elements can be looped over faster than looked up in a Dictionary.

Lemonade

@DStanley Yes but the OP is asking in terms of speed search and if it is based on lookups then Dictionary is more preferrable even with 5 items. If his scenario doesn't care about the order then I would use HashSet even if it is just 5 items. – Lemonade