Theory · Lists, dictionaries and sets · lesson 6 of 10

Dictionary

Picture an office phone directory. Next to each name stands an extension number: Ann has 101, Bob has 102. To call Bob, you do not leaf through the directory from the first page, you open it at the letter B right away.

A list cannot do that. To find a number by a name, you would have to keep two lists, of names and of numbers. Then you would look the name up with IndexOf, checking the elements one by one.

For lookups by name .NET has the dictionary: a collection of pairs where a value is found by its key. It is the type Dictionary<TKey, TValue>. In the directory the key is the name and the value is the number:

var phones = new Dictionary<string, int>();
phones["Ann"] = 101;
phones["Bob"] = 102;
Console.WriteLine(phones["Bob"]); // 102
Console.WriteLine(phones.Count);  // 2

Let's go through the program line by line:

Dictionary<string, int> is a dictionary with string keys and int values. This generic type has two type parameters: the key type and the value type.
phones["Ann"] = 101; puts in a pair: the key Ann, the value 101.
phones["Bob"] finds the value by its key, and the program prints 102.
Count is the number of pairs in the dictionary: 2.

Keys in a dictionary do not repeat: one name has one number. Values can repeat, though: two people can share one phone.

Putting a value in

With the indexer

You have seen the indexer on a list: guests[0]. A dictionary's indexer takes a key in the brackets instead of an index: phones["Ann"]. The line phones["Ann"] = 101 puts in a pair if the key is not there yet, and replaces the value if the key is already there.

With `Add`

phones.Add("Ann", 101) only adds a new pair. If the key is already there, the program stops with an ArgumentException.

var phones = new Dictionary<string, int>();
phones.Add("Ann", 101);
phones["Ann"] = 199;
Console.WriteLine(phones["Ann"]); // 199
Console.WriteLine(phones.Count);  // 1

Add put the pair in, and the indexer replaced the value for the same key. There is still one pair, so Count is 1.

Reading a value

The indexer finds a value by its key. If the key is missing, it does not return 0, it stops the program. Here is what the program reports when it reads phones["Cid"] and there is no key Cid in the dictionary:

TEXT

Unhandled exception. System.Collections.Generic.KeyNotFoundException: The given key 'Cid' was not present in the dictionary.

When a key may be missing, it is checked first. A dictionary has two methods for that:

ContainsKey(key) tells whether the key is there: true or false;
TryGetValue(key, out value) looks the key up once and, if it succeeds, puts the value into the out variable, like int.TryParse.

var phones = new Dictionary<string, int>();
phones["Ann"] = 101;
Console.WriteLine(phones.ContainsKey("Ann")); // True
Console.WriteLine(phones.ContainsKey("ann")); // False
if (phones.TryGetValue("Ann", out int number))
{
    Console.WriteLine(number); // 101
}
Console.WriteLine(phones.TryGetValue("Cid", out int none)); // False
Console.WriteLine(none);                 // 0
Console.WriteLine(phones.Remove("Ann")); // True
Console.WriteLine(phones.Count);         // 0

Step by step:

ContainsKey("Ann") finds the key and returns true.
ContainsKey("ann") returns false: string keys are compared case-sensitively, so Ann and ann are different keys.
TryGetValue("Ann", …) finds the key, returns true and puts 101 into number.
There is no key Cid: TryGetValue returns false and puts the default value into none, which for int is 0.
Remove removes the pair and returns true, because the key was there.

How a dictionary finds a key

Why does a dictionary not leaf through the pairs one by one? From the key it computes a number, a hash, and with that number it goes straight to a small group of pairs where the key may lie. That is how you open a directory at the right letter at once.

That is why a lookup by key takes almost the same time in a dictionary of ten pairs and in one of a million. IndexOf in a list, by contrast, checks the elements one by one, and the longer the list, the longer the search. Interviewers often ask why a lookup in a Dictionary is faster than in a List: the answer is the hash.

Here the directory and the dictionary part ways. In a directory the names stand in alphabetical order, while a dictionary promises no order of its pairs at all. If you walk it in a loop, the pairs come in an order you cannot rely on.

Common mistake

Someone tried to change a number with a second Add:

var phones = new Dictionary<string, int>();
phones.Add("Ann", 101);
phones.Add("Ann", 199); // ✗