How Generic Dictionary stores data (Custom Dictionary)

Dictionary is powerful data structure to maintain data in key value pairs. Due to this key value pair dictionary becomes quite useful in coding. Developer can fetch only the data which is corresponding to a specific key.

A dictionary can have duplicate record, but key must be unique.

How dictionary maintain data and how it performs operation?

A dictionary uses linked lists to maintain data. Consider you are using a generic dictionary<string, ‘AnyType’>. Dictionary sorts and search data based on the key, now will it sort data if key is string type, for obvious reasons sorting and searching on string will be quite slow as compared to int or other enum types.

So, how does dictionary perform these operations so quickly?

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

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. 
   
4. public class Node<T>  
5.   
6. {  
7.   
8. public T data;  
9.   
10. public Node(T data)  
11.   
12. {  
13.   
14. this.data = data;  
15.   
16. }  
17.   
18. }  
19.   
20. }  

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

1. namespace Generic  
2.   
3. {  
4.   
5. public class HashNodeMap<T>  
6.   
7. {  
8.   
9. public int key;  
10.   
11. public Node<T> data;  
12.   
13. public HashNodeMap<T> next;  
14.   
15. }  
16.   
17. }  

Above, key will be used to store hash code of each key, node will store the actual data and next will help us link the new item

1. namespace Generic  
2.   
3. {  
4.   
5. public class GenericHashDictionary<Tkey,Tdata>  
6.   
7. {  
8.   
9. public HashNodeMap<Tdata> hashNode = null;  
10.   
11. public int Count;  
12.   
13. public object this[Tkey s]  
14.   
15. {  
16.   
17. get  
18.   
19. {  
20.   
21. return FindHashCode(s).data;  
22.   
23. }  
24.   
25. set  
26.   
27. {  
28.   
29. // You logic to update the item found  
30.   
31. // Ex- hashNode[“key”] = ‘AnyType’;  
32.   
33. }  
34.   
35. }  
36.   
37. // Generic method to create new node every time an item is added in custom dictionary  
38.   
39. private HashNodeMap<Tdata> CreateNode(Tkey key, Tdata data)  
40.   
41. {  
42.   
43. int hashCode = key.GetHashCode();  
44.   
45. HashNodeMap<Tdata> newNodeMap = new HashNodeMap<Tdata>();  
46.   
47. newNodeMap.data = new Node<Tdata>(data);  
48.   
49. newNodeMap.key = hashCode;  
50.   
51. return newNodeMap;  
52.   
53. }  
54.   
55. // Method to add new item in custom dictionary  
56.   
57. public void Add(Tkey key, Tdata data)  
58.   
59. {  
60.   
61. HashNodeMap<Tdata> current = null;  
62.   
63. if (hashNode == null)  
64.   
65. {  
66.   
67. hashNode = CreateNode(key, data);  
68.   
69. }  
70.   
71. else  
72.   
73. {  
74.   
75. current = hashNode;  
76.   
77. while (current.next != null)  
78.   
79. {  
80.   
81. current = current.next;  
82.   
83. }  
84.   
85. current.next = CreateNode(key, data);  
86.   
87. }  
88.   
89. Count++;  
90.   
91. }  
92.   
93.   
94. private Node<Tdata> FindHashCode(Tkey key)  
95.   
96. {  
97.   
98. Node<Tdata> data = null;  
99.   
100. int hashCode = key.GetHashCode();  
101.   
102. HashNodeMap<Tdata> current = hashNode;  
103.   
104. while (current != null)  
105.   
106. {  
107.   
108. if (current.key == hashCode)  
109.   
110. {  
111.   
112. data = current.data;  
113.   
114. break;  
115.   
116. }  
117.   
118. if (current.next != null)  
119.   
120. {  
121.   
122. current = current.next;  
123.   
124. }  
125.   
126. }  
127.   
128. return data;  
129.   
130. }  
131.   
132. }  
133.   
134. }  

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 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 helpfull

Thanks