SortedDictionary in C#

Sorted Dictionary in C#

SortedDictionary in C# is useful in C# if you want to sort the elements based on the key. 

Some important points to consider:

• Keys are always sorted. 
• SortedDictionary is a binary search tree with O(log n) retrieval time.
• It is used when you need faster insertion and removal. 
• Keys are always sorted in Ascending order.

Some of the functionalities are common among Dictionary and Sorted Dictionary:

• Add() - To add key-value pair. 
• Example: Add(100, "Test");
• Clear() - Removes all the keys from the SortedDictionary.
• Remove(TKey) - To remove the specified key from the SortedDictionary.
• ContainsKey(TKey) - To check if there is an element in the SortedDictionary with the specified value.
• ContainsValue(TValue)- To check if there is an element in the dictionary with the specified value.

Disadvantages : 

• SortedDictionary has a slower retrieval time ( O(log n)) compared to Dictionary which has O(1)- Constant retrieval time.
• Dictionary is implemented as a HashTable where as a SortedDictionary is a binary search tree.

Use cases :

     My recommendation would be to use this SortedDictionary if you have a small collection of  items. Based on the below analysis, we see that the SortedDictionary works well with smaller list        of elements. 

     

         For 100 Records -> 2ms when using Dictionary -> 0ms when using SortedDictionary.
         For 100000 Records -> 80ms when using Dictionary -> 370ms when using SortedDictionary.

         The below code when run in C#

             

            var sortedDictionary = new SortedDictionary();

            var stopwatch = new Stopwatch();

            stopwatch.Start();

            for (int i = 0; i < 10; i++)

            {

                sortedDictionary.Add(Guid.NewGuid().ToString(), i);

            }

            stopwatch.Stop();

            Console.WriteLine("Sorted Dictionary={0}", stopwatch.ElapsedMilliseconds.ToString());

            Console.WriteLine(stopwatch.ElapsedMilliseconds);

            var list = new Dictionary();

            stopwatch = new Stopwatch();

            stopwatch.Start();

            for (int i = 0; i < 10; i++)

            {

                list.Add(Guid.NewGuid().ToString(), i);

            }

            var temp = list.OrderBy(t=> t.Key);

            stopwatch.Stop();

            Console.WriteLine("Dictionary={0}", stopwatch.ElapsedMilliseconds.ToString());

            Console.ReadKey();