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?
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
But really, any time you have two related lists of integers, this could be an appropriate data structure.
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
Dictionary<int, int> personHeightMap = new Dictionary<int, int>(); personHeightMap.Add(21, 185); personHeightMap.Add(31, 174); int height = personHeightMap.ContainsKey(21) ? personHeightMap : -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.
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
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.
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.
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.
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.
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.
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.