C# Dictionary Examples

Perform fast lookups with string keys. Add elements to Dictionary from System.Collections.Generic.

Dictionary. The gopher digs tunnels. When hungry, it uses them to eat plants. A dictionary could map the gopher's tunnels to its food sources.

Dictionary keys. The Dictionary is a fast way to remember things. A key (like a string) maps to a value (like an int). Add() inserts keys and values.ToDictionary

An example. Here we add 4 keys (each with an int value) to 2 separate Dictionary instances. Every Dictionary has pairs of keys and values.

String, int: Dictionary is used with different elements. We specify its key type and its value type (string, int).

Version 1: We use Add() to set 4 keys to 4 values in a Dictionary. Then we access the Count property to see how many items we added.

Version 2: This creates a Dictionary with the same internal values as the first version, but its syntax is more graceful.

C# program that uses Dictionary, Add, Initializer and Count using System; using System.Collections.Generic; class Program { static void Main() { // Version 1: create a Dictionary, then add 4 pairs to it. var dictionary = new Dictionary<string, int>(); dictionary.Add("cat", 2); dictionary.Add("dog", 1); dictionary.Add("llama", 0); dictionary.Add("iguana", -1); // The dictionary has 4 pairs. Console.WriteLine("DICTIONARY 1: " + dictionary.Count); // Version 2: create a Dictionary with an initializer. var dictionary2 = new Dictionary<string, int>() { {"cat", 2}, {"dog", 1}, {"llama", 0}, {"iguana", -1} }; // This dictionary has 4 pairs too. Console.WriteLine("DICTIONARY 2: " + dictionary2.Count); } } Output DICTIONARY 1: 4 DICTIONARY 2: 4

ContainsKey. This commonly-called method sees if a given string is present in a Dictionary. We use string keys here—we look at more types of Dictionaries further on.ContainsKey

Returns: ContainsKey returns true if the key is found. Otherwise, it returns false. No exception is thrown if the key is missing.

C# program that uses ContainsKey using System; using System.Collections.Generic; class Program { static void Main() { Dictionary<string, int> dictionary = new Dictionary<string, int>(); dictionary.Add("apple", 1); dictionary.Add("windows", 5); // See whether Dictionary contains this string. if (dictionary.ContainsKey("apple")) { int value = dictionary["apple"]; Console.WriteLine(value); } // See whether it contains this string. if (!dictionary.ContainsKey("acorn")) { Console.WriteLine(false); } } } Output 1 False

TryGetValue. This is often the most efficient lookup method. As the name TryGetValue implies, it tests for the key. It then returns the value if it finds the key.TryGetValue

Important: Many programs can be optimized with TryGetValue. We can use the value we access without getting it a second time.

C# program that uses TryGetValue using System; using System.Collections.Generic; class Program { static void Main() { Dictionary<string, string> values = new Dictionary<string, string>(); values.Add("cat", "feline"); values.Add("dog", "canine"); // Use TryGetValue. string test; if (values.TryGetValue("cat", out test)) // Returns true. { Console.WriteLine(test); // This is the value at cat. } if (values.TryGetValue("bird", out test)) // Returns false. { Console.WriteLine(false); // Not reached. } } } Output feline

TryGetValue, syntax 2. We can declare the "out" variable directly in the method call. This can make the code easier to read—the statements are combined, but have the same effects.

Description: This variable (description) cannot be accessed elsewhere in the program other than in the if-statement.

C# program that uses inline out, TryGetValue using System.Collections.Generic; class Program { static void Main() { var values = new Dictionary<string, string>(); values.Add("A", "uppercase letter A"); values.Add("c", "lowercase letter C"); // Use inline "out string" with TryGetValue. if (values.TryGetValue("c", out string description)) { System.Console.WriteLine(description); } } } Output lowercase letter C

Loop. Here we loop over KeyValuePairs in a Dictionary. With collections like Dictionary, we must always know the value types. With each KeyValuePair, there is a Key member and Value member.Foreach

String, int: The code creates a Dictionary with string keys and int values. The Dictionary stores animal counts.

Tip: In the foreach-loop, each KeyValuePair struct has 2 members, a string Key and an int Value.

KeyValuePair

Var: This keyword reduces the amount of typing required. And it may make code easier to read for humans (like us).

Var

