Dictionary
A lookup table
A list finds an element by comparing, one after another. A dictionary finds a value by its key in about one step: it hashes the key and looks the hash up in a table of buckets. The cost is one hash per lookup and the memory of the table, and the price is that a key must not change while it is in the dictionary.
var counts = new Dictionary<string, int>();
counts["a"] = 1;
counts["b"] = 2;
counts["a"] = counts["a"] + 1;
Console.WriteLine(counts["a"]);
Console.WriteLine(counts.TryGetValue("z", out int z));
Console.WriteLine(z);
Console.WriteLine(counts.Count);
Console.WriteLine(counts.ContainsKey("b"));
dotnet run
2
False
0
2
True
The indexer both reads and writes: counts["a"] = 1 adds the key, and counts["a"] reads the value. Reading a key that is not there throws KeyNotFoundException, which is why a program that cannot be sure uses TryGetValue.
TryGetValue and the missing key
TryGetValue returns whether the key was there and writes the value into an out parameter when it was. The parameter is always assigned — to the default value of the type when the key is missing — so the compiler accepts it as initialised, and the 0 of the previous program came from that rule, not from the dictionary.
var stock = new Dictionary<string, int> { ["apple"] = 3 };
if (stock.TryGetValue("pear", out int pears))
{
Console.WriteLine($"pears: {pears}");
}
else
{
Console.WriteLine("no pears");
}
stock["pear"] = 0;
stock["pear"] += 4;
Console.WriteLine($"pears now: {stock["pear"]}");
dotnet run
no pears
pears now: 4
The second half is the counting idiom: a key that may be absent is created with 0 and then incremented, and the indexer does both in one line. The collection initialiser { ["apple"] = 3 } is the short form of the same writes.
Iterating a dictionary
foreach over a dictionary yields KeyValuePair<TKey, TValue> values, and the pairs come in an order the documentation does not promise:
var counts = new Dictionary<string, int>
{
["b"] = 2,
["a"] = 1,
};
foreach (var pair in counts)
{
Console.WriteLine($"{pair.Key}={pair.Value}");
}
foreach (var key in counts.Keys.OrderBy(k => k))
{
Console.WriteLine($"sorted: {key}");
}
Console.WriteLine($"pairs: {counts.Count}");
dotnet run
b=2
a=1
sorted: a
sorted: b
pairs: 2
This runtime printed the pairs in insertion order, and a later release or a
different set of keys may print another order: the order is an
implementation detail. A program that shows a table, writes a file or
compares output sorts the keys itself, as the second loop does, or uses a
SortedDictionary from the next lesson.
A dictionary cannot be changed while a foreach walks
it: an Add or a Remove
inside the loop throws InvalidOperationException.
The fix is to collect the keys first and change the dictionary after the
loop, or to iterate over counts.Keys.ToList().
Exercises
- Count the words of a sentence with a dictionary of string to int and print the pairs in sorted key order.
- Read a missing key with the indexer inside a try and print the exception type.
- Remove a key while a foreach walks the dictionary. Read the exception and fix the loop.
- Compare the count of a dictionary with the count of a list of the same keys after a thousand lookups. Which one would you keep for the lookups?
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
How does a dictionary find a value so quickly?
Answer
It hashes the key and looks the hash up in a table of buckets
A hash table turns the key into a bucket index, so a lookup costs about one hash and one comparison.
-
What happens when the indexer reads a key that is not in the dictionary?
Answer
KeyNotFoundException
The indexer throws for a missing key; TryGetValue is the call that returns false instead.
-
What does this program print?
var map = new Dictionary<string, int> { ["a"] = 1 }; Console.WriteLine(map.TryGetValue("b", out int value)); Console.WriteLine(value);Answer
False / 0
TryGetValue returns false and assigns the default of int, which is 0, to the out parameter.
-
What does this program print?
var map = new Dictionary<string, int>(); map["x"] = 1; map["x"] = map["x"] + 1; Console.WriteLine(map["x"]); Console.WriteLine(map.Count);Answer
2 / 1
The indexer replaces the value of an existing key rather than adding a second one, so the count stays 1.
-
Which order does a foreach over a dictionary promise?
Answer
None: the order is an implementation detail
The pairs are produced in an order of the implementation, so a program that needs one sorts the keys or uses SortedDictionary.
-
What happens when a key is added inside a foreach over the dictionary?
Answer
InvalidOperationException, because the collection changed
A dictionary checks its version on every step of the enumeration and refuses a change during it.
-
What does this program print?
var map = new Dictionary<string, int> { ["a"] = 1, ["b"] = 2 }; Console.WriteLine(map.Count); Console.WriteLine(map.ContainsKey("a"));Answer
2 / True
The initialiser added both keys, so the count is 2, and ContainsKey finds a.
-
Why must a key not change while it is in a dictionary?
Answer
Its hash would point at another bucket and the value would be lost
The bucket is chosen from the hash at insertion time, so a changed hash makes the entry unreachable by lookup.
-
What does this program print?
var map = new Dictionary<int, string>(); map[1] = "one"; foreach (var pair in map) { Console.WriteLine($"{pair.Key}:{pair.Value}"); }Answer
1:one
Any type with a hash and equality can be a key, and the pair prints the key and the value.
-
Which call tells you whether a key exists without throwing?
Answer
ContainsKey
ContainsKey returns a bool; Remove also returns one but takes the entry out, and the indexer throws.
The code on this page was built with the .NET SDK 10.0.303 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev