Dictionary Implementation in C#

Rahul Sahay
9y
28.3k
0
0

Article

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.

using System.Collections;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;
using System;
namespace Collections
{
internal class Dictionary
{
private static void Main(string[] args)
{
var months = new List<Months>
{
new Months("Jan","January"),
new Months("Feb","February"),
new Months("Mar","March"),
};
foreach (var month in months)
{
//This will invoke Overrided ToString() method
Console.WriteLine(month);
}
Console.ReadLine();
}
}
public class Months
{
public string monthName { get; set; }
public string monthShort { get; set; }
public Months(string monthshort, string monthname)
{
this.monthName = monthname;
this.monthShort = monthshort;
}
public override string ToString()
{
return string.Format("Short Name:{0},Month Name:{1}", monthShort,monthName);
}
}
}

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.

using System.Collections;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;
using System;
namespace Collections
{
internal class Dictionary
{
private static void Main(string[] args)
{
var months = new Dictionary<string,Months>
{
//A,B,C are keys here
{"A",new Months("Jan","January")},
{"B",new Months("Feb","February")},
{"C",new Months("Mar","March")},
};
foreach (var month in months)
{
//This will invoke Overrided ToString() method
Console.WriteLine(month);
}
Console.ReadLine();
}
}
public class Months
{
public string monthName { get; set; }
public string monthShort { get; set; }
public Months(string monthshort, string monthname)
{
this.monthName = monthname;
this.monthShort = monthshort;
}
public override string ToString()
{
return string.Format("Short Name:{0},Month Name:{1}", monthShort,monthName);
}
}
}

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:

foreach (KeyValuePair<string,Months>month in months)
{
//This will invoke Overrided ToString() method
Console.WriteLine(month);
}

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

foreach (var month in months.Values)
{
//This will invoke Overrided ToString() method
Console.WriteLine(month);
}

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.

//LookUp code
var march = months["C"];
Console.WriteLine(march);

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.

//LookUp code
var march = months["D"];
Console.WriteLine(march);

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.

//Safe LookUp code
Months month;
bool found = months.TryGetValue("D", out month);
if (found)
{
Console.WriteLine(month);
}
else
{
Console.WriteLine("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.

months["C"]=new Months("Apr","April");
foreach (var month in months.Values)
{
//This will invoke Overrided ToString() method
Console.WriteLine(month);
}

Now, let's consider the scenario that you tried printing the value of b. However, in the Dictionary I have the same with B. 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 IEqualityComparer<T>. 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.

using System.Collections;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;
using System;
namespace Collections
{
internal class Dictionary
{
private static void Main(string[] args)
{
var months = new Dictionary<string,Months>(StringComparer.InvariantCultureIgnoreCase)
{
//A,B,C are keys here
{"A",new Months("Jan","January")},
{"B",new Months("Feb","February")},
{"C",new Months("Mar","March")},
};
Console.WriteLine(months["b"]);
Console.ReadLine();
}
}
public class Months
{
public string monthName { get; set; }
public string monthShort { get; set; }
public Months(string monthshort, string monthname)
{
this.monthName = monthname;
this.monthShort = monthshort;
}
public override string ToString()
{
return string.Format("Short Name:{0},Month Name:{1}", monthShort,monthName);
}
}
}

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.

using System.Collections;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;
using System;
namespace Collections
{
internal class Dictionary
{
private static void Main(string[] args)
{
var months = new Dictionary<string, Months>(new IgnoreCases())
{
//A,B,C are keys here
{"A",new Months("Jan","January")},
{"B",new Months("Feb","February")},
{"C",new Months("Mar","March")},
};
Console.WriteLine(months["b"]);
Console.ReadLine();
}
}
public class Months
{
public string monthName { get; set; }
public string monthShort { get; set; }
public Months(string monthshort, string monthname)
{
this.monthName = monthname;
this.monthShort = monthshort;
}
public override string ToString()
{
return string.Format("Short Name:{0},Month Name:{1}", monthShort,monthName);
}
}
public class IgnoreCases : IEqualityComparer<string>
{
public bool Equals(string x, string y)
{
return x.ToUpper() == y.ToUpper();
}
public int GetHashCode(string obj)
{
return obj.GetHashCode();
}
}
}

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: