C# Dictionary

Dictionary

Fast lookups are critical.
Dictionaries provide fast lookups,
based on keys,
to get values. With them, we use keys and values of any type, including int and string. Dictionary uses a special syntax form.

IntStrings

Add

Let us get started. We add four keys with values to a Dictionary instance. Afterwards, we look inside the Dictionary with the Visual Studio debugger. The Dictionary is composed of separate keys and values.

Framework: NET

Here:We see the Dictionary code.
The example program has no output: it does nothing useful.

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

Based on:

.NET 4.5

Program that uses Add method: C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	Dictionary<string, int> dictionary =
	    new Dictionary<string, int>();
	dictionary.Add("cat", 2);
	dictionary.Add("dog", 1);
	dictionary.Add("llama", 0);
	dictionary.Add("iguana", -1);
    }
}

Debugger

Let us peek inside the Visual Studio debugger to examine the memory. The Dictionary instance is represented by a collection of key and value pairs. It is fun (and perhaps helpful) to open and close the data structure elements.

Tip:The pairs like (dog, 1) are the string representations of KeyValuePair instances. KeyValuePair is a struct.

Dictionary locals

ContainsKey

Copy: new object copied

Next, you can check to see if a given string is present in a Dictionary with string keys. We look at more types of Dictionaries further on, but here is the ContainsKey method. It returns true if the key was found.

ContainsKey

Tip:There is a more efficient method called TryGetValue. You should definitely use it when possible.

And:As its name implies, it tests for the key and then returns the value if it finds the key.

TryGetValue
Program that uses ContainsKey: C#

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 Dictionary contains this string.
	if (!dictionary.ContainsKey("acorn"))
	{
	    Console.WriteLine(false);
	}
    }
}

Output

1
False

Also, we sometimes encounter a KeyNotFoundException. This happens when we access a key that does not exist. With Dictionary we must test keys for existence first, with ContainsKey or TryGetValue.

KeyNotFoundException

KeyValuePair

KeyValuePair: Key and Value properties

When Dictionary, or any object that implements IDictionary, is used in a foreach-loop, it returns an enumeration. In the case of Dictionary, this enumeration is in the form of KeyValuePair values.

KeyValuePair

Loop

Foreach loop construct

Here we use foreach syntax and KeyValuePair generics in the foreach loop. With collections like Dictionary, we must always know the value types.
With each KeyValuePair,
there is a Key member
and Value member.

Foreach
Program that uses foreach on Dictionary: C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	// Example Dictionary again
	Dictionary<string, int> d = new Dictionary<string, int>()
	{
	    {"cat", 2},
	    {"dog", 1},
	    {"llama", 0},
	    {"iguana", -1}
	};
	// Loop over pairs with foreach
	foreach (KeyValuePair<string, int> pair in d)
	{
	    Console.WriteLine("{0}, {1}",
		pair.Key,
		pair.Value);
	}
	// Use var keyword to enumerate dictionary
	foreach (var pair in d)
	{
	    Console.WriteLine("{0}, {1}",
		pair.Key,
		pair.Value);
	}
    }
}

Output

cat, 2
dog, 1
llama, 0
iguana, -1

cat, 2
dog, 1
llama, 0
iguana, -1
Arrow indicates looping

The code creates a Dictionary with string keys and int values. The Dictionary stores animal counts. The program has a ShowDictionaryPair method. This method shows the foreach-loop and the KeyValuePair declaration.

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

Var keyword

The final loop in the code shows how to make the syntax for looping simpler by using the var keyword. This is not desirable in some projects. But for KeyValuePair, it reduces source code size. It makes code easier to read.

VarVar Dictionary

Keys

Key: used to access value

Here we use the Keys property. We then look through each key and lookup the values. This method is slower but has the same results. Using the Keys collection and putting it in an array or List is sometimes effective.

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

Program that gets Keys: C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	Dictionary<string, int> d = new Dictionary<string, int>()
	{
	    {"cat", 2},
	    {"dog", 1},
	    {"llama", 0},
	    {"iguana", -1}
	};
	// Store keys in a List
	List<string> list = new List<string>(d.Keys);
	// Loop through list
	foreach (string k in list)
	{
	    Console.WriteLine("{0}, {1}",
		k,
		d[k]);
	}
    }
}

Output

cat, 2
dog, 1
llama, 0
iguana, -1

Benchmark

Performance optimization

Using foreach on KeyValuePairs is several times faster than using Keys. KeyValuePair allows us to look through each pair. This avoids lookups. And it avoids changes to the garbage-collected heap.