C# program that uses foreach on Dictionary using System; using System.Collections.Generic; class Program { static void Main() { Dictionary<string, int> data = new Dictionary<string, int>() { {"cat", 2}, {"dog", 1}, {"llama", 0}, {"iguana", -1} }; // Loop over pairs with foreach. foreach (KeyValuePair<string, int> pair in data) { Console.WriteLine("FOREACH KEYVALUEPAIR: {0}, {1}", pair.Key, pair.Value); } // Use var keyword to enumerate Dictionary. foreach (var pair in data) { Console.WriteLine("FOREACH VAR: {0}, {1}", pair.Key, pair.Value); } } } Output FOREACH KEYVALUEPAIR: cat, 2 FOREACH KEYVALUEPAIR: dog, 1 FOREACH KEYVALUEPAIR: llama, 0 FOREACH KEYVALUEPAIR: iguana, -1 FOREACH VAR: cat, 2 FOREACH VAR: dog, 1 FOREACH VAR: llama, 0 FOREACH VAR: iguana, -1

Keys. Here we use the Keys property. We then look through each key and look up the values. This method is slower but has the same results.

KeyCollection: The Keys property returns a collection of type KeyCollection, not an actual List. We can convert it into a List.

C# program that gets Keys using System; using System.Collections.Generic; class Program { static void Main() { var data = new Dictionary<string, int>() { {"cat", 2}, {"dog", 1}, {"llama", 0}, {"iguana", -1} }; // Store keys in a List. var list = new List<string>(data.Keys); // Loop through the List. foreach (string key in list) { Console.WriteLine("KEY FROM LIST: " + key); } } } Output KEY FROM LIST: cat KEY FROM LIST: dog KEY FROM LIST: llama KEY FROM LIST: iguana

Types. Dictionary is a generic class. To use it, we must specify a type. This is a good feature. It means we can use an int key just as easily as a string key.

Int: In this program, we see an example of a Dictionary with int keys. The values can also be any type.

C# program that uses int keys using System; using System.Collections.Generic; class Program { static void Main() { // Use int key type. var data = new Dictionary<int, string>(); data.Add(100, "color"); data.Add(200, "fabric"); // Look up the int. if (data.ContainsKey(200)) { Console.WriteLine("CONTAINS KEY 200"); } } } Output CONTAINS KEY 200

LINQ. Extension methods can be used with Dictionary. We use the ToDictionary method. This is an extension method on IEnumerable. It places keys and values into a new Dictionary.

Lambda: The program uses lambda expressions. With these small functions, we specify a method directly as an argument.

Lambda

Here: The example uses ToDictionary, from System.Linq, on a string array. It creates a lookup table for the strings.

C# program that uses System.Linq, ToDictionary using System; using System.Linq; class Program { static void Main() { string[] values = new string[] { "One", "Two" }; // Create Dictionary with ToDictionary. // ... Specify a key creation method, and a value creation method. var result = values.ToDictionary(item => item, item => true); foreach (var pair in result) { Console.WriteLine("RESULT PAIR: {0}, {1}", pair.Key, pair.Value); } } } Output RESULT PAIR: One, True RESULT PAIR: Two, True

ContainsValue. This method lacks the constant-time look up speed of ContainsKey. It instead searches the entire collection. It is linear in complexity.ContainsValue

Note: This example will loop through all elements in the Dictionary until it finds a match, or there are no more elements to check.

Speed: Microsoft states that "this method is an O(N) operation, where N is Count." It does not run in constant time.

C# program that uses ContainsValue using System; using System.Collections.Generic; class Program { static void Main() { var data = new Dictionary<string, int>(); data.Add("cat", 1); data.Add("dog", 2); // Use ContainsValue to see if the value is present with any key. if (data.ContainsValue(1)) { Console.WriteLine("VALUE 1 IS PRESENT"); } } } Output VALUE 1 IS PRESENT

Indexer. We do not need to use Add to insert into a Dictionary. We can instead use the indexer, with the "[" and "]" brackets. This syntax also gets the value at the key.

Caution: If we try to get a value at a key that doesn't exist, an exception is thrown.

Note: With the indexer, an exception is not thrown when we assign to a key that already has a value. But with Add, an exception is thrown.

