Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C# (http://www.go4expert.com/articles/c-sharp-tutorials/)
-   -   Understanding C# Dictionaries WIth Examples (http://www.go4expert.com/articles/understanding-c-sharp-dictionaries-t30034/)

shabbir 26Mar2014 11:23

Understanding C# Dictionaries WIth Examples
 
In my recent articles, I have been walking you through some of the most commonly used types and interfaces that play integral role in storing collection of items. We have previously studied Lists, Stacks, Queues and other collections. I have also explained Array class and its usage in one of my previous articles. Today, I will show you another extremely important as well as interesting collection called the Dictionary collection.

A dictionary is a collection where elements are stored in the form of a Key/Value pair. Usually dictionaries are used for sorted lists of elements and lookups. All the dictionary types have to implement either or both IDictionary or the generic version i.e. IDictionary<TKey, TValue> interface. In C# framework, we have following dictionary classes.

UnSorted Dictionary Classes
  • Hashtable
  • Dictionary<Key, Value>
  • ListDictionary
  • OrderedDictionary.
Sorted Dictionary Classes
  • SortedList
  • SortedList<Key, Value>
  • SortedDictionary <Key, Value>
Basically, the IDictionary<TKey, TValue> interface extends the ICollection<T> interface by adding methods and properties that are useful for accessing elements of the collection based on the key.

In order to add an element into a dictionary collection you have two ways. You either use an Add method to add element to a dictionary or you can use set accessor of the index to store element at that particular index. The second method i.e. setting index’s value can only add item if the key is not already present in the collection. Dictionary can contain unique keys for element. Therefore, if you try to add items with the key already present in the dictionary, an exception will be thrown.

Similarly, in order to get element from a dictionary you can either use TryGetValue method or can get value using indexer. If you use get element on the basis of index an exception will be thrown if the element is not found. However in case of TryGetValue method, if the element is not found no exception is thrown, instead the method returns false. Though you can use ContainsKey method first to check whether element with the specified key exists or not and then you can use indexers to get the item but in that case, two calls would be needed. Therefore, it is always advisable to get elements from a dictionary collection using TryGetValue method.

If you enumerate over a class implementing IDictionary<TKey,TValue> interface, the result will be a series of KeyValuePair struct which looks like this:
Code:

public struct KeyValuePair<TKey, TValue>
{
    public TKey Key {get;}
    public TValue Value {get;}
}

From this struct you can get either or both the keys and values by calling dictionaries key value properties.
Now come towards the non-generic version of the dictionary interfaces. IDictionary is almost similar to the generic version i.e. IDictionary<TKey, TValue> with three exceptions.
  • If you get a key which is non-existent, via an indexer in dictionary collection, null will be returned instead of exception which is the case in generic version.
  • Instead of ContainsKey, Contains method is used to check whether or not a particular key exists.
  • If you enumerate over a class that implements IDictionary interface, the returned values will be a sequence of DictionaryEntry structs unlike KeyValyePair structs. DictionaryEntry struct looks like this:
Code:

public struct DictionaryEntry
{
    public object Key {get;set;}
    public object Value {get;set;}
}

Dictionary <TKey, TValue> & Non-generic Hashtable



Of all the dictionary classes, Dictionary <TKey, TValue> is used most widely and frequently. Also, amongst all the generic and non-generic collections, Dictionary <TKey, TValue> and List<T> are used more often.

A very important thing to note here is that the non-generic version of Dictionary<TKey, TValue> collection is called Hashtable. There is no Dictionary collection which refers to the non-generic version of the Dictionary<TKey, TValue>, rather when we refer to Dictionary, we are actually referring to Dictionary<TKey, TValue>.

The Dictionary class implements generic as well as non-generic version of IDictionary interfaces; however the non-generic interface is not exposed publicly whereas the generic interface is exposed publicly.

Now enough of theory let us practically jump into the implementation of Dictionary classes. In our first example, I am going to show you how the Dictionary collection is used to store collection of items with associated keys. Have a look at our first example.

