Dictionary Implementation in C#

Now, Dictionary<TKey,TValue> is the basic implementation of IDictionary<TKey,TValue>. Before implementing Dictionary, let's see the following code. 

The following is very straight forward code of a collection printing a month's name and its short form.

  1. using System.Collections;    
  2. using System.Collections.Generic;    
  3. using System.Collections.ObjectModel;    
  4. using System.Linq;    
  5. using System;    
  6.     
  7. namespace Collections    
  8. {    
  9.     internal class Dictionary    
  10.     {    
  11.         private static void Main(string[] args)    
  12.         {    
  13.     
  14.             var months = new List<Months>    
  15.             {    
  16.                 new Months("Jan","January"),    
  17.                 new Months("Feb","February"),    
  18.                 new Months("Mar","March"),    
  19.             };    
  20.                 
  21.             foreach (var month in months)    
  22.             {    
  23.                 //This will invoke Overrided ToString() method    
  24.                 Console.WriteLine(month);    
  25.             }    
  26.             Console.ReadLine();    
  27.         }    
  28.     
  29.             
  30.     
  31.     }    
  32.     
  33.     public class Months    
  34.     {    
  35.         public string monthName { getset; }    
  36.         public string monthShort { getset; }    
  37.     
  38.         public Months(string monthshort, string monthname)    
  39.         {    
  40.             this.monthName = monthname;    
  41.             this.monthShort = monthshort;    
  42.         }    
  43.     
  44.         public override string ToString()    
  45.         {    
  46.             return string.Format("Short Name:{0},Month Name:{1}", monthShort,monthName);    
  47.         }    
  48.     }    
  49.     
  50. }   
see result

However, in the that snippet I have used List<T>. If I need to use a Dictionary then at that point I need to decide one item that can be treated as the key. In the following, I have made the same code as the Dictionary implementation.
  1. using System.Collections;    
  2. using System.Collections.Generic;    
  3. using System.Collections.ObjectModel;    
  4. using System.Linq;    
  5. using System;    
  6.     
  7. namespace Collections    
  8. {    
  9.     internal class Dictionary    
  10.     {    
  11.         private static void Main(string[] args)    
  12.         {    
  13.     
  14.             var months = new Dictionary<string,Months>    
  15.             {    
  16.                 //A,B,C are keys here    
  17.                 {"A",new Months("Jan","January")},    
  18.                 {"B",new Months("Feb","February")},    
  19.                 {"C",new Months("Mar","March")},    
  20.                    
  21.             };    
  22.                 
  23.             foreach (var month in months)    
  24.             {    
  25.                 //This will invoke Overrided ToString() method    
  26.                 Console.WriteLine(month);    
  27.             }    
  28.             Console.ReadLine();    
  29.         }    
  30.     
  31.             
  32.     
  33.     }    
  34.     
  35.     public class Months    
  36.     {    
  37.         public string monthName { getset; }    
  38.         public string monthShort { getset; }    
  39.     
  40.         public Months(string monthshort, string monthname)    
  41.         {    
  42.             this.monthName = monthname;    
  43.             this.monthShort = monthshort;    
  44.         }    
  45.     
  46.         public override string ToString()    
  47.         {    
  48.             return string.Format("Short Name:{0},Month Name:{1}", monthShort,monthName);    
  49.         }    
  50.     }    
  51.     
  52. }   
Now, when I see the output of this, it will print both the key and value (of the pair) in the [] brackets.

command prompt

Now, if I hover on the var keyword in the foreach() loop, I will learn that var is converted to a name and value pair, hence it is output.

output the same

However, I can get the same result with:
  1. foreach (KeyValuePair<string,Months>month in months)   
  2. {   
  3.    //This will invoke Overrided ToString() method   
  4.    Console.WriteLine(month);   
  5. }   
But, this is fairly less readable, hence using the var keyword lets the compiler figure-out what type it will be. However, I can use any of the APIs if I want to be specific as shown below.

foreach
  1. foreach (var month in months.Values)   
  2. {   
  3.    //This will invoke Overrided ToString() method   
  4.    Console.WriteLine(month);   
  5. }   
And this will return only the values as shown below.

cmd

I can do the same thing for keys as well. 

Now, when I need to look up any item in the dictionary then the code will be something like shown below.
  1. //LookUp code   
  2. var march = months["C"];   
  3. Console.WriteLine(march);   
console

However, this code holds true because I know the key because I have written that. How about the dictionary that somebody gave you and you are not sure about the key? For example in the following, it will throw the Key not found exception.
  1. //LookUp code   
  2. var march = months["D"];   
  3. Console.WriteLine(march);   
exception

