C# Dictionary
Published: 2023-01-10 17:30:11

## Introduction
As I have progressed in my quest to improve my skills in both programming and coding over the past year (I started with virtually no programming experience approximately 1 year ago in January 2022 at a coding bootcamp), I have tried to learn whatever I can about different facets of programming languages. Recently, I switched to C#, and this is my second summary of a topic related to this language. I hope it provides some useful information to some. Here is a short description of the C# dictionary.

## What is a dictionary?

A C# dictionary is a generic collection of key/value pairs. The syntax for a dictionary is as follows: 

`Dictionary<TKey,TValue>`

TKey refers to the key of the object; TValue refers to the value, which the key is mapped to. Between the two, only the value can be null if it is a reference type. The key must also be unique as duplicate keys will throw an exception.

As stated above, this object is generic and defined within the System.Collections.Generic namespace. It is also dynamic, so it is able to grow, depending on the needs of the user, unlike a C# array, which is fixed in size. 

One difference between this object and the C# hashtable is that the hashtable is non-generic and is defined under the System.Collections namespace. See the references section for more on the C# hashtable. 

## Why is a dictionary important?

The dictionary is a useful way to minimize runtime complexity, as this object will usually run near O(1) constant time for retrieval (ContainsKey() method), insertion (Add() method), and deletion (Remove() method) of a value. 

When I say "near" (i.e. near O(1)) I mean that the complexity is not exactly, but is close enough to that value (O(1)) that it may safely be referred to that value (O(1)). On a graph showing input on the x-axis and runtime on the y-axis, a value near O(1) runtime would be much closer to the O(1) slope than it would be to the slopes of the next most common values (i.e. O(log n) or O(n)).

Exceptions:
1. If the Count property of the dictionary exceeds the dictionary's capacity when using the Add() method, the capacity must be reset, causing the key/value pairs within the dictionary to be reallocated. This causes an O(n) runtime for Add() in this scenario.
2. If you need to retrieve a specific value within the dictionary (ContainsValue() method), this performs a linear search and has an O(n) time complexity.

![Big O Time Complexity Graph](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/m8ynv9td4f9omd8341ye.png)
Figure One: A graph displaying general trends of the Big O time complexities of the following: constant time (O(1)), logarithmic time (O(log n)), linear time (O(n)), and quadratic time (O(n^2)).
 
## When to use a dictionary

Aside from above, here are a couple uses of a dictionary:

When needing to utilize key/value mappings to store data, dictionaries allow for this advantage over arrays and lists, which use indices. 

If you would like to iterate over an object, use of the foreach() method to look at each key/value pair is possible with dictionaries as well as lists/arrays.

## Example of dictionary use

Below is an example of an implemented dictionary:

```
Dictionary<string,string> definitions = new Dictionary<string,string>();

definitions.Add("hue", "a color or shade");
definitions.Add("HTML", "hypertext markup language");
definitions.Add("chilly", "too cold to be comfortable");
definitions.Add("barrier", "an obstacle that prevents movement or access")
```

The above code implements a dictionary that begins as an empty object. After each subsequent Dictionary<string,string>.Add() method, a key with a word is added with a mapped value of its definition (i.e. "hue" mapping to "a color or shade").

## Dictionary hierarchy

The following are the interface implementations of the dictionary:

- `IReadOnlyDictionary<TKey,TValue>`

- `IDictionary<TKey,TValue>`

- `IReadOnlyCollection<KeyValuePair<TKey,TValue>>`

- `IDictionary`

## Summary/Conclusions
I hope this short review of C# dictionaries provided some value to you. I will be covering dictionaries more in depth in the future, but I wanted to start with this superficial summary. Thank you for reading.

Below is a list of what I covered:

- Dictionaries are generic collections used to store key/value pairs.

- Dictionaries can be added to, removed from, counted, etc, with minimal runtime complexity.

- Dictionaries have many advantages over lists/arrays, though each of these objects has its own optimal uses.

- Dictionaries are similar to but not identical to hashtables in C#.

## References and Further Reading

[Dictionary<Tkey,Tvalue> Class: Microsoft](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.dictionary-2?view=net-7.0)

[C# Dictionary With Examples: GeeksForGeeks](https://www.geeksforgeeks.org/c-sharp-dictionary-with-examples/)

[C# Hashtable With Examples: Geeksforgeeks](https://www.geeksforgeeks.org/c-sharp-hashtable-with-examples/)

[What is the Complexity of These Dictionary Methods: Stack Overflow](https://stackoverflow.com/questions/7532678/what-is-the-complexity-of-these-dictionary-methods)

[Big O Time Complexity Graph Reference(figure 1)](https://levelup.gitconnected.com/big-o-time-complexity-what-it-is-and-why-it-matters-for-your-code-6c08dd97ad59)

[Dictionary Add Method With Examples: Microsoft](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.dictionary-2.add?redirectedfrom=MSDN&view=net-7.0#System_Collections_Generic_Dictionary_2_Add__0__1_)

[Dictionary Count Method: Microsoft](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.dictionary-2.count?view=net-7.0)

[Dictionary ContainsKey Method: Microsoft](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.dictionary-2.containskey?redirectedfrom=MSDN&view=net-7.0#System_Collections_Generic_Dictionary_2_ContainsKey__0_)

[Dictionary ContainsValue Method: Microsoft](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.dictionary-2.containsvalue?view=net-7.0)

[Dictionary Remove Method: GeeksForGeeks](https://www.geeksforgeeks.org/c-sharp-dictionary-remove-method/)

[Dictionary Remove Method: Microsoft](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.dictionary-2.remove?view=net-7.0)

[KeyValuePair<TKey,TValue> Struct: Microsoft](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.keyvaluepair-2?view=net-7.0)

[Different Ways to Add to a Dictionary: Stack Overflow](https://stackoverflow.com/questions/1838476/different-ways-of-adding-to-dictionary)