Counting with a dictionary

Picture counting the votes in an election for class representative. On a sheet of paper you write a name and put a tally mark next to it for every vote. A new name gets a new line with one mark, and a familiar one gets one more. It is the same directory: the name is the key, and the number of marks is the value.

Without a dictionary you would have to look through all the votes again for each name. With a dictionary one pass is enough: each vote adds a mark to its name at once.

Counting in one pass

string[] votes = ["Ann", "Bob", "Ann", "Cid", "Ann", "Bob"];
var counts = new Dictionary<string, int>();
foreach (string name in votes)
{
    if (counts.ContainsKey(name))
    {
        counts[name]++;
    }
    else
    {
        counts[name] = 1;
    }
}
Console.WriteLine(counts["Ann"]); // 3
Console.WriteLine(counts["Bob"]); // 2

Let's go through what the program does:

1. counts starts empty: there are no names on the sheet yet.
2. For each vote the loop checks whether that name is already among the keys.
3. If it is, counts[name]++ raises its value by one, that is, puts down another mark.
4. If it is not, counts[name] = 1 starts a new pair with the first vote.
5. After the loop Ann has three votes and Bob two.

This kind of counting is at the heart of many interview problems:

• find the most frequent word;
• check that two strings are made of the same letters;
• find the first character that does not repeat.

A dictionary solves each of them in one or two passes over the data. A solution with two nested loops compares every element with every other: for 10,000 elements that is 100 million comparisons, while one pass is 10,000 steps.

Walking the pairs

A foreach loop over a dictionary yields pairs. Each pair has a key, Key, and a value, Value. The full form of such a loop is foreach (KeyValuePair<string, int> pair in counts), and inside the loop you write pair.Key and pair.Value.

A shorter way unpacks the pair into two variables at once: var (name, count). Let's find the winner in the dictionary counts from the first example:

string winner = "";
int best = 0;
foreach (var (name, count) in counts)
{
    if (count > best)
    {
        winner = name;
        best = count;
    }
}
Console.WriteLine($"{winner} {best}"); // Ann 3

Let's go through the loop:

• foreach (var (name, count) in counts) puts the pair's key into name and its value into count on every iteration;
• if the name has more votes than the leader so far, it becomes the new winner.

Here the sheet and the dictionary part ways. On the sheet the lines stand in the order you wrote them, while a dictionary promises no such order. That does not get in the winner's way: with three votes there is one winner, whatever order the pairs come in. With a tie, though, the winner would be whoever the loop meets first, and the dictionary does not guarantee that order.

One call: GetValueOrDefault

The ContainsKey check can be folded into one call. GetValueOrDefault(name) returns the value for a key, and if the key is missing, the default value, which for int is 0:

string[] votes = ["Ann", "Bob", "Ann"];
var counts = new Dictionary<string, int>();
foreach (string name in votes)
{
    counts[name] = counts.GetValueOrDefault(name) + 1;
}
Console.WriteLine(counts["Ann"]); // 2
Console.WriteLine(counts["Bob"]); // 1

The loop reads the current number of votes, or 0, and writes back a number one higher. A new name gets 1, a familiar one gets one more vote.

Common mistake

A vote was added without checking whether the key is already there:

string[] votes = ["Ann", "Bob"];
var counts = new Dictionary<string, int>();
foreach (string name in votes)
{
    counts[name]++; // ✗
}

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

The program compiles, but on the very first vote it stops with a KeyNotFoundException. counts[name]++ first reads the value for the key, and there is no key Ann yet. A new name has to be started first: with a ContainsKey check or with GetValueOrDefault, as in the examples above.

Key points

• A dictionary counts in one pass: the key is what we count, the value is how many times it came up.
• counts[key]++ works only for a key that is already there; a new key is started with ContainsKey or GetValueOrDefault.
• foreach over a dictionary yields pairs with Key and Value, and var (name, count) unpacks a pair into two variables.
• The order of pairs in a dictionary is not guaranteed, so the result must not depend on it.