For this kind of scenario, we use the following snippet. Here, TryGetValue() will look for the key and return the output in a month variable and based on that you can go ahead and print your value.
  1. //Safe LookUp code   
  2. Months month;   
  3.   
  4. bool found = months.TryGetValue("D"out month);   
  5. if (found)   
  6. {   
  7.    Console.WriteLine(month);   
  8. }   
  9. else   
  10. {   
  11.    Console.WriteLine("Key not found");   
  12. }   
key not found

I can also modify the existing element based on the key as shown in the following snippet. This also proves the point that for a given key, only one value can exist in the dictionary.
  1. months["C"]=new Months("Apr","April");   
  2.   
  3. foreach (var month in months.Values)   
  4. {   
  5.    //This will invoke Overrided ToString() method   
  6.    Console.WriteLine(month);   
  7. }   
result

Now, let's consider the scenario that you tried printing the value of <strong>b</strong>. However, in the Dictionary I have the same with <strong>B</strong>. In that case, what will happen? It will return that the Key was not found. Now, to fix that, Dictionary also provides an option to compare the key before fetching. This option comes with the interface <strong>IEqualityComparer<T></strong>. However, there is already a built-in string comparer class that compares the string. So, with the following signature it will fetch the value exactly the same.
  1. using System.Collections;    
  2. using System.Collections.Generic;    
  3. using System.Collections.ObjectModel;    
  4. using System.Linq;    
  5. using System;    
  6.     
  7. namespace Collections    
  8. {    
  9.     internal class Dictionary    
  10.     {    
  11.         private static void Main(string[] args)    
  12.         {    
  13.     
  14.             var months = new Dictionary<string,Months>(StringComparer.InvariantCultureIgnoreCase)    
  15.             {    
  16.                 //A,B,C are keys here    
  17.                 {"A",new Months("Jan","January")},    
  18.                 {"B",new Months("Feb","February")},    
  19.                 {"C",new Months("Mar","March")},    
  20.                    
  21.             };    
  22.     
  23.             Console.WriteLine(months["b"]);    
  24.             Console.ReadLine();    
  25.         }    
  26.     
  27.             
  28.     
  29.     }    
  30.     
  31.     public class Months    
  32.     {    
  33.         public string monthName { getset; }    
  34.         public string monthShort { getset; }    
  35.     
  36.         public Months(string monthshort, string monthname)    
  37.         {    
  38.             this.monthName = monthname;    
  39.             this.monthShort = monthshort;    
  40.         }    
  41.     
  42.         public override string ToString()    
  43.         {    
  44.             return string.Format("Short Name:{0},Month Name:{1}", monthShort,monthName);    
  45.         }    
  46.     }    
  47.     
  48. }  
month

However, I can do the same using an interface as well. But before that, let's talk about hash codes that are the underlying technology of Dictionary. Now, the way Dictionary allocates the key inside in the memory is fairly complicated. Let's say, based on some algorithm, they allocate a compartment of memory for a specific Key. Similarly, there can be different compartments for different Keys. However, the same algorithm also repeats the compartment for a different key after reaching the threshold. So, a single compartment can have a specific number of keys. So, if you compare the performance of Dictionary with other collections like List, it is fairly efficient, because based on the key, it will first identify which compartment I need to look for to fetch the value. 

Now, the importance of Hashcode is, a Dictionary uses a hashcode to identify the compartment. Every object has a member function GetHashCode(). This function gets the hashcode of the object. The hashcode here is a 32 bit integer. Now, let's see whether the following snippet works.
  1. using System.Collections;    
  2. using System.Collections.Generic;    
  3. using System.Collections.ObjectModel;    
  4. using System.Linq;    
  5. using System;    
  6.     
  7. namespace Collections    
  8. {    
  9.     internal class Dictionary    
  10.     {    
  11.         private static void Main(string[] args)    
  12.         {    
  13.     
  14.             var months = new Dictionary<string, Months>(new IgnoreCases())    
  15.             {    
  16.                 //A,B,C are keys here    
  17.                 {"A",new Months("Jan","January")},    
  18.                 {"B",new Months("Feb","February")},    
  19.                 {"C",new Months("Mar","March")},    
  20.                    
  21.             };    
  22.     
  23.             Console.WriteLine(months["b"]);    
  24.             Console.ReadLine();    
  25.         }    
  26.     
  27.             
  28.     
  29.     }    
  30.     
  31.     public class Months    
  32.     {    
  33.         public string monthName { getset; }    
  34.         public string monthShort { getset; }    
  35.     
  36.         public Months(string monthshort, string monthname)    
  37.         {    
  38.             this.monthName = monthname;    
  39.             this.monthShort = monthshort;    
  40.         }    
  41.     
  42.         public override string ToString()    
  43.         {    
  44.             return string.Format("Short Name:{0},Month Name:{1}", monthShort,monthName);    
  45.         }    
  46.     }    
  47.     
  48.     public class IgnoreCases : IEqualityComparer<string>    
  49.     {    
  50.     
  51.         public bool Equals(string x, string y)    
  52.         {    
  53.             return x.ToUpper() == y.ToUpper();    
  54.         }    
  55.     
  56.         public int GetHashCode(string obj)    
  57.         {    
  58.             return obj.GetHashCode();    
  59.         }    
  60.     }    
  61.     
  62. }  