Note:These figures are not perfect. I made a small change to the Keys version, so these figures are only general.

Benchmark for KeyValuePair foreach-loop

KeyValuePair: 125 ms
Note:         This loops through the pairs in the Dictionary.

Keys loop:    437 ms
Note:         This gets the Keys, then loops through them.
	      It does another lookup for the value.

Sort

Sorted letters: A to Z

If you need to sort the values in a Dictionary, you may be perplexed at first and wonder how to order the keys. I have an article about how to do this. It is not optimal but it works.

Info:A dictionary cannot be sorted.
But we can extract its keys and values and then sort those.

Sort Dictionary

Types

Int keyword

Dictionary is a generic class. This means it requires you to specify a type for it to use. So, you can use an int key, just as easily as a string key. In this program, we see an example of a Dictionary with int keys.

Tip:For advanced developers, you can use the GetHashCode method and override it to create Dictionaries or hashes with the class.

Program that uses int keys: C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	// Use a dictionary with an int key.
	Dictionary<int, string> dict = new Dictionary<int, string>();
	dict.Add(100, "Bill");
	dict.Add(200, "Steve");
	// You can look up the int in the dictionary.
	if (dict.ContainsKey(200))
	{
	    Console.WriteLine(true);
	}
    }
}

Output

True

LINQ

LINQ: language integrated query

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. The program uses lambda expressions.

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

ToDictionary

Note:This step has an initial cost.
The program will require more time to start up.
But it optimizes later performance.

Program that uses LINQ: C#

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

class Program
{
    static void Main()
    {
	string[] arr = new string[]
	{
	    "One",
	    "Two"
	};
	var dict = arr.ToDictionary(item => item, item => true);
	foreach (var pair in dict)
	{
	    Console.WriteLine("{0}, {1}",
		pair.Key,
		pair.Value);
	}
    }
}

Output

One, True
Two, True

ContainsValue

Note

Dictionary has a method called ContainsValue. This method does not enjoy the constant-time lookup speed of ContainsKey. It instead searches the entire collection. It is linear in complexity.

This example will loop through all elements in the Dictionary until it finds a match, or there are no more elements to check. MSDN states that "this method is an O(N) operation, where N is Count."

ContainsValue
Program that uses ContainsValue: C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	Dictionary<string, int> d = new Dictionary<string, int>();
	d.Add("cat", 1);
	d.Add("dog", 2);
	if (d.ContainsValue(1))
	{
	    Console.WriteLine(true); // true
	}
    }
}

Output

True

Indexer

Note

Instead of calling Add on a Dictionary to add a new value, you can use the indexer with the "[" and "]" brackets. This syntax can also be used to get the value at the key. There are some advantages to this.

Caution:If you 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 you assign to a key that already has a value. But with Add, an exception is thrown.

Program that uses Dictionary indexer: C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	Dictionary<int, int> dictionary = new Dictionary<int, int>();

	// You can assign with the indexer.
	dictionary[1] = 2;
	dictionary[2] = 1;
	dictionary[1] = 3; // Reassign.

	// You can read with the indexer.
	// ... If you read an element that doesn't exist, you get an exception.
	Console.WriteLine(dictionary[1]);
	Console.WriteLine(dictionary[2]);
    }
}

Output

3
1

Clear

Pound symbol

You can erase all pairs by using the Clear method. Or you can assign the variable to null. The difference between Clear and null is not important for memory usage. In either case, the entries are garbage-collected.

Internally:We find that Clear calls Array.Clear, which is not managed code. Dictionary is implemented with arrays.

Clear

Count

The Count method is an effective way to compute the total number of keys in the instance. This is much simpler than accessing the Keys property, or looping over the Dictionary to count it.

Count

Remove

Visual Studio logo

We can eliminate an entry, not just by setting its value to null or string.Empty, but by also removing the key itself. We use the Remove method. No remnants of the key-value pair are kept.

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

However:Remove throws System.ArgumentNullException with a null parameter. You cannot remove null.

Program that uses Remove: C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	Dictionary<string, int> d = new Dictionary<string, int>();
	d.Add("cat", 1);
	d.Add("dog", 2);

	d.Remove("cat"); // Removes cat
	d.Remove("nothing"); // Doesn't remove anything
    }
}

Result
    The key "cat" is removed.

Copy

The Dictionary class has a constructor that copies all values and keys into a new Dictionary instance. You can write the logic yourself. But using this constructor improves code reuse and simplicity.

Note:This site has more information on the Dictionary copy constructor. We demonstrate how it writes into separate memory.

Copy Dictionary

Return

Return keyword

