Using Dictionaries in .Net – An OverviewWhile using collection of objects, it is not always that the individual elements are accessed sequentially but are also referred or indexed by one single string or number. Elements of the collection may have to be accessed randomly by some key value. The key value which can be of any data type, identifies the element uniquely from the list and allows easy access to the required element.
For example, information regarding a telephone subscriber can be obtained by indexing on his telephone number stored in a dictionary. Dictionary in .Net is designed similar to a real-life dictionary and is aimed to help in such situations where a group of similar items need to be maintained in a collection and each item has to be accessed by a key rather than a numeric index. Dictionary in .Net In .net, Dictionary is a facility provided to store a group of objects of any data type and a ‘key’ value is used to access each of the elements. The dictionary is designed such that its size changes dynamically when its elements are added or removed. As in arrays, the size of the dictionary can be found using the Count property. The type of the dictionary can be specified as fixed size, variable size and read-only. Fixed size implies no addition or removal, variable size allows any modification of the element and addition/removal of the element while the read-only type elements cannot be modified. There are two classes, namely, Hashtable and Dictionary which provide dictionary functionality by implementing the interface, IDictionary. Each of the element (called as DictionaryEntry object) stored in these collections have a key and corresponding value in it. The main difference between Hashtable and Dictionary is that the elements of Hashtable are of Object type while those of Dictionary type are of value type. This is the reason for not using Hashtable for elements that are not of Object type since the overhead in boxing/unboxing necessary for storing/retrieving values can affect performance. Code sample Following is the code to illustrate the usage of dictionary. The example taken is that of a telephone directory in which the telephone number is indexed (key). Hashtable TeleDirectory = new Hashtable(79); //assume subscriberId is the key(of structure type, TeleNo) and subscriberInfo is of structure type, TeleSubscriberInfo consisting of subscriber information TeleNo subscriberId; //add the code for filling the subscriberId and subscriberInfo structure variables with the necessary values and then add it to the hashtable TeleDirectory.Add (subscriberId, subscriberInfo); //To access the same element after adding it, following code is used TeleSubscriberInfo subscriberInfo1 = TeleDirectory[subscriberId]; //To remove the element, following code is used TeleDirectory.Remove[subscriberId]; Design of dictionary in .Net Unlike arrays, the elements of the dictionary are not sequentially placed in the memory. Instead, each element is placed in a bucket based on the hash value of its key. Further access to that element will be based on the key and the search area will be restricted to that specific bucket resulting in a faster access to the element. Although the framework offers the Dictionary class, Dictionary which implements an abstract base class, DictionaryBase to provide dictionary functionality, the most often used dictionary class is HashTable. It is used as an array with some specified size, which is usually a prime number (suited for the internal algorithm). Both the key and the item need to be of type, Object. This makes it to store any types of data within it. The two main methods for implementing the dictionary are GetHashCode() and Equals(). GetHashCode() is the method which gets the hash code used for the location of storing the item. By default, Hashtable provides the implementation of GetHashCode method which does not guarantee the uniqueness or consistency. It is suggested to override this method in the derived class to generate hash code based on a field of the instance of the object and hence derive better performance. Another requirement for generating the hash code is that the generated value should be evenly distributed across the entire range of available values. This is framed for the reason that there is a potential risk of probability of two values of generated hash code to be same and hence a situation of clash. To solve this issue, it is better to specify the maximum load (a parameter while creating the Hashtable to indicate the proportion of the table occupied) as minimum for the hashtable to work more efficiently. Also, it is also suggested to specify the size of the Hashtable object to be a prime number for maximum efficiency due to the internal algorithms used for the working of the dictionary. Equals() is another method that is used to compare two items based on the value of the field that needs to be compared between the different objects in the dictionary. It is a general rule that if one object equals another in a dictionary, both these objects should return the same hash code when GetHashCode() is called. This is also the reason for the C# compiler to throw a warning when only one of the methods is overridden and other is not. System.String is a classical example of the implementation of the dictionary in .Net itself. It is used to compare two strings for which it uses string as key in its dictionary. The two methods, Equals() and GetHashCode() are overridden such that the two String objects having same string contents will return the same hash code. Usage of Dictionaries Dictionaries can be used in the following scenarios: • where
the data of the items to be stored is indexed by the name of the object
|