Lesson 32 of 62Intermediate16 min

Dictionary

By the end of this lesson

Look values up by key in constant time and handle missing keys correctly.

You have a list of forty thousand products and a SKU. Finding the matching product in a List means comparing SKUs one at a time until you hit it — on average twenty thousand comparisons. Do that once per line on an order and the page takes seconds for no good reason.

A Dictionary stores pairs: a key you look things up by, and a value you get back. Given a key it goes almost straight to the value, and it takes roughly the same time whether the dictionary holds forty entries or forty thousand.

Why this matters

How it gets there without searching

Every key is turned into a number by a method called GetHashCode. That number is then reduced to a position in an internal array of buckets. To look a key up, the dictionary calculates the number again, goes to that bucket, and checks only the keys sitting there.

Because the calculation does not depend on how many entries exist, the work does not grow as the dictionary grows. That is why lookup is described as constant time.

It is described as roughly constant because two different keys can produce the same bucket. That is a collision, and the dictionary handles it by keeping several entries in one bucket and comparing them. With a reasonable hash calculation collisions are uncommon, so the average stays flat. With a poor one — every key returning the same number — a dictionary degrades into a slow list.

Products indexed by SKU

Dictionary<string, Product> productsBySku = new Dictionary<string, Product>();

productsBySku["DL-1001"] = new Product("Desk lamp", 1_450m, 12);
productsBySku["NB-2002"] = new Product("Notebook", 120m, 40);

productsBySku.Add("PN-3003", new Product("Pen", 25m, 200));

Console.WriteLine(productsBySku.Count);                 // 3
Console.WriteLine(productsBySku["NB-2002"].Name);       // Notebook
Console.WriteLine(productsBySku.ContainsKey("XX-9999")); // False

productsBySku.Remove("PN-3003");

foreach (KeyValuePair<string, Product> entry in productsBySku)
{
    Console.WriteLine($"{entry.Key} -> {entry.Value.Name}");
}

foreach (string sku in productsBySku.Keys)
{
    Console.WriteLine(sku);
}

Dictionary<string, Product> means the keys are strings and the values are Products. Both types are fixed when you declare it.
The indexer with = assigns. It adds the entry if the key is new and replaces the value if the key already exists, without complaint either way.
Add also inserts, but throws ArgumentException if the key is already there. Use Add when a duplicate key means a bug, and the indexer when replacing is intended.
Iterating gives you KeyValuePair entries, each with a Key and a Value. Keys and Values give you either side on its own.
Enumeration order is not guaranteed and should not be relied on. It is not insertion order and it is not sorted.

Reading a key that might not be there

// Throws KeyNotFoundException if the SKU is not present.
Product product = productsBySku["XX-9999"];

// Two lookups: one to check, one to fetch.
if (productsBySku.ContainsKey("NB-2002"))
{
    Product found = productsBySku["NB-2002"];
    Console.WriteLine(found.Name);
}

// One lookup, and the result tells you whether it worked.
if (productsBySku.TryGetValue("NB-2002", out Product? found2))
{
    Console.WriteLine(found2.Name);
}
else
{
    Console.WriteLine("Unknown SKU.");
}

// When a missing key is not a problem, a default is enough.
Product? maybe = productsBySku.GetValueOrDefault("XX-9999");   // null

TryGetValue returns true or false, and puts the value into the variable declared with out. It hashes the key once and does everything in that single pass.
ContainsKey followed by the indexer hashes the key twice and compares twice. On a hot path that is double the work for no benefit.
The gap is worse than performance in code shared between threads: another thread can remove the entry between the check and the fetch, so the indexer throws on a key you had confirmed existed. TryGetValue has no such window.
out Product? found2 declares the variable in the same line as the call. Outside the if it may be null, which is why the type has a question mark.
Reach for TryGetValue by default. Use ContainsKey when you only want to know whether a key is present and do not need the value.

The members worth knowing, and what each is for:

dictionary[key] — read: Fetches the value, and throws KeyNotFoundException if the key is absent. Use it when a missing key means the program is already wrong.
dictionary[key] = value — write: Adds or replaces, silently. Convenient, and worth remembering that it will overwrite.
Add(key, value): Adds, and throws if the key exists. The right choice when a duplicate signals a bug you want to hear about.
TryAdd(key, value): Adds if absent, returns false if present, throws nothing. Useful for "first one wins" behaviour.
TryGetValue(key, out value): One lookup, tells you whether it found anything. The default way to read a key that may be missing.
GetValueOrDefault(key): Returns the value or the type's default — null for a class, zero for an int. Compact, and note that it cannot distinguish "missing" from "present but zero".