C# program that uses Dictionary indexer using System; using System.Collections.Generic; class Program { static void Main() { Dictionary<int, int> dictionary = new Dictionary<int, int>(); // We can assign with the indexer. dictionary[1] = 2; dictionary[2] = 1; dictionary[1] = 3; // Reassign. // Read with the indexer. // ... An exception occurs if no element exists. Console.WriteLine(dictionary[1]); Console.WriteLine(dictionary[2]); } } Output 3 1

Remove, Count. With Remove, no remnants of the key-value pair are kept. Sometimes using null as a key's value is a better option—but this may add complexity to a program.

Note: Running the code in Visual Studio, no exceptions are thrown. When we remove a key that doesn't exist, nothing happens.

However: Remove() throws System.ArgumentNullException with a null parameter. We cannot remove null.

Count: This computes the total number of keys. Count is the simplest way to count all pairs in a Dictionary.

Count

C# program that uses Remove, Count using System; using System.Collections.Generic; class Program { static void Main() { var data = new Dictionary<string, int>(); data.Add("cat", 1); data.Add("dog", 2); Console.WriteLine("COUNT: " + data.Count); // Remove cat. data.Remove("cat"); Console.WriteLine("COUNT: " + data.Count); // This does not remove anything. data.Remove("nothing"); Console.WriteLine("COUNT: " + data.Count); } } Output COUNT: 2 COUNT: 1 COUNT: 1

Copy. Dictionary provides a constructor that copies all values and keys into a new Dictionary instance. This constructor improves code reuse. It makes copying simpler.Copy Dictionary

Test: The "test" Dictionary in this program is created, and has just 1 key and value pair in it.

Copy: We create a copy by passing the "test" Dictionary to its constructor. We add a key. The copy has 2 keys—but "test" still has 1.

C# program that copies Dictionary using System; using System.Collections.Generic; class Program { static void Main() { var test = new Dictionary<int, int>(); test[20] = 30; // Copy the dictionary, and add another key, so we now have 2 keys. var copy = new Dictionary<int, int>(test); copy[30] = 40; Console.WriteLine("TEST COUNT: {0}", test.Count); Console.WriteLine("COPY COUNT: {0}", copy.Count); } } Output TEST COUNT: 1 COPY COUNT: 2

Composite keys. We can sometimes use multiple variables in a key. We can create a special function that transforms those variables into a string, serializing them.

SetComposite: This method receives 2 ints—the parts of the key. It creates a string with a comma, and assigns into the Dictionary.

GetComposite: This looks up a value in the Dictionary with 2 int arguments—the same string key is generated on each call.

Result: We use the string "1,2" to mean the ints 1 and 2. A string is created each time. We have 2 keys per value.

C# program that uses composite keys using System; using System.Collections.Generic; class Program { static Dictionary<string, string> _composite = new Dictionary<string, string>(); static void SetComposite(int part1, int part2, string value) { // Use 2 ints for the string key. _composite[part1.ToString() + "," + part2.ToString()] = value; } static string GetComposite(int part1, int part2) { // Create composite string to look up result. _composite.TryGetValue(part1.ToString() + "," + part2.ToString(), out string result); return result; } static void Main() { // Set values in Dictionary with composite keys. SetComposite(1, 2, "hello"); SetComposite(300, 400, "aloha"); // Get values in Dictionary with composite keys. Console.WriteLine("GETCOMPOSITE: {0}", GetComposite(1, 2)); Console.WriteLine("GETCOMPOSITE: {0}", GetComposite(300, 400)); } } Output GETCOMPOSITE: hello GETCOMPOSITE: aloha

Dictionary field. Sometimes it is useful to have a Dictionary at the class level, as a field. And if we have a static class, we should initialize the Dictionary at the class level.

Note: Avoid the static constructor—static constructors often carry performance penalties.

C# program that uses Dictionary field using System; using System.Collections.Generic; class Example { Dictionary<int, int> _lookup = new Dictionary<int, int>() { {1, 1}, {2, 3}, {3, 5}, {6, 10} }; public int GetValue() { return _lookup[2]; // Example only. } } class Program { static void Main() { // Create Example object instance. var example = new Example(); // Look up a value from the Dictionary field. Console.WriteLine("RESULT: " + example.GetValue()); } } Output RESULT: 3

KeyNotFoundException. This error happens when we access a nonexistent key. With Dictionary we should test keys for existence first, with ContainsKey or TryGetValue.KeyNotFoundException

