Dictionary and HashSet

In short: A map (dictionary) keeps key and value pairs with unique keys and finds a value by its key fast, and a set keeps unique values.

Problem

Who is this user?

The users of the site are in a list. At every login you look up the email by the username:

static string FindEmail(List<User> users, string username)
{
    foreach (User u in users)
    {
        if (u.Username == username)
        {
            return u.Email;
        }
    }
    return null;
}

With three users this is instant. With 2,000,000, every login compares up to 2,000,000 names, and there are thousands of logins a minute. You do not read a phone book from the first page. You go straight to the letter.

The idea

Dictionary: key → value

You want to ask "what is the email of georgiev?" and get the answer right away. The collection for this is called a dictionary (map). It holds pairs: a key and a value. In C# the dictionary is Dictionary:

Dictionary<string, string> emails = new Dictionary<string, string>();
emails["ivanov"] = "ivanov@example.com";
emails["mpetrova"] = "mpetrova@example.com";
emails["georgiev"] = "georgiev@example.com";

Console.WriteLine(emails["georgiev"]);
Console.WriteLine(emails.ContainsKey("nobody"));
Console.WriteLine("Users: " + emails.Count);

Output

georgiev@example.com
False
Users: 3

• There are two type parameters: one for the key and one for the value. Dictionary<string, string> is "from text to text".
• emails[key] = value puts in a pair, and emails[key] returns the value.
• ContainsKey(key) asks whether the key is in it, and Count is the number of pairs.
• Dictionary is in System.Collections.Generic, like List. You do not need a using: it is included in every new program.

emails[key] for a key that is not there does not give null. It throws KeyNotFoundException. When you do not know whether the key is there, ask with TryGetValue: it returns whether it found the key, and gives the value through out. You can also write a dictionary all at once, with [key] = value pairs:

Dictionary<string, string> emails = new Dictionary<string, string>
{
    ["ivanov"] = "ivanov@example.com",
    ["mpetrova"] = "mpetrova@example.com",
};
if (emails.TryGetValue("ivanov", out string email))
{
    Console.WriteLine(email);
}
try
{
    Console.WriteLine(emails["nobody"]);
}
catch (KeyNotFoundException e)
{
    Console.WriteLine("KeyNotFoundException: " + e.Message);
}

Output

ivanov@example.com
KeyNotFoundException: The given key 'nobody' was not present in the dictionary.

emails[key] does not loop over all the pairs. It finds the place of the key almost at once, no matter how many there are. How it does that is the next lesson.

The idea

The warehouse: changes and checks

The stock in a warehouse: item → count.

Dictionary<string, int> stock = new Dictionary<string, int>();
stock["laptop"] = 4;
stock["mouse"] = 25;
stock["laptop"] = 3;

Console.WriteLine(stock["laptop"]);
Console.WriteLine(stock.ContainsKey("monitor"));
Console.WriteLine(stock.GetValueOrDefault("monitor", 0));
stock.Remove("mouse");
Console.WriteLine(stock.Count);

Output

3
False
0
1

• Keys are unique. The second stock["laptop"] = 3 does not add a new row. It replaces 4 with 3.
• ContainsKey asks whether the key is in the dictionary.
• GetValueOrDefault(key, 0) returns the value, or 0 if the key is not there. This protects you from KeyNotFoundException.
• Remove(key) removes the pair.

More precisely, if you are curious

• Values can repeat: the laptop and the mouse can both be 3. Keys cannot.
• There is also ContainsValue. But it loops over all the values, because a dictionary is fast only by key.

• You can also put in a pair with Add(key, value). The difference is with a key that is already there: [key] = replaces the value, but Add throws ArgumentException and leaves the old one alone:

Dictionary<string, int> stock = new Dictionary<string, int>();
stock.Add("laptop", 4);
try
{
    stock.Add("laptop", 3);
}
catch (ArgumentException e)
{
    Console.WriteLine(e.Message);
}
Console.WriteLine(stock["laptop"]);

