Object Oriented Programming and C#: Dictionaries/Hash Tables

A “dictionary” in C# is a ADT (Abstract data type) that maps “keys” to “values”. Normally with an array, the values within this collection of data are accessed using indexing. For the dictionary, instead of indexes there are keys. Another name for a dictionary is a “hash table”, although the distinction can be made in the sense that the hash table is a non-generic type and the dictionary is of generic type. The namespace required for dictionaries is the “System.Collections.Generics” namespace.

The dictionary is initialized much like a list (dynamic array), however the dictionary take two parameters (“TKey”,”TValue”). The first is the data type of the key and the second the data type of the value. Similarly to dynamic arrays, values can be added to the dictionary using a “Add(key,value)” command. Similarly, a value can be deleted using the “Delete(key)” command. However it is important to note that keys do not have to be integers, unlike an index. They can be of any data type imaginable. However, a dictionary cannot contain duplicate keys.

The functionality of a dictionary in C# is similar to a physical dictionary. A dictionary contains words and their definitions and analogously, a programming dictionary maps a key (word) to a value (definition).

The following program illustrates adding values to a dictionary. The key is of type integer and the value of type string. The values “one”, “two” and “three” are added with corresponding integer keys.

1

Much like with arrays, a “foreach” statement can be used to iterate over all the values of a dictionary.

2

It is important to note for a hash table, the relationship between the key and its value as that this must be one to one. When different keys have the same hash value, a “collision” occurs. In order to resolve the collision, a link list must be created in order to chain elements to a single location.

An important concept with hash table: speed of processing does not depend on size. For arrays, in order to find a specific value a linear search must be performed. This takes a long time to complete if the array is very long. With a hash table, size does not matter because the hashing function is a constant time. The “ContainsKey()” method can be used to find a specific key without the need for a linear search.

When would you use a dictionary/hash table over a list? Dictionaries can be helpful in instances where indexes have special meaning. A particular use of a dictionary could be to count the words in a text using the “String.Split()” method and adding each word to the dictionary. In this instance, the “foreach” statement could easily be used to iterate over every value and find the number of words. In short, the dictionary maps meaningful keys to values whereas the list simply maps indexes to values.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s