Post
Ask Question

How Generic Dictionary Stores Data (Custom Dictionary)

How does a dictionary maintain data?

A dictionary uses linked lists to data. Consider you are using a generic dictionary<string, ‘AnyType’>. A dictionary sorts and searches data based on the key which will be difficult to sort on string type. 

How does dictionary perform these operations so quickly?

Well, quite simple. It uses a hash code. Dictionary converts the key value into its corresponding hash code and stores only that hash code. Now searching and sorting on hash code becomes faster.

How does it do it, practically?

Just like linked list, let’s create a Node class. To understand following code better, I would say please go and watch how linked list is implemented here

  1. namespace Generic  
  2. {  
  3.     public class Node<T>  
  4.     {  
  5.         public T data;  
  6.         public Node(T data)  
  7.         {  
  8.             this.data = data;  
  9.         }  
  10.     }  
  11. }

Now to maintain a key value pair and to link the objects, we need to create another class.

  1. namespace Generic  
  2. {  
  3.     public class HashNodeMap<T>  
  4.     {  
  5.         public int key;  
  6.         public Node<T> data;  
  7.         public HashNodeMap<T> next;  
  8.     }  
  9. }  
Above, a key is used to store hash code of each key, a node stores actual data. The next step will help us link the new item.
  1. public class GenericHashDictionary<Tkey,Tdata>    
  2.     {    
  3.         public HashNodeMap<Tdata> hashNode = null;    
  4.         public int Count;    
  5.     
  6.         public object this[Tkey s]    
  7.         {    
  8.             get    
  9.             {    
  10.                 return FindHashCode(s).data;    
  11.             }    
  12.             set    
  13.             {    
  14.     
  15.             }    
  16.         }    
  17.     
  18.         private HashNodeMap<Tdata> CreateNode(Tkey key, Tdata data)    
  19.         {    
  20.             int hashCode = key.GetHashCode();    
  21.             HashNodeMap<Tdata> newNodeMap = new HashNodeMap<Tdata>();    
  22.             newNodeMap.data = new Node<Tdata>(data);    
  23.             newNodeMap.key = hashCode;    
  24.             return newNodeMap;    
  25.         }    
  26.     
  27.         public void Add(Tkey key, Tdata data)    
  28.         {    
  29.             HashNodeMap<Tdata> current = null;    
  30.             if (hashNode == null)    
  31.             {    
  32.                 hashNode = CreateNode(key, data);    
  33.             }    
  34.             else    
  35.             {    
  36.                 current = hashNode;    
  37.                 while (current.next != null)    
  38.                 {    
  39.                     current = current.next;    
  40.                 }    
  41.                 current.next = CreateNode(key, data);    
  42.             }    
  43.             Count++;    
  44.         }    
  45.     
  46.         private Node<Tdata> FindHashCode(Tkey key)    
  47.         {    
  48.             Node<Tdata> data = null;    
  49.             int hashCode = key.GetHashCode();    
  50.             HashNodeMap<Tdata> current = hashNode;    
  51.     
  52.             while (current != null)    
  53.             {    
  54.                 if (current.key == hashCode)    
  55.                 {    
  56.                     data = current.data;    
  57.                     break;    
  58.                 }    
  59.                 if (current.next != null)    
  60.                 {    
  61.                     current = current.next;    
  62.                 }    
  63.             }    
  64.             return data;    
  65.         }    
  66. }    

Above are some basic operation performed in a standard dictionary.

Now time to use this
  1. GenericHashDictionary<string, string> hdt = new GenericHashDictionary<string, string>();  
  2. hdt.Add("userName", "ishoo");  
  3. hdt.Add("password", "1234");  
  4. hdt.Add("email", "ishooagarwal");  
 
As you can see the (-ve) numbers these are keys which I had used. 
 
I am still developing this data structure and implementing various things in it. Currently I am implementing IEnumerable and IEnumerator so that foreach loop can be performed on this custom dictionary. 
 
In my next blog I will show you how to to sort remove and iterate through the custom dictionary.
 
Hope you enjoy it and find it helpful.