Example1
Code:

using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Numerics;

namespace CSharpTutorial
{
    class Program
    {
        public static void Main()
        {
            Dictionary<int, string> numcoll = new Dictionary<int, string> { };

            numcoll.Add(1, "One"); // Adding KeyValue pairs via Add method
            numcoll.Add(2, "Two"); // Adding KeyValue pairs via Add method

            numcoll[3] = "Three";  // Adding KeyValue pairs via indexes
            numcoll[4] = "Four";  // Adding KeyValue pairs via indexes

            Console.WriteLine(numcoll[2]);
            Console.WriteLine(numcoll.ContainsKey(4));
            Console.WriteLine(numcoll.ContainsValue("Three"));

            string num;

            if (!numcoll.TryGetValue(5, out num))
            {
                Console.WriteLine("Key Doesnt Exist");
            }
            else
            {
                Console.WriteLine(num);
            }

            Console.WriteLine("\n***************************\nEnumerating over Dictionary");
            foreach(KeyValuePair<int,string> nums in numcoll)
            {
            Console.WriteLine(nums.Key+" "+nums.Value);
            }

            Console.WriteLine("\n*************************************\nEnumerating over Dictionary Keys");
            foreach (int nums in numcoll.Keys)
            {
                Console.WriteLine(nums);
            }

            Console.WriteLine("\n*************************************\nEnumerating over Dictionary Values");
            foreach (string nums in numcoll.Values)
            {
                Console.WriteLine(nums);
            }
            Console.ReadLine();
        }
    }
}

The code in Example1 might look daunting at first but it actually isn’t. Let us see what is happening in this code. I will explain the code line by line from the start.

In the beginning of the code, we have declared a dictionary collection which we have named ‘numcoll’. This collection can store key-value pairs where keys will be integer types and values will be string types. We will store integers as keys and their corresponding values in words as values of the ‘numcoll’.

In the next lines of code we have added some key-value pairs in the ‘numcoll’ using Add methods. These are the lines of code where we have used the Add method to add key-value pair into a dictionary.
Code:

numcoll.Add(1, "One"); // Adding Key-Value pairs via Add method
numcoll.Add(2, "Two"); // Adding Key-Value pairs via Add method

Notice here that, we have added keys as integer and their values as strings. When the key is integer 1, the value is string “One”. You can add any value, but it should be string type. Here we have used key-value pairs of integer and string respectively to better explain the concept. This is one way of adding key-value pairs into a dictionary. But we explained that we can also set and get items of the dictionary using indexers. In the next lines we did that. Consider these lines of code
Code:

numcoll[3] = "Three";  // Adding Key-Value pairs via indexes
numcoll[4] = "Four";  // Adding Key-Value pairs via indexes

In order to set values using indexers, you simply have to use array style indexing. But in square brackets, instead of mentioning the index, you have to mention the key. For example, if you mention 3 in ‘numcoll’ index brackets and equate it to some string value ‘Three’, it means that you are telling the compiler to add a key-value pair to dictionary ‘numcoll’ with key being the integer ‘3’ and the value being string ‘Three’.

Similarly, you can also excess the value from a dictionary by specifying its key as the dictionary index. We have done this in the next line where we are accessing the value with key ‘2’ and displaying it on the console. This is the line which does that.
Code:

Console.WriteLine(numcoll[2]);
The next two lines of code are particularly interesting.
Code:

Console.WriteLine(numcoll.ContainsKey(4));
Console.WriteLine(numcoll.ContainsValue("Three"));

In the above lines of code, first we have called ContainsKey method and passed it the integer ‘4’ this would return true since we have key 4 in the numcoll dictionary. Next, we have called ContainsValue method and passed it string value ‘Three’. This would also evaluate to true because we have value ‘Three’ in the dictionary. However, ContainsKey method would be faster as compared to ContainsValue method.

