CODEWITHSUNDEEP
c#dictionarygeneric-list
ina
ina

Reputation: 19534

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

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

Upvotes: 5

Views: 2688

Answers (3)

D Stanley
D Stanley

Reputation: 152521

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

Upvotes: 9

123 456 789 0
123 456 789 0

Reputation: 10865

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.

Upvotes: 2

Mark
Mark

Reputation: 1371

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

Upvotes: 5

Related Questions