Dictionary is common data structure which most of developers use to store data for quick access in future. It provides various operation, has good capabilities and has really good time complexity. But, Do you ever wonder how dictionary does all this effortlessly. A common curiosity which every developer should have is how does a dictionary maintains data internally. Well, Answer to this question is rather painless.

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

How does dictionary perform these operations so quickly?

Well, quite elementary. It uses a hash code to sort data. 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

namespace Generic  
{  
    public class Node<T>  
    {  
        public T data;  
        public Node(T data)  
        {  
            this.data = data;  
        }  
    }  
}

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

namespace Generic  
{  
    public class HashNodeMap<T>  
    {  
        public int key;  
        public Node<T> data;  
        public HashNodeMap<T> next;  
    }  
}  

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.

public class GenericHashDictionary<Tkey,Tdata>    
    {    
        public HashNodeMap<Tdata> hashNode = null;    
        public int Count;    
    
        public object this[Tkey s]    
        {    
            get    
            {    
                return FindHashCode(s).data;    
            }    
            set    
            {    
    
            }    
        }    
    
        private HashNodeMap<Tdata> CreateNode(Tkey key, Tdata data)    
        {    
            int hashCode = key.GetHashCode();    
            HashNodeMap<Tdata> newNodeMap = new HashNodeMap<Tdata>();    
            newNodeMap.data = new Node<Tdata>(data);    
            newNodeMap.key = hashCode;    
            return newNodeMap;    
        }    
    
        public void Add(Tkey key, Tdata data)    
        {    
            HashNodeMap<Tdata> current = null;    
            if (hashNode == null)    
            {    
                hashNode = CreateNode(key, data);    
            }    
            else    
            {    
                current = hashNode;    
                while (current.next != null)    
                {    
                    current = current.next;    
                }    
                current.next = CreateNode(key, data);    
            }    
            Count++;    
        }    
    
        private Node<Tdata> FindHashCode(Tkey key)    
        {    
            Node<Tdata> data = null;    
            int hashCode = key.GetHashCode();    
            HashNodeMap<Tdata> current = hashNode;    
    
            while (current != null)    
            {    
                if (current.key == hashCode)    
                {    
                    data = current.data;    
                    break;    
                }    
                if (current.next != null)    
                {    
                    current = current.next;    
                }    
            }    
            return data;    
        }    
}

Above are some basic operation performed in a standard dictionary.

Now time to use this

GenericHashDictionary<string, string> hdt = new GenericHashDictionary<string, string>();  
hdt.Add("userName", "ishoo");  
hdt.Add("password", "1234");  
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.