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")){ ... }

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?)

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