32

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?

Improve this question
8
  • 1
    Does there need to be a relation between two(or more) given ints? Then the map(dictionary in this language) makes sense. Commented Mar 10, 2012 at 3:27
  • 4
    The name dictionary makes it obvious to me. When you need to look something up quick you use a dictionary. Commented Mar 10, 2012 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>. Commented Mar 10, 2012 at 9:36
  • 3
    @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>. Commented Mar 10, 2012 at 17:45
  • 3
    @chaos this question is about that weird case. Commented Oct 31, 2012 at 7:18

7 Answers 7

Reset to default
33

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.

Improve this answer
6
  • 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. Commented Mar 10, 2012 at 9:27
  • 4
    yes but a dictionary can be sparse Commented Mar 10, 2012 at 10:16
  • @jk: that is exactly what I tried to elaborate in my answer. Commented Mar 10, 2012 at 10:29
  • 8
    Personal PIN? Sounds kinda redundant. Commented Apr 30, 2012 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. Commented Dec 13, 2013 at 8:37
28

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.

Improve this answer
3
  • 7
    +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. Commented Dec 13, 2013 at 13:51
  • 2
    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. Commented Aug 5, 2014 at 23:11
  • 1
    +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. Commented Aug 6, 2014 at 11:56
16

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.

Improve this answer
5
  • 8
    this is the important difference imho, Dictionary<int,int> can be sparse Commented Oct 31, 2012 at 9:28
  • In that case, Can't we use List<KeyValuePair<int,int>>? Which one would be better for linear traversal? Commented Feb 14, 2018 at 8:06
  • @DeepakMishra: the main difference here is, with List<KeyValuePair<int,T>>, there is no O(1) lookup operation available. Second, elements in List<KeyValuePair<int,T>> can have a specific ordering, independent from their key values. If you need the latter but not the former, List<KeyValuePair<int,T>> or List<Tuple<int,T>> might be the better choice. If you need both, there is also OrderedDictionary. Commented Feb 14, 2018 at 10:19
  • @DocBrown Which one would be better for linear traversal(i.e foreach) and insert operation, no need of direct lookup? Commented Feb 14, 2018 at 10:22
  • 1
    @DeepakMishra: there is no such thing like "generally better" in software development. Better here could mean faster, better to read, less code to type, easier to extend for upcoming requirements. But in general, stop overthinking this, implement one which solves your problem at hand correctly and is most simple in your eyes, check if it fast enough for your purpose, and invest only more thoughts in it when you observe drawbacks. Commented Feb 14, 2018 at 12:18
6

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.

Improve this answer
0
2

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.

Improve this answer
0

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.

Improve this answer
-3

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.

Improve this answer
1
  • 8
    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. Commented Dec 12, 2013 at 21:30

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.