Next, TryGetValue method has been used inside the ‘if’ statement. This method actually takes Key and returns the corresponding value. We have passed it another parameter ‘num’ of type string to which the returned value will be stored. TryGetValue method returns false, if the key passed to it is non-existent. We have passed it key ‘5’ which doesn’t exist in the ‘numcoll’ dictionary, so the method would return false.

Now, come to the last and extremely interesting part of the code. We mentioned earlier that we can enumerate over a Dictionary<TKey, TValye> class and this class actually returns a sequence of KeyValuePair<TKey, TValue>. In our example, Key-value pair with integer type key and string type value would be return since our ‘numcoll’ dictionary has a key of type integer and value of type string. Therefore, in our foreach loop we fetch single KeyValuePair from the dictionary and then individually displayed its key and value using Key and Value property of the KeyValuePair struct which we described earlier.

Apart from getting KeyValuePair by enumerating over the dictionary, you can also get keys and values individually. For instance by calling Keys property of ‘numcoll’ in foreach loop, you can iteratively get all the keys in the dictionary. Similarly, by calling Values property of ‘numcoll’, you can iteratively get all values stored in a dictionary. We have done this in the last two foreach loops where first we got all keys and displayed them on the console output. Then we fetched all values and displayed them on the output screen. The output of the code in Example1 is as follows.

Output1

http://imgs.g4estatic.com/c-sharp/di...es/output1.png

Like most of the other collections, if we specify the size of the dictionary from the outset in the constructor, the performance of the collection can be improved hugely. The non-generic version of dictionary i.e. Hashtable is almost similar to the Dictionary but unlike Dictionary, Hashtable also exposes the non-generic interface.

Coming towards few disadvantages of using Dictionaries and Hashtable; they do not store items in sorted order. Another disadvantage is that the order in which items are stored is also altered and not retained. And lastly, duplicate keys are not allowed in dictionary items, a behavior often undesired.

OrderedDictionary



We mentioned few problems with Dictionary and Hashtable. One of them was that they do not retain the order in which elements are stored. Fortunately enough, we have a non-generic collection that implements dictionary interfaces and retains the order in which elements are stored. This class is called OrderedDictionary. The elements of OrderedDictionary can be can be accessed via an indexer as well as key. OrderedDictionary combines the properties of Hashtable and ArrayList in a way that apart from containing all the properties of a Hashtable, it also contains RemoveAt and other index methods contained by ArrayList collection. For a better understanding of how OrderedDictionary is actually implemented, have a look at our second example of this tutorial.

Example2
Code:

using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Text;
using System.Numerics;

namespace CSharpTutorial
{
    class Program
    {
        public static void Main()
        {
            OrderedDictionary numcoll = new OrderedDictionary();
            numcoll.Add(1, "One"); // Adding KeyValue pairs via Add method
            numcoll.Add(2, "Two"); // Adding KeyValue pairs via Add method
            numcoll.Add(3, "Three");

            Console.WriteLine(numcoll[1]);
            Console.WriteLine("\n***********************\nEnumaritng over OrderedDictionary");

            foreach (DictionaryEntry nums in numcoll)
            {
                Console.WriteLine(nums.Key + " " + nums.Value);
            }

            Console.WriteLine("\n***********************\nEnumaritng over Keys");
            foreach (int keys in numcoll.Keys)
            {
                Console.WriteLine(keys);
            }

            Console.WriteLine("\n***********************\nEnumaritng over Values");
            foreach (string items in numcoll.Values)
            {
                Console.WriteLine(items);
            }

            Console.ReadLine();
        }
    }
}

In our second example we have an OrderedDictionary which we have named ‘numcoll’. We added three key-value pairs in this collection. Like our first example, our keys are integers and our values are strings.

A key difference between OrderedDictionary and Dictionary, other than ordering is in accessing data via index. In Dictionary, index value meant key but in OrderedDictionary, the index value is actual index. Consider following line of code:
Code:

Console.WriteLine(numcoll[1]);
This line of code would not display the value with key 1 i.e. ‘One’. Rather, this line would display the value at the second index i.e. ‘Two’; since indexes start from 0, therefore 1st index would actually contain second value which would be displayed on the screen.