Common mistake

Common mistakes

Expecting the indexer to behave symmetrically. Reading a missing key throws; writing a missing key adds it. That asymmetry is deliberate — silently returning a default on read would turn a typo in a SKU into a wrong number instead of a clear error, and you could not tell a missing entry apart from one whose value happens to be null or zero. It still surprises people, so it is worth saying out loud.

Using Add in a loop over data that may contain duplicates, and being surprised by ArgumentException in production on a data set you did not control. Decide whether duplicates mean "replace", "ignore" or "fail", and use the indexer, TryAdd or Add accordingly.

Using a mutable object as a key and then changing it. The hash was calculated from its old state, so the entry is in a bucket that no longer matches, and you can no longer find it — even though it is still in the dictionary. Keys should be values that do not change: a string, an int, a Guid, a record.

Writing a custom class as a key without overriding Equals and GetHashCode. Two Product objects with identical contents are different keys by default, because the comparison falls back to reference identity.

Relying on enumeration order, which is not defined. If you need order, sort when you read, or use SortedDictionary and accept that it is slower.

When to use this

When a Dictionary is the wrong tool

The collection is small. Scanning a list of twenty items is fast, and a List is easier to read and to print while debugging. The crossover is small enough that clarity should decide.

You need items in order, or by position. A dictionary offers neither. Use a List, or SortedDictionary if you need sorted keys and can accept the cost.

You need to look items up by more than one thing — by SKU and by supplier and by name. One dictionary gives you one key. Two dictionaries pointing at the same objects is a real option, and keeping them in step becomes your problem.

There is no meaningful key. Forcing one, such as using the position as a key, gives you a List with extra steps.

You only need to know whether something is present, with no value attached. That is a HashSet, which is the subject of the next lesson.

Summary

A Dictionary stores key and value pairs and finds a value by key in roughly constant time
It works by hashing the key to a bucket, so lookup cost does not grow with the number of entries
Reading a missing key with the indexer throws; writing a missing key adds it
TryGetValue does one lookup and reports success, which is the default way to read a possibly-missing key
Keys must not change after insertion, and custom key types need Equals and GetHashCode

Practice

Attempt each one before opening the solution. Getting it wrong first is how the idea sticks.

Try it yourself

You have a List of order lines, each with a SKU and a quantity, and the same SKU can appear more than once. Build a Dictionary of total quantity per SKU.

Write it with TryGetValue rather than ContainsKey, and work out what the value should be the first time a SKU is seen.

Show solution

The first time a SKU appears, TryGetValue returns false and leaves the out variable at zero — which happens to be exactly the right starting total, so the same line of code handles both the first occurrence and every later one.

That is the usual shape of a counting or grouping loop, and it is worth recognising because it appears constantly. GetValueOrDefault would read equally well here; the reason to prefer TryGetValue in general is that it distinguishes a missing key from a stored zero, which matters as soon as zero is a meaningful value.

List<OrderLine> lines = new List<OrderLine>
{
    new OrderLine("DL-1001", 2),
    new OrderLine("NB-2002", 5),
    new OrderLine("DL-1001", 3),
    new OrderLine("PN-3003", 10)
};

Dictionary<string, int> quantityBySku = new Dictionary<string, int>();

foreach (OrderLine line in lines)
{
    quantityBySku.TryGetValue(line.Sku, out int runningTotal);
    quantityBySku[line.Sku] = runningTotal + line.Quantity;
}

foreach (KeyValuePair<string, int> entry in quantityBySku)
{
    Console.WriteLine($"{entry.Key}: {entry.Value}");
}
// DL-1001: 5,  NB-2002: 5,  PN-3003: 10

Knowledge check

Nothing is recorded and there is no score. The explanation appears either way.

Why is TryGetValue usually preferred over ContainsKey followed by reading the indexer?

ContainsKey does not work with string keysTryGetValue hashes and finds the key once instead of twice, and leaves no gap in which the entry could be removedTryGetValue adds the key if it is missingContainsKey scans the whole dictionary, so it is proportional to the number of entries

Saved in this browser only.