It is also possible to use a Dictionary as an argument to methods or as a return value from methods or properties. 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 principles apply when with return values.

Return

List vs. Dictionary

Collections

I suggest you almost always use Dictionary for lookups. If you use List and you need to look up a key, your program may freeze if you have excess elements. With Dictionary your program recovers from pathological, edge cases.

List

On the other hand, it is faster to loop through all the elements in a List than in a Dictionary. If looping through elements is the most common operation, a List is superior. Usually looping speed is not critical.

Dictionary vs. List Loops

Also:You will find other collections, such as SortedDictionary, in the .NET Framework available for you to use.

But:I have found it is hard to get equivalent performance as you can with Dictionary.

SortedDictionary

Composite keys

Programming tip

You can sometimes use multiple variables in a key by creating a special function that transforms those variables into a string, serializing them. So, you could use the string "1,2" to mean the ints 1 and 2.

Tip:This is similar to how composite names in programming languages use a period: "Type.Member".

Field

Variable

Sometimes it is useful to have a Dictionary at the class level, not in a method or constructor. And if you have a static class then you should initialize your Dictionary at the class level.

Also:Avoid the static constructor—static constructors have performance penalties, which I have measured.

Program that uses Dictionary field: C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	Example e = new Example();
	Console.WriteLine(e.GetValue());
    }
}

class Example
{
    Dictionary<int, int> _d = new Dictionary<int, int>()
    {
	{1, 1},
	{2, 3},
	{3, 5},
	{6, 10}
    };
    public int GetValue()
    {
	return _d[2]; // Example only
    }
}

Output

3

GetEnumerator

It is possible to loop over a Dictionary without a foreach-loop. We use the GetEnumerator method and then a while-loop on the MoveNext method. This improves performance slightly, but adds complexity.

GetEnumerator

IEqualityComparer

Convert

The Dictionary type uses an IEqualityComparer to determine the hash code for its keys. You can implement this interface with a class. This can improve performance in some programs, but often has limited benefits.

IEqualityComparer

Fuzzy:An IEqualityComparer can match strings in a fuzzy way. This optimizes speed by eliminating allocations.

IEqualityComparer: Fuzzy

Performance

Performance optimization

We revisit here Dictionary performance. The Dictionary is well-optimized by the .NET Framework developers. But there are still some techniques that influence performance. Knowing how Dictionary works is important.

1. Change add order.The order we add keys to a Dictionary influences how fast those keys are looked up in the future.

Change Add Order

2. Increase capacity.We can increase the capacity to about four times what it needs to be to accommodate all elements.

Increase Capacity

3. Use smaller collections.If you have two different sets of data, using two different Dictionaries may help.

Use Smaller Dictionary

4. Shorten lookup keys.For a Dictionary with string keys, short lookup keys can improve performance.

Shorten Key Length

5. Use faster comparer.Also for Dictionaries with string keys, you can use a faster StringComparer.

Use StringComparer

6. Test keys for existence.It is best to use ContainsKey to see if a key exists before changing it.

Test Before Adding

7. Measure memory usage.When optimizing a program, you are possibly wasting your time unless you measure your progress.

Measure Memory UsageBenchmark

Compare

Not equal

These articles compare Dictionary to other collections such as an array and a List. In some program contexts, arrays and Lists can be used instead of a Dictionary. Some aspects of performance are more important than others.

Array vs. DictionaryList vs. Dictionary

Caution:Some of the optimization tips do not apply to most programs. And some tips may cause minimal benefits or even performance loss.

Also:We see examples of the classic tradeoff in computer science: faster lookups but with less memory efficiency.

Misc.

Miscellaneous

Not all requirements you may have with your collections are satisfied by the built-in methods. You will require some custom methods. These methods provide a sample of the custom routines you can construct.

Dictionary Binary FileDictionary EqualsCombine Dictionary Keys

Also:These examples show Dictionary instances used in different contexts. They may be less useful.

Case, DictionaryStatic DictionaryStopword Dictionary

Research

How does a Dictionary (or hashtable) work? The essential principle involves a hash code. We take keys and use arithmetic to transform them into numbers. We then store them in locations based on those numbers in the Dictionary.

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.

We try to reference items in a table directly by doing arithmetic operations to transform keys into table addresses. Sedgewick, p. 587

Summary

Concept

It is good that fast lookups are important. We just spent lots of time explaining how to do them. We looped over a Dictionary with KeyValuePair. And we checked key existence with ContainsKey and TryGetValue (my favorite method).

Thus:Dictionary, like all hash tables, is fascinating. Astonishingly fast, it is useful in many places.


C#: Collections