Now come towards the enumeration part. The OrderedDictionary, when enumerated returns DictionaryEntry struct which we explained in the beginning of the article. In the next line of codes in Example2, we have enumerated upon ‘numcoll’ using foreach loop and have displayed the keys and values of each DictionaryEntry in it. Like Dictionary, we can call Keys and Values property to individually get keys and values of an OrderedDictionary. We have done this In the last part of Example2 where first individually displayed keys using foreach loop and then displayed Values using another foreach loop.

The output of the code in Example2 is as follows:

Output2

http://imgs.g4estatic.com/c-sharp/di...es/output2.png

An extremely important thing to note here is that, OrderedDictionary is not a sorted dictionary collection; it only preserves the order of the element in which they are stored. Now let us discuss another important dictionary type.

ListDictionary



ListDictionary is similar to OrderedDictionary and retains the order in which data is stored. A major difference between the ListDictionary and the OrderedDictionary is that ListDictionary stores underlying data in a single linked list. A potential problem with ListDictionary is that performs extremely slow when large amount of data is stored in it. In order to deal with this issue, a variation of ListDictionary is available in .NET framework which is called HybridDictionary which when reaches certain size automatically changes to Hashtable which works comparatively fast as compared to ListDictionary. Both ListDictionary and HybridDictionary only have non-generic versions. To see how ListDictionary is implanted in code, have a look at Example3.

Example3
Code:

using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Text;
using System.Numerics;

namespace CSharpTutorial
{
    class Program
    {
        public static void Main()
        {
            ListDictionary numcoll = new ListDictionary();
            numcoll.Add(1, "One"); // Adding KeyValue pairs via Add method
            numcoll.Add(2, "Two"); // Adding KeyValue pairs via Add method
            numcoll.Add(3, "Three");

            Console.WriteLine(numcoll[1]);
            Console.WriteLine("\n***********************\nEnumaritng over OrderedDictionary");

            foreach (DictionaryEntry nums in numcoll)
            {
                Console.WriteLine(nums.Key + " " + nums.Value);
            }

            Console.WriteLine("\n***********************\nEnumaritng over Keys");
            foreach (int keys in numcoll.Keys)
            {
                Console.WriteLine(keys);
            }

            Console.WriteLine("\n***********************\nEnumaritng over Values");
            foreach (string items in numcoll.Values)
            {
                Console.WriteLine(items);
            }
            Console.ReadLine();
        }
    }
}

The code in Example3 is identical to the one in Example2 but here we have changed the dictionary type. Now we have ListDictionary type dictionary which has been named “numcoll”. You would see that in case of ListDictionary, providing key in the index returns the corresponding value instead of the value at that index. Consider the following line
Code:

Console.WriteLine(numcoll[1]);
This line would display the value stored against the key ‘1’, so, string “One” would be printed on the output screen. Enumerating ListDictionary is similar to OrderedDictionary; DictionaryEntry struct is returned which can be used to get keys and values etc. The output of the code in Example3 would be similar to Example2, except that “One” would be displayed in the beginning when key 1 is specified in the index of the ‘numcoll’ dictionary. The output is as follows.

Output3

http://imgs.g4estatic.com/c-sharp/di...es/output3.png

Sorted Dictionaries



Till now we have been discussing unsorted dictionaries. We have studied ordered dictionary but that is only useful if we want to retain the order of the data in which we insert it. In case we want our items to be sorted on the basis of key, we need some other dictionaries. Sorted dictionaries serve this purpose. We have two major types of sorted dictionaries in .NET framework.
  • SortedDictionary <TKey, TValue>
  • SortedList <TKey, TValue>
SortedDictionary<,> works extremely fast with both insertion as well as retrieval due to the fact that red/black tree is used to implement SortedDictionary<,>. Red/black tree is a data structure that works extremely well both during insertion as well as retrieval. On the other hand, SortedList<,> list works extremely well during retrieval but works poorly during insertion. SortedList<,> internally use ordered array pair.