C# program that shows KeyNotFoundException using System.Collections.Generic; class Program { static void Main() { var colors = new Dictionary<string, int>() { { "blue", 10 } }; // Use ContainsKey or TryGetValue instead. int result = colors["fuschia"]; } } Output Unhandled Exception: System.Collections.Generic.KeyNotFoundException: The given key was not present in the dictionary. at System.Collections.Generic.Dictionary`2.get_Item(TKey key) at Program.Main() in ...

Benchmark, StringComparer. When you do a lookup on a Dictionary of string keys, the string must be hashed. If we pass StringComparer.Ordinal to our Dictionary, we have a faster algorithm.

Version 1: We look up the key "Las Vegas" in a Dictionary with no comparer specified in its constructor.

Version 2: In this version we look up the string "Las Vegas" in a Dictionary with StringComparer.Ordinal.

Result: When we consider a string as "ordinal," we lose some string features, but gain performance on comparison and hashing.

C# program that times StringComparer.Ordinal using System; using System.Collections.Generic; using System.Diagnostics; class Program { const int _max = 10000000; static void Main() { var data1 = new Dictionary<string, bool>(); data1["Las Vegas"] = true; var data2 = new Dictionary<string, bool>(StringComparer.Ordinal); data2["Las Vegas"] = true; // Version 1: do lookups on Dictionary with default string comparisons. Stopwatch s1 = Stopwatch.StartNew(); for (int i = 0; i < _max; i++) { if (!data1.ContainsKey("Las Vegas")) { return; } } s1.Stop(); // Version 2: do lookups in Dictionary that has StringComparer.Ordinal. Stopwatch s2 = Stopwatch.StartNew(); for (int i = 0; i < _max; i++) { if (!data2.ContainsKey("Las Vegas")) { return; } } s2.Stop(); Console.WriteLine(((double)(s1.Elapsed.TotalMilliseconds * 1000000) / _max).ToString("0.00 ns")); Console.WriteLine(((double)(s2.Elapsed.TotalMilliseconds * 1000000) / _max).ToString("0.00 ns")); } } Output 19.65 ns ContainsKey, default comparer 18.99 ns ContainsKey, StringComparer.Ordinal

Benchmark, Keys. Here we compare loops. A foreach-loop on KeyValuePairs is faster than the looping over Keys and accessing values in the loop body.

Version 1: This code loops over the dictionary in a foreach-loop directly, without accessing the Keys property.

Version 2: This version of the code accesses the Keys property, and then looks up each value in a foreach-loop.

Result: When possible, loop over the pairs in a Dictionary directly. Eliminating lookups will improve performance.

C# program that benchmarks foreach on Dictionary using System; using System.Collections.Generic; using System.Diagnostics; class Program { static void Main() { var test = new Dictionary<string, int>(); test["bird"] = 10; test["frog"] = 20; test["cat"] = 60; int sum = 0; const int _max = 1000000; // Version 1: use foreach loop directly on Dictionary. var s1 = Stopwatch.StartNew(); for (int i = 0; i < _max; i++) { foreach (var pair in test) { sum += pair.Value; } } s1.Stop(); // Version 2: use foreach loop on Keys, then access values. var s2 = Stopwatch.StartNew(); for (int i = 0; i < _max; i++) { foreach (var key in test.Keys) { sum += test[key]; } } s2.Stop(); Console.WriteLine(s1.Elapsed.TotalMilliseconds); Console.WriteLine(s2.Elapsed.TotalMilliseconds); } } Output 28.117 ms Dictionary foreach 83.3468 ms Keys foreach

Benchmark, GetEnumerator. With the GetEnumerator method we can loop over a Dictionary. We call GetEnumerator() and then use a while-loop on the MoveNext method.

Version 1: This code uses the foreach loop to sum the values in a Dictionary collection.

Version 2: This method uses the GetEnumerator method, the MoveNext method, and the Current property to sum the values.

GetEnumerator

Result: By using GetEnumerator, our loop is faster. The IL generated is a bit different (no try-finally block is generated).

