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
1  
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

8 Answers 8

up vote 18 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
2  
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

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
6  
+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
    
Last not least, when you know what you are looking for, the hash table is around O(1) time, while the array is O(logN) in the best case (sorted and w/o duplicates) and O(N) in the worst case. –  JensG Aug 5 at 23:11
    
+1. No one else seems to have addressed the point that lists are semantically ordered and dicts are semantically lookups, which is absolutely fundamental, in my opinion. –  Benjamin Hodgson Aug 6 at 11:56

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
5  
this is the important difference imho, Dictionary<int,int> can be sparse –  jk. Oct 31 '12 at 9:28

How can anyone consider them equivalent?

Dictionary is sparse and permits random insertions but makes in-order traversal a problem, List is not sparse and an out of order insertion is expensive, it inherently provides in-order traversal.

There would be very few situations where one wasn't dramatically superior to the other.

share|improve this answer

Aside: Other programming languages refer to this type of data structure as a Map, rather than a Dictionary.

If your data can meaningfully be defined as key/value pairs, then a Dictionary will provide much faster access if you need to find a value using its key.

For example, suppose you have a list of Customers. Each Customer includes details such as a name and address, and a unique customer number. Suppose you also have a list of Orders being processed. Each Order will contain details of what is being made, and will need to include the customer number of the person who ordered it.

When an order is ready to ship, you need to find the address to ship it to. If the customers are stored as a plain List, then you need to search the entire list to find the customer with the right customer number. Instead, you could store the customers in a Dictionary, with the customer number as the key. The Dictionary will now let you pull out the correct customer in one step without any searching.

share|improve this answer

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

If the code in question is storing two sets of correlated values, the Dictionary class provides an indexed way of looking up values by a key. If there is only one set of values, but that set needs to be accessed randomly (perhaps to check for the existence of a key in a set), and the values are unique, a HashSet might be the best set class to use.

share|improve this answer

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

protected by gnat Aug 5 at 22:14

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

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