C# Dictionary and HashSet operations

Before you start

C# collections and LINQ.

Count words with a dictionary and combine sets with union, intersection, and difference.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

Dictionary<TKey, TValue> stores key–value pairs with O(1) average lookup. TryGetValue reads a value and tells whether the key exists, in one lookup, so counting items is a loop of TryGetValue followed by an assignment. The indexer throws KeyNotFoundException for a missing key. Enumeration order is not something to rely on, so sort before printing.

HashSet<T> stores unique values and answers Contains in O(1) on average. UnionWith, IntersectWith, and ExceptWith change a set in place to hold the union, intersection, and difference with another collection. Sets are the natural tool for removing duplicates and for membership tests.

Code example

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

class Program {
  static void Main() {
    string text = "the quick brown fox jumps over the lazy dog the end";
    var counts = new Dictionary<string, int>();
    foreach (string word in text.Split(' ')) {
      counts[word] = counts.TryGetValue(word, out int seen) ? seen + 1 : 1;
    }
    foreach (var pair in counts.OrderByDescending(p => p.Value).ThenBy(p => p.Key).Take(3)) {
      Console.WriteLine(pair.Key + ": " + pair.Value);
    }
    Console.WriteLine("distinct words: " + counts.Count);

    var a = new HashSet<int> { 1, 2, 3, 4 };
    var b = new HashSet<int> { 3, 4, 5 };
    var inter = new HashSet<int>(a);
    inter.IntersectWith(b);
    var union = new HashSet<int>(a);
    union.UnionWith(b);
    var diff = new HashSet<int>(a);
    diff.ExceptWith(b);
    Console.WriteLine("intersection " + string.Join(" ", inter.OrderBy(x => x)));
    Console.WriteLine("union " + string.Join(" ", union.OrderBy(x => x)));
    Console.WriteLine("difference " + string.Join(" ", diff.OrderBy(x => x)));
  }
}

Output

the: 3
brown: 1
dog: 1
distinct words: 9
intersection 3 4
union 1 2 3 4 5
difference 1 2

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1using System;

2using System.Collections.Generic;

3using System.Linq;

5class Program {

6 static void Main() {

7 string text = "the quick brown fox jumps over the lazy dog the end";

8 var counts = new Dictionary<string, int>();

9 foreach (string word in text.Split(' ')) {

10 counts[word] = counts.TryGetValue(word, out int seen) ? seen + 1 : 1;

11 }

12 foreach (var pair in counts.OrderByDescending(p => p.Value).ThenBy(p => p.Key).Take(3)) {

13 Console.WriteLine(pair.Key + ": " + pair.Value);

14 }

15 Console.WriteLine("distinct words: " + counts.Count);

17 var a = new HashSet<int> { 1, 2, 3, 4 };

18 var b = new HashSet<int> { 3, 4, 5 };

19 var inter = new HashSet<int>(a);

20 inter.IntersectWith(b);

21 var union = new HashSet<int>(a);

22 union.UnionWith(b);

23 var diff = new HashSet<int>(a);

24 diff.ExceptWith(b);

25 Console.WriteLine("intersection " + string.Join(" ", inter.OrderBy(x => x)));

26 Console.WriteLine("union " + string.Join(" ", union.OrderBy(x => x)));

27 Console.WriteLine("difference " + string.Join(" ", diff.OrderBy(x => x)));

28 }

29}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
One lookup reads the old count if there is one; the assignment stores the new count.	`—`	—
Sort by count, highest first, then by word, and take three entries.	`—`	—
the appears three times; the ties at 1 are broken alphabetically.	`—`	the: 3 brown: 1 dog: 1
Nine different words in the 11-word sentence.	`—`	the: 3 brown: 1 dog: 1 distinct words: 9
Keep only the elements found in both sets.	`—`	the: 3 brown: 1 dog: 1 distinct words: 9
Remove the elements that appear in b.	`—`	the: 3 brown: 1 dog: 1 distinct words: 9
3 and 4 are in both sets.	`—`	the: 3 brown: 1 dog: 1 distinct words: 9 intersection 3 4
Every element from either set, once.	`—`	the: 3 brown: 1 dog: 1 distinct words: 9 intersection 3 4 union 1 2 3 4 5
In a but not in b.	`—`	the: 3 brown: 1 dog: 1 distinct words: 9 intersection 3 4 union 1 2 3 4 5 difference 1 2

Behind the scenes

How C# processes this code

C# compiles to code for the .NET runtime, which invokes the program entry point.

Cost and common mistakes

Lookup and insert O(1) average; the set operations are O(n + m).

The set operations modify the set they are called on. Copy the set first, as the example does, if you need the original.
Keys need correct GetHashCode and Equals. Mutating a key after it is added breaks lookups.
Enumeration order of a Dictionary or HashSet is unspecified. Sort when you need a stable output.

Try it yourself

How would you test whether a is a subset of b?

Reveal answer and reasoning

Call a.IsSubsetOf(b), which returns true when every element of a is also in b.