Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

So I ran into a Dictionary<int, int> today at work. This just seemed weird to me because I would have probably just used a List<int> instead. Is there a difference and would there be a use case where one structure would be preferred over the other?

share|improve this question
    
Does there need to be a relation between two(or more) given ints? Then the map(dictionary in this language) makes sense. –  Rig Mar 10 '12 at 3:27
2  
The name dictionary makes it obvious to me. When you need to look something up quick you use a dictionary. –  ChaosPandion Mar 10 '12 at 5:51
2  
@ChaosPandion: a List<T> within the .NET framework is a random access array, where a lookup operation is typically faster than for a Dictionary<int,T>. –  Doc Brown Mar 10 '12 at 9:36
1  
@DocBrown - Only in the rather weird case of using the numeric index as the key. Other wise a look up is gonna be faster when using Dictionary<TKey, TValue>. –  ChaosPandion Mar 10 '12 at 17:45
1  
@chaos this question is about that weird case. –  MarkJ Oct 31 '12 at 7:18
show 2 more comments

5 Answers

up vote 16 down vote accepted

You would use a Dictionary<int, int> if your indexes have a special meaning besides just positional placement.

The immediate example that comes to mind is storing an id column and an int column in a database. For example, if you have a [person-id] column and a [personal-pin] column, then you might bring those into a Dictionary<int, int>. This way pinDict[person-id] gives you a PIN, but the index is meaningful and not just a position in a List<int>.

But really, any time you have two related lists of integers, this could be an appropriate data structure.

share|improve this answer
    
If my person-id is from a range 0,...,999, and I would have to load the personal-pin values into memory for all 1000 persons, I would typically choose a List<int>, and not a dictionary. See my answer below. –  Doc Brown Mar 10 '12 at 9:27
    
yes but a dictionary can be sparse –  jk. Mar 10 '12 at 10:16
    
@jk: that is exactly what I tried to elaborate in my answer. –  Doc Brown Mar 10 '12 at 10:29
5  
Personal PIN? Sounds kinda redundant. –  Jack Apr 30 '12 at 6:27
    
Hm, when the index has "a special meaning", in real world-scenarios it may be likely that they do not form a contiguous range [0,...,n] (though this is not mandatory), so this answer is not plain wrong, but imprecise. Nevertheless IMHO the decision should not be based on this "special meaning thing", but only on "do the keys build approximately an interval [0,...,n]". Based on the number of upvotes I guess most readers missed that point. –  Doc Brown Dec 13 '13 at 8:37
show 1 more comment

Semantically, a Dictionary<int, T> and List<T> are very similar, both are random access containers of the .NET framework. To use a list as a replacement for a dictionary, you need a special value in your type T (like null) to represent the empty slots in your list. If T is not a nullable type like int, you could use int? instead, or if you are just expecting to store positive values, you could also use a special value like -1 to represent empty slots.

Which one you will choose should depend on the range of the key values. If your keys in the Dictionary<int, T> are within an integer interval, without many gaps between them (for example, 80 values out of [0,...100]), then a List<T> will be more appropriate, since the accessing by index is faster, and there is less memory and time overhead compared to a dictionary in this case.

If your key values are 100 int values from a range like [0,...,1000000], then a List<T> needs memory to hold 1000000 values of T, where your dictionary will just need memory in an order of magnitude around 100 values of T, 100 values of int (plus some overhead, in reality expect about 2 times the memory for storing those 100 keys and values). So in the latter case a dictionary will be more appropriate.

share|improve this answer
4  
this is the important difference imho, Dictionary<int,int> can be sparse –  jk. Oct 31 '12 at 9:28
add comment

Think of the List as an array and the Dictionary as a hash table. You would only use the Dictionary if you needed to map (or associate) meaningful keys to values, whereas a List only maps (or associates) positions (or indices) to values.

For example, say you wanted to store an association between a person's age and their height. You could use a Dictionary<int, int> to map the person's age (an int) to their height (an int):

Dictionary<int, int> personHeightMap = new Dictionary<int, int>();

personHeightMap.Add(21, 185);
personHeightMap.Add(31, 174);

int height = personHeightMap.ContainsKey(21) ? personHeightMap[21] : -1;

Not a very useful example, but the point is you wouldn't be able to do this as elegantly with a List because it would need to store these values positionally.

share|improve this answer
2  
+1 for mentioning that a List deals with order, where a Dictionary deals with association. If you need to get your data in a certain order every time, or their order in relation to each other is important, a List is the way to go. Dictionaries tend to be unordered, and deal with mapping key -> value relationships. –  KChaloux Dec 13 '13 at 13:51
add comment

The Dictionary uses hashing to search for the data. A Dictionary first calculated a hash value for the key and this hash value leads to the target data bucket. After that, each element in the bucket needs to be checked for equality. But actually the list will be faster than the dictionary on the first item search because nothing to search in the first step. But in the second step, the list has to look through the first item, and then the second item. So each step the lookup takes more and more time. The larger the list, the longer it takes.

More about .... Dictionary Vs List with example.

share|improve this answer
add comment

These are great answers that seem to cover the bases.

Another consideration I will offer is that Dictionaries (in C#) are more complex from a coding perspective. Having both lists and dictionaries in the same codebase makes your code harder to maintain in that both methods have subtle differences in how to do basic operations such as searching and marshalling object data. My perspective is that unless you need a dictionary for some justifiable reason, use a list.

share|improve this answer
4  
I disagree. Dictionary/map is a fundamental data structure that every software engineer should be intimately familiar with. Either way: you would need a justifiable reason to use any data structure; including List. –  Steve Evers Dec 12 '13 at 21:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.