To see how, SortedDictionary<,> is actually implemented, have a look at our fourth example for this tutorial.

Example4
Code:

using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Text;
using System.Numerics;

namespace CSharpTutorial
{
    class Program
    {
        public static void Main()
        {
            SortedDictionary<int, string> numcoll = new SortedDictionary<int, string>();

            numcoll.Add(3, "Three");
            numcoll.Add(1, "One");
            numcoll.Add(2, "Two");
            numcoll.Add(5, "Five");
            numcoll.Add(4, "Four");
            Console.WriteLine(numcoll[1]);

            Console.WriteLine("\n********************************\nInserting data in unsorted order ....\n");
            Console.WriteLine("3 Three\n1 One\n2 Two\n5 Five\n4 Four");
            Console.WriteLine("\n***********************\nEnumaritng over SortedDictionary");

            foreach (KeyValuePair<int,string> nums in numcoll)
            {
                Console.WriteLine(nums.Key + " " + nums.Value);
            }
            Console.WriteLine("\n***********************\nEnumaritng over Keys");
            foreach (int keys in numcoll.Keys)
            {
                Console.WriteLine(keys);
            }
            Console.WriteLine("\n***********************\nEnumaritng over Values");
            foreach (string items in numcoll.Values)
            {
                Console.WriteLine(items);
            }
            Console.ReadLine();
        }
    }
}

In Example4, we have a SortedDictionary<int, string> ‘numcoll’. We added the data to this dictionary in the order 3, 1,2,5,4. But you would see that when you enumerate upon this dictionary, the data displayed would be in sorted order. The output of the code in Example4

Output4

http://imgs.g4estatic.com/c-sharp/di...es/output4.png

In the same way, SortedList<,> can be implemented to sort data in the dictionary. Our next example replaces the SortedDictionary<,> in Example4 with SortedList<,> . Have a look at the last example of this tutorial.

Example5

Code:

using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Text;
using System.Numerics;

namespace CSharpTutorial
{
    class Program
    {
        public static void Main()
        {
            SortedList<int, string> numcoll = new SortedList<int, string>();

            numcoll.Add(3, "Three");
            numcoll.Add(1, "One");
            numcoll.Add(2, "Two");
            numcoll.Add(5, "Five");
            numcoll.Add(4, "Four");

            Console.WriteLine(numcoll[1]);
            Console.WriteLine("\n********************************\nInserting data in unsorted order ....\n");
            Console.WriteLine("3 Three\n1 One\n2 Two\n5 Five\n4 Four");
            Console.WriteLine("\n***********************\nEnumaritng over SortedList");

            foreach (KeyValuePair<int,string> nums in numcoll)
            {
                Console.WriteLine(nums.Key + " " + nums.Value);
            }

            Console.WriteLine("\n***********************\nEnumaritng over Keys");
            foreach (int keys in numcoll.Keys)
            {
                Console.WriteLine(keys);
            }

            Console.WriteLine("\n***********************\nEnumaritng over Values");
            foreach (string items in numcoll.Values)
            {
                Console.WriteLine(items);
            }

            Console.ReadLine();
        }
    }
}

The code in Example5 is same as in Example4, with the only difference that we have substituted SortedDictionary<,> with SortedList<,>. The items are inserted in unsorted ordered but when you enumerate them, they will appear in sorted order based on the key. An important thing to note here is that, during enumeration, both SortedDictionary<,> and SortedList <,> return KeyValuePair<,>. The output of Example5 is identical to Example4.

This was the last article on collections in C#. I have explained almost all the important collections that can be used to store collection of items. I have also explained the scenarios in which these collections can be used. I strongly recommend you to explore System.Collections, System.Collections.Generics and System.Collections.Specialized namespaces and implement all the collections yourself in your code. Keep visiting this site; we are heading towards another exciting feature of C#, the LINQ.


All times are GMT +5.5. The time now is 21:36.