Output

An item with the same key has already been added. Key: laptop
4

Try it

How many are on the menu?

What will the program print?

Dictionary<string, int> menu = new Dictionary<string, int>();
menu["coffee"] = 2;
menu["tea"] = 2;
menu["coffee"] = 3;
Console.WriteLine(menu.Count + " " + menu["coffee"]);

Answer

2 2

3 2

2 3

3 3

Check

The idea

Looping and order

The delivery price by city. foreach over the dictionary gives the pairs: each one is a KeyValuePair<string, double>, with Key and Value:

Dictionary<string, double> delivery = new Dictionary<string, double>();
delivery["Sofia"] = 4.5;
delivery["Plovdiv"] = 5.2;
delivery["Varna"] = 6.0;
delivery["Burgas"] = 6.0;
delivery["Ruse"] = 5.8;

foreach (KeyValuePair<string, double> e in delivery)
{
    Console.WriteLine($"{e.Key}: €{e.Value:F2}");
}

Output

Sofia: €4.50
Plovdiv: €5.20
Varna: €6.00
Burgas: €6.00
Ruse: €5.80

The cities came out in the order they were added. But Dictionary promises no order. While you only add, it usually keeps the order of adding. After Remove, though, the new key takes the place of the removed one. With the same five cities:

delivery.Remove("Plovdiv");
delivery["Pleven"] = 5.0;
Console.WriteLine(string.Join(", ", delivery.Keys));

Output

Sofia, Pleven, Varna, Burgas, Ruse

Pleven was added last, but it came out second. Do not write code that relies on the order of a Dictionary. When the order matters, change only the class:

• OrderedDictionary keeps the order of adding, and promises it. With the same cities, Remove and adding Pleven, Pleven goes to the end:

Output

Sofia, Varna, Burgas, Ruse, Pleven

• SortedDictionary sorts the keys:

SortedDictionary<string, double> delivery = new SortedDictionary<string, double>();
delivery["Sofia"] = 4.5;
delivery["Plovdiv"] = 5.2;
delivery["Varna"] = 6.0;
delivery["Burgas"] = 6.0;
delivery["Ruse"] = 5.8;

foreach (KeyValuePair<string, double> e in delivery)
{
    Console.WriteLine($"{e.Key}: €{e.Value:F2}");
}

Output

Burgas: €6.00
Plovdiv: €5.20
Ruse: €5.80
Sofia: €4.50
Varna: €6.00

{e.Value:F2} prints the price with two digits after the decimal point: otherwise 6.0 comes out as 6.

More precisely, if you are curious

• If you need only the keys, loop over Keys. If you need only the values, loop over Values:

foreach (string city in delivery.Keys)
{
    Console.Write(city + " ");
}
Console.WriteLine();

double sum = 0;
foreach (double price in delivery.Values)
{
    sum += price;
}
Console.WriteLine($"Average: €{sum / delivery.Count:F2}");

Output

Sofia Plovdiv Varna Burgas Ruse
Average: €5.50

• SortedDictionary is slower than Dictionary, because it keeps the keys sorted. Use it when you need the order.
• OrderedDictionary with type parameters is new: it has been there since .NET 9.

The idea

Counting

How many times was each item ordered? The key is the item, and the value is the count. At each order you take the old count (or 0) and add 1:

string orders = "coffee tea coffee cocoa coffee tea";
SortedDictionary<string, int> counts = new SortedDictionary<string, int>();
foreach (string item in orders.Split(' '))
{
    counts[item] = counts.GetValueOrDefault(item, 0) + 1;
}
Console.WriteLine(string.Join(", ", counts));

Output

[cocoa, 1], [coffee, 3], [tea, 2]

This is the most common use of a dictionary: counting words, votes, errors by type, sales by city. Here it is a SortedDictionary, so the items come out sorted. string.Join(", ", counts) prints each pair as [key, value].