code

Now, this failed for a valid reason. So, "b".GetHashCode()!= "B".GetHashCode() because they are not the same string. Since b actually doesn't exist, there is no question of getting the same hash code for that. Now, the easiest fix around that is to redirect the hashCode to fetch the orignal one like this:
  1. //Redirected to the original hash code   
  2. public int GetHashCode(string obj)   
  3. {   
  4.    return obj.ToUpper().GetHashCode();   
  5. }   
sort name

Now, let's consider a scenario where we want to sort the keys. For that I would use SortedList as shown in the following snippet.
  1. using System.Collections;    
  2. using System.Collections.Generic;    
  3. using System.Collections.ObjectModel;    
  4. using System.Linq;    
  5. using System;    
  6.     
  7. namespace Collections    
  8. {    
  9.     internal class Dictionary    
  10.     {    
  11.         private static void Main(string[] args)    
  12.         {    
  13.     
  14.             var months = new SortedList<string, Months>    
  15.             {    
  16.                 //A,B,C are keys here    
  17.                 {"A",new Months("Jan","January")},    
  18.                 {"B",new Months("Feb","February")},    
  19.                 {"C",new Months("Mar","March")},    
  20.                    
  21.             };    
  22.     
  23.     
  24.             foreach (var month in months.Values)    
  25.             {    
  26.                 //This will invoke Overrided ToString() method    
  27.                 Console.WriteLine(month);    
  28.             }    
  29.             Console.ReadLine();    
  30.         }    
  31.     
  32.             
  33.     
  34.     }    
  35.     
  36.     public class Months    
  37.     {    
  38.         public string monthName { getset; }    
  39.         public string monthShort { getset; }    
  40.     
  41.         public Months(string monthshort, string monthname)    
  42.         {    
  43.             this.monthName = monthname;    
  44.             this.monthShort = monthshort;    
  45.         }    
  46.     
  47.         public override string ToString()    
  48.         {    
  49.             return string.Format("Short Name:{0},Month Name:{1}", monthShort,monthName);    
  50.         }    
  51.     }    
  52.     
  53.     
  54. }   
And similarly, I can make the dictionary as a readonlydictionary.
  1. using System.Collections;    
  2. using System.Collections.Generic;    
  3. using System.Collections.ObjectModel;    
  4. using System.Linq;    
  5. using System;    
  6.     
  7. namespace Collections    
  8. {    
  9.     internal class Dictionary    
  10.     {    
  11.         private static void Main(string[] args)    
  12.         {    
  13.     
  14.             var months = new Dictionary<string, Months>    
  15.             {    
  16.                 //A,B,C are keys here    
  17.                 {"A",new Months("Jan","January")},    
  18.                 {"B",new Months("Feb","February")},    
  19.                 {"C",new Months("Mar","March")},    
  20.                    
  21.             };    
  22.     
  23.             var readonlyMonths = new ReadOnlyDictionary<string, Months>(months);    
  24.             foreach (var month in months.Values)    
  25.             {    
  26.                 //This will invoke Overrided ToString() method    
  27.                 Console.WriteLine(month);    
  28.             }    
  29.             Console.ReadLine();    
  30.         }    
  31.     
  32.             
  33.     
  34.     }    
  35.     
  36.     public class Months    
  37.     {    
  38.         public string monthName { getset; }    
  39.         public string monthShort { getset; }    
  40.     
  41.         public Months(string monthshort, string monthname)    
  42.         {    
  43.             this.monthName = monthname;    
  44.             this.monthShort = monthshort;    
  45.         }    
  46.     
  47.         public override string ToString()    
  48.         {    
  49.             return string.Format("Short Name:{0},Month Name:{1}", monthShort,monthName);    
  50.         }    
  51.     }    
  52.     
  53.         
  54. }   
However, any attempt to modify the dictionary will give an error here.
  1. readonlyMonths.Add("D",new Months("Apr","April"));   
error

This was all about Dictionary. Thanks for joining me.

Thanks,
Rahul.
Happy Coding.

Up Next
    Ebook Download
    View all
    Learn
    View all