C# Dictionary

Array Collections File Keyword String .NET Cast Class Data Dictionary Enum Exception If Interface Lambda LINQ List Loop Method Number Process Property Regex Sort Split StringBuilder Struct Substring Switch Time Windows

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

A generic, Dictionary uses a special syntax form. We specify its key and value types. A custom class is constructed based on these parameters.


String

An example. We add four keys with values. Afterwards, we look inside the Dictionary with the Visual Studio debugger. The Dictionary is composed of separate keys and values.

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

Output:The example program has no output: it does nothing useful. At least it does not crash.

Based on:

.NET 4.5

C# program that uses Add method

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);
    }
}
Locals: Dictionary keys and values

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.

Note:It is fun (and perhaps helpful) to open and close the data structure elements. Learning often involves experimentation.

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


True keyword

ContainsKey. This 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 true if the key is found.

ContainsKey
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
Try

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

TryGetValue
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
KeyValuePair: Key and Value properties

KeyValuePair. When a collection that implements IDictionary (like Dictionary) is used in a foreach-loop, it returns an enumeration. A Dictionary will return KeyValuePair structs in a loop.

KeyValuePair
Error

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

KeyNotFoundException
Loop

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 has two members, a string Key and an int Value.

C# program that uses foreach on Dictionary

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
Var keyword

Var keyword. The final loop in the above code uses var. This reduces the amount of typing required. And it may make code easier to read for humans (like us).

VarVar Dictionary
Key: used to access value

Keys. 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.

Note: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.

C# program that gets Keys

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
Performance

Benchmark. I found a foreach-loop on KeyValuePairs is faster than the Keys method. KeyValuePair allows us to look through each pair. This avoids lookups and allocations.

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

Sort. A Dictionary cannot be directly sorted. But we can take its Keys and then sort those in a separate List collection. A query expression may also be used.

Sort Dictionary
Int

Types. 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.

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 a Dictionary with an int key.
	Dictionary<int, string> dict = new Dictionary<int, string>();
	dict.Add(100, "Bill");
	dict.Add(200, "Steve");
	// We can look up the int in the Dictionary.
	if (dict.ContainsKey(200))
	{
	    Console.WriteLine(true);
	}
    }
}

Output

True
LINQ: Language Integrated Query

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.

Lambdas

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

ToDictionary
C# that uses LINQ

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
Cover logo

ContainsValue. This method does not enjoy the constant-time lookup 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:MSDN states that "this method is an O(N) operation, where N is Count." It does not run in constant time.

C# that uses ContainsValue

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
Index

Indexer. Instead of calling Add on a Dictionary to add a new value, we can use the indexer with the "[" and "]" brackets. This syntax can also be used to get the value at the key.

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.

C# that uses Dictionary indexer

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.

	// Read with the indexer.
	// ... An exception occurs if no element exists.
	Console.WriteLine(dictionary[1]);
	Console.WriteLine(dictionary[2]);
    }
}

Output

3
1
None

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.

Clear

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

Array.Clear
Pound symbol

Count. This computes the total number of keys in a Dictionary. This is much simpler than accessing the Keys property, or looping over the Dictionary to count it.

Count
Copyright

Remove. We can eliminate an entry, not just by setting its value to null or string.Empty, but by also removing the key itself. With Remove, 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.

C# that uses Remove

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.
    }
}
Copy: new object copied

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
Return keyword

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
Collections: Dictionary, Tuple and Set

List versus Dictionary. I suggest you almost always use Dictionary for lookups. In large collections, a List will become unusable for lookups.

But:A Dictionary will still work well with large amounts of data. With Dictionary your program recovers from pathological, edge cases.

List

Looping:It is faster to loop through elements in a List. If looping through elements is the most common operation, a List is superior.

Dictionary vs. List Loops
Elements: sorting elements in an array

SortedDictionary. We find other collections,
such as SortedDictionary,
in the .NET Framework. They tend to be slower than Dictionary.

SortedDictionaryCollections
ABC: letters

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.

Note:We can use the string "1,2" to mean the ints 1 and 2. This approach is not optimally fast.

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


Field

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# that uses Dictionary field

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
Arrow indicates looping

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.

GetEnumerator
Convert

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.

IEqualityComparerIEqualityComparer: Ignore Chars
Steps

Performance. The Dictionary is well-optimized by the .NET Framework developers. They are smart people. But there are still some techniques that influence performance.

Change Add OrderIncrease CapacityUse Smaller DictionaryShorten Key LengthUse StringComparerTest Before AddingMeasure Memory UsageBenchmark
List

Compare types. Sometimes, an array or List can be used instead of a Dictionary. This influences performance. Any analysis depends on the program.

Array vs. DictionaryList vs. Dictionary

Misc. Not all requirements are satisfied by built-in methods. We require some custom methods. These methods are examples of the custom routines we 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
Books

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.

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.

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

Algorithms in C++
Time

A comment. 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.


What we did. We checked key existence with ContainsKey and TryGetValue.
Dictionary,
like all hash tables,
is fascinating. Astonishingly fast, it is useful in many places.

C#