string orders = "coffee tea coffee cocoa coffee tea";
SortedDictionary<string, int> counts = new SortedDictionary<string, int>();
foreach (string item in orders.Split(' '))
{
    counts[item] = counts.GetValueOrDefault(item, 0) + 1;
}
Console.WriteLine(string.Join(", ", counts));

Step by step, in words

1. 6 orders and an empty SortedDictionary.
2. "coffee" is not there: GetValueOrDefault gives 0, and writing to counts[item] adds the key with 1.
3. "tea" is not there: GetValueOrDefault gives 0, and writing to counts[item] adds the key with 1.
4. "coffee" is already there: GetValueOrDefault gives 1, and writing to counts[item] replaces the value with 2.
5. "cocoa" is not there: GetValueOrDefault gives 0, and writing to counts[item] adds the key with 1. SortedDictionary puts it before "coffee": the keys are sorted.
6. "coffee" is already there: GetValueOrDefault gives 2, and writing to counts[item] replaces the value with 3.
7. "tea" is already there: GetValueOrDefault gives 1, and writing to counts[item] replaces the value with 2.
8. Each item is a key once, and the value is how many times it was ordered.

More precisely, if you are curious

• split(" ") from the lesson on text splits the line into words.
• In the "Modern C#" module you will see LINQ. It has ready-made counting, CountBy, which gives the pairs in the order the items were first seen:

string orders = "coffee tea coffee cocoa coffee tea";
Console.WriteLine(string.Join(", ", orders.Split(' ').CountBy(item => item)));

Output

[coffee, 3], [tea, 2], [cocoa, 1]

Try it

Find the bug

The program should count the orders. Instead, it stops at the very first one:

Error

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

Which line has the bug?

Pick the line with the bug.

1string[] orders = { "coffee", "tea", "coffee" };2SortedDictionary<string, int> counts = new SortedDictionary<string, int>();3foreach (string item in orders)4{5 counts[item] = counts[item] + 1;6}7Console.WriteLine(string.Join(", ", counts));

Check

The idea

HashSet: each one once

How many different people logged in to the site today? If someone logs in five times, they should be counted once. A collection that holds each value only once is called a set:

string[] visits = { "ana@example.com", "boris@example.com", "ana@example.com", "vera@example.com", "boris@example.com" };
HashSet<string> visitors = new HashSet<string>();
foreach (string email in visits)
{
    visitors.Add(email);
}
Console.WriteLine("Visits: " + visits.Length);
Console.WriteLine("Unique visitors: " + visitors.Count);
Console.WriteLine(visitors.Contains("vera@example.com"));

Output

Visits: 5
Unique visitors: 3
True

• Add on a value that is already in it does nothing and returns False. If it is new, it returns True:

HashSet<string> seen = new HashSet<string>();
Console.WriteLine(seen.Add("F-101"));
Console.WriteLine(seen.Add("F-101"));

Output

True
False

• Contains is as fast as ContainsKey on a dictionary. Inside, a HashSet is like a Dictionary in which you keep only the keys.
• There are no indexes. A set answers only the question "is it in here?".

More precisely, if you are curious

• The order of a HashSet is not promised, just like with Dictionary. SortedSet sorts. You can also write a set all at once, in {} with values:

SortedSet<string> tags = new SortedSet<string> { "java", "sql", "git", "java" };
Console.WriteLine(string.Join(", ", tags));

HashSet<string> backend = new HashSet<string> { "java", "sql", "docker" };
SortedSet<string> common = new SortedSet<string>(tags);
common.IntersectWith(backend);
Console.WriteLine(string.Join(", ", common));
tags.UnionWith(backend);
Console.WriteLine(string.Join(", ", tags));

Output

git, java, sql
java, sql
docker, git, java, sql

• IntersectWith keeps only the elements two sets have in common, and UnionWith joins them. Both change the set you call them on, so the common ones are in a copy: new SortedSet<string>(tags). You will need them in the exercise.

Try it

A duplicate invoice

The accountant wants to see the invoice numbers that were entered twice. Which method checks and adds at the same time?