C# program that times GetEnumerator, MoveNext using System; using System.Collections.Generic; using System.Diagnostics; class Program { static int Version1(Dictionary<string, int> values) { int sum = 0; foreach (var pair in values) { sum += pair.Value; } return sum; } static int Version2(Dictionary<string, int> values) { int sum = 0; var enumerator = values.GetEnumerator(); while (enumerator.MoveNext()) { var pair = enumerator.Current; sum += pair.Value; } return sum; } const int _max = 1000000; static void Main() { var data = new Dictionary<string, int>(); data["bird"] = 1; data["cat"] = 2; data["feather"] = -1; data["fur"] = -2; // Version 1: use foreach to loop over a Dictionary. var s1 = Stopwatch.StartNew(); for (int i = 0; i < _max; i++) { Version1(data); } s1.Stop(); // Version 2: use GetEnumerator to loop over a Dictionary. var s2 = Stopwatch.StartNew(); for (int i = 0; i < _max; i++) { Version2(data); } s2.Stop(); Console.WriteLine(((double)(s1.Elapsed.TotalMilliseconds * 1000000) / _max).ToString("0.00 ns")); Console.WriteLine(((double)(s2.Elapsed.TotalMilliseconds * 1000000) / _max).ToString("0.00 ns")); } } Output 41.07 ns foreach 39.51 ns GetEnumerator, MoveNext

Benchmark, key length. When a string key is looked up in a Dictionary, it must be hashed and compared. Logically a shorter string key should be faster, as less data is being tested.

Version 1: This code looks up a short string key in the Dictionary—each lookup is just 4 chars.

Version 2: Here we look up a string key that is longer. Each lookup succeeds (in the same way as version 1).

Result: The version that looks up the key "Alps" is faster than the version that looks up the string key "Appalachian."

C# program that times string key length using System; using System.Collections.Generic; using System.Diagnostics; class Program { const int _max = 10000000; static void Main() { var places = new Dictionary<string, int>() { { "Alps", 1 }, { "Appalachian", 2 } }; // Version 1: look up a short string key. var s1 = Stopwatch.StartNew(); for (int i = 0; i < _max; i++) { if (!places.ContainsKey("Alps")) { return; } } s1.Stop(); // Version 2: look up a long string key. var s2 = Stopwatch.StartNew(); for (int i = 0; i < _max; i++) { if (!places.ContainsKey("Appalachian")) { return; } } s2.Stop(); Console.WriteLine(((double)(s1.Elapsed.TotalMilliseconds * 1000000) / _max).ToString("0.00 ns")); Console.WriteLine(((double)(s2.Elapsed.TotalMilliseconds * 1000000) / _max).ToString("0.00 ns")); } } Output 18.32 ns 4-char string key 21.00 ns 12-char string key

Clear. We can erase all pairs with the Clear method. Or we can assign the Dictionary variable to null. This causes little difference in memory usage—the entries are garbage-collected.Dictionary Clear

Return. A Dictionary can be returned, or passed as an argument. The Dictionary type is defined as a class. It is always passed as a reference type.

And: This means only 32-64 bits will be copied on the method invocation. The same principle applies when returning values.

Return

Custom methods. Knowing how to use the methods on a Dictionary is only the first accomplishment. As a developer you will need to design custom methods that use dictionaries.Dictionary, Binary File Dictionary, Combine Keys Dictionary, Equals Dictionary, Sort

IEqualityComparer. Dictionary uses an IEqualityComparer to compute the hash code for its keys. We can implement this interface with a class. This can improve performance.IEqualityComparer

Map. The Dictionary is a map. A real map helps us find our destination, but a digital map directs us from a key to a value. In languages we often find a map type.Map

Case-insensitive keys. With a special StringComparer we can have case-insensitive key lookups on a dictionary. This reduces the need to call ToLower. It reduces string creation.Case, Dictionary

Research. A Dictionary is powerful, but it is not magic. It just uses a good algorithm. This requires a hash code. We take keys and use arithmetic to transform them into numbers.

Locations: We then store them in locations based on those numbers in the Dictionary. We select a "bucket" based on the hash.

Finally: When we go to look up a key, we compute a new hash code and look for it in the Dictionary. Less searching is needed.

Quote: We try to reference items in a table directly by doing arithmetic operations to transform keys into table addresses (Algorithms in C++ Third Edition).

A summary. It is good that fast lookups are important. We just spent lots of time researching them. Dictionary, like all hash tables, is fascinating. It is fast—and useful in many places.

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

C# Dictionary Examples

Related Links:

.Net

Java

Related Links