Dictionaries: looking things up by key

A lookup, not a row

A list is read by position, which is no use when the thing you want is called tea. A Dictionary<TKey, TValue> holds pairs and reads them by key: basket["tea"] answers straight away, however many pairs are in it. The angle brackets name the two types, as in Dictionary<string, int> — keys are text, values are whole numbers.

The reason it is fast is worth knowing and not worth worrying about: the key is turned into a number that points near the value, so the dictionary goes almost straight there instead of looking through everything. That is also why keys must be values that do not change, and why a dictionary never has two entries with the same key.

Adding, replacing and reading

Square brackets write as well as read. basket["tea"] = 2; adds the pair if the key is new, and replaces the value if it is not — a tidy way to count, as in basket[name] = basket[name] + 1. Writing a key that is there does not disturb the others.

Reading a key that is not there is the one sharp edge: basket["jam"] on a dictionary without jam throws an exception and stops the program where it stands. ContainsKey("jam") asks first and answers true or false, so a read is usually wrapped in that question.

Remove takes a key, deletes the pair if it is there, and answers true or false so the caller knows which happened. Clear empties the dictionary in one call. Count says how many pairs there are, which is not the same as the sum of the values: three bags of tea under one key are one pair, not three. Keeping those two questions apart is most of what a stock report needs.

Walking the pairs, and why the order is not promised

Each entry arrives as a KeyValuePair, with .Key and .Value on it, and basket.Keys or basket.Values hands you just one half. Walking a dictionary is the right way to print a summary — as long as the output does not depend on the order, because a dictionary does not promise one.

Sort the keys when the output has to look the same on every run: basket.Keys.OrderBy(k => k). The order of a dictionary follows how its keys are stored, not how they were added, so a report that needs a stable shape sorts explicitly. That is a habit worth forming early, and it is what the example below does.

Pairs, checks and a stable order

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        var basket = new Dictionary<string, int>();
        basket["tea"] = 2;            // adds it, or replaces
        basket["cake"] = 1;

        Console.WriteLine(basket["tea"]);           // 2
        Console.WriteLine(basket.Count);            // 2
        Console.WriteLine(basket.ContainsKey("jam")); // False

        // A missing key is not a null; reading it throws.
        // Ask first, then read.
        if (basket.ContainsKey("jam"))
        {
            Console.WriteLine(basket["jam"]);
        }
        else
        {
            Console.WriteLine("no jam today");
        }

        // Walk the pairs. The order is not promised, so sort
        // the keys when the output has to look the same.
        foreach (var key in basket.Keys.OrderBy(k => k))
        {
            Console.WriteLine(key + " x" + basket[key]);
        }
    }
}

How a key finds its value

A dictionary stores its entries in buckets chosen by the hash code of the key. A hash is a number computed from the contents of the key; equal keys produce equal hashes, and the dictionary uses that number to jump close to the right bucket instead of scanning every entry. That is why a lookup costs about the same whether there are ten entries or ten thousand.

The key has to stay stable while it is in the dictionary. A string is a good key because its text does not change. If you used an object whose hash depended on a property and then changed that property, the entry would still be there, but the dictionary would look in the wrong bucket and fail to find it.

Ask once, not twice

ContainsKey followed by an indexer read looks up the key twice. TryGetValue does both in one call: it returns true or false, and puts the value into an out parameter when it finds one. The pattern is slightly longer to read and does half the work.

Add and the indexer differ in one important way. Add refuses a key that already exists and throws; the indexer replaces the old value without complaint. Use Add when a duplicate means a bug, and the indexer when the later value should win.

Try these next

• Count the words in a short sentence with a dictionary and print the counts in alphabetical order.
• Read a key with TryGetValue, then with ContainsKey plus the indexer, and note which one looks the key up once.
• Add the same key twice with Add and read the exception, then do it with the indexer and see the value replaced.