string[] invoices = { "F-101", "F-102", "F-101", "F-103" };
HashSet<string> seen = new HashSet<string>();
foreach (string number in invoices)
{
    if (!seen.(number))
    {
        Console.WriteLine("Duplicate invoice: " + number);
    }
}

Check

Exercise

Dictionaries at work

Solve the tasks in your editor.

1. A user table. A UserTable class with the methods Add(string username, string email), Get(string username) and Size(). Inside, it is a Dictionary. For a user who is not there, Get returns null: GetValueOrDefault without a second argument gives exactly that. Add ivanov, mpetrova and georgiev with emails in the form ivanov@example.com, and look up mpetrova and nobody. In the next lesson you will also build your own hash table, without Dictionary.

Output

mpetrova: mpetrova@example.com
nobody: no such user
Users: 3

2. Word frequency. Read a line of text, make it lowercase and count each word. Print the words in alphabetical order.

Input

Coffee with milk and coffee without sugar and coffee

Output

and: 2
coffee: 3
milk: 1
sugar: 1
with: 1
without: 1

3. Documents by keyword. A DocumentIndex class with the methods AddDocument(int id, params string[] keywords) and Search(string keyword), which returns a list of the numbers of the documents with that word. Inside, it is a Dictionary<string, List<int>>: for each word, a list of documents. Add document 1 with "OOP" and "Java", document 2 with "SQL" and "databases", and document 3 with "Java" and "collections". Search for "Java", "SQL" and "Python", and print the numbers in [], separated by commas.

Output

Java: [1, 3]
SQL: [2]
Python: []

4. A contact network. A Contact class with a name and an email, and a ContactNetwork class with the methods AddContact(string name, string email), AddConnection(string a, string b) (the connection goes both ways), FriendsOf(string name), Common(string a, string b) (mutual friends) and EmailOf(string name). Keep the contacts in a Dictionary<string, Contact> and the connections in a Dictionary<string, SortedSet<string>>, so the names come out sorted. Connect Ivan with Maria and Ivan with Peter.

Output

Ivan: [Maria, Peter]
Maria: [Ivan]
Mutual friends of Maria and Peter: [Ivan]
Peter's email: peter@example.com

More tasks

• A unique ID. A method GenerateUserId(string email) gives each new email a number, U001, U002 and so on, and for an email it has already seen it returns the same number. Capital and lowercase letters in the email are treated the same. There is a version with a hash function in the next lesson.
• A book catalog. The key is the ISBN, for example 978-954-28-0001-2, and the value is the title. Add books, look one up and print all of them, sorted by ISBN.
• A trip planner. For each destination, keep a list of activities: "Paris" → "the Eiffel Tower", "the Louvre". Print the plan in the order the destinations were added. Which dictionary will you choose?
• An online dictionary. Word → definition. Read words until "end" comes. For an unknown word, print "No such word."
• Grades by subject. Read lines like "Math 6", "Physics 5", "Math 4", and print the average grade for each subject, sorted by name.

Test

Check yourself

1. When is a Dictionary a better choice than a list?

When you need repeated values one after anotherWhen you look up by key, for example the email by usernameWhen you need the elements by index

2. menu already has the key "coffee" with the value 2. What does menu["coffee"] = 3 do?

Adds a second "coffee" keyReplaces the value with 3; there is still one keyThrows an exception

3. The key "tea" is not in menu. What does menu["tea"] do?

Returns 0Throws KeyNotFoundExceptionReturns null

4. You loop over a Dictionary. In what order do the keys come out?

Always in the order of addingIn an order Dictionary does not promiseIn alphabetical order

5. What does Add on a HashSet return if the value is already in it?

True, and it adds it a second timeFalse, and the set does not changeIt throws an exception

Check

Start the lesson over

Related lessons

• Builds on: Polymorphism · Interfaces · Exceptions · Lists
• Continues in: Hash codes and hash functions · Nested classes · Lambdas and delegates · LINQ
• Tasks on this topic: Collections