Hash Maps in C#

Hash Tables, better known as Hash Maps, are just collections of key-value pairs. In other words, they are pieces of data (values) mapped to unique identifiers called properties (keys).

Hash Maps were designed to give us a way of, given a key, associating a value with it for very quick lookups.

In C#, the Hash Map is implemented as a Dictionary

Creation:

You create an empty Hash Map by declaring a Dictionary<keyType, valueType> and initializing it with new Dictionary<keyType, valueType>(), where the keyType and valueType are the data types of the keys and values.

Let's declare a Hash Map that maps text values representing digits to their numerical value (e.g. "two" => 2). We will map strings to integers, so the two types are string and int. We will name the map digitValue

Dictionary<string, int> digitValue = new Dictionary<string, int>();

Creating an empty dictionary takes O(1) time.

Initialization:

You can also add some key-value pairs in your dictionary at creation:

Dictionary<string, int> digitValue = new Dictionary<string, int> {
    {"zero", 0},
    {"one", 1}
};

Accessing values:

A value is retrieved from a map using the index operator []:

Dictionary<string, int> digitValue = new Dictionary<string, int> {
    {"zero", 0},
    {"one", 1}
};

// Accesing values:
int a = digitValue["zero"]; // a is 0

int b = digitValue["one"]; // b is 1

int c = digitValue["three"]; // throws KeyNotFoundException since 'three' does not exist

int d = digitValue.GetValueOrDefault("three", 0); // d is 0, the default value

As you can see, if you refer to a key that is not in the map, C# throws a KeyNotFoundException. We can use GetValueOrDefault to specify a default value in case it does not exist

Accessing a value from a map takes O(1) time.

Adding an entry:

We can add a key / value pair by assigning with the index operator as follows:

Dictionary<string, int> digitValue = new Dictionary<string, int> {
    {"zero", 0},
    {"one", 1}
};

// Adding new entries:
digitValue["three"] = 3;

//The new Hash Map:
// {
//	"zero": 0,
//  "one":  1,
//	"three": 3
//}

Adding a new entry to a map takes O(1) time.

Updating an entry:

We can update an existing entry by assigning with the index operator as follows:

Dictionary<string, int> digitValue = new Dictionary<string, int> {
    {"zero", 0},
    {"one", 1}
};

// updating entries:
digitValue["zero"] = 5;

//the new hash map:
// {
//	"zero": 5,
//  "one":  1
//}

Updating an entry from a map takes O(1) time.

Deleting entries:

The Remove() method allows you to remove a key from a map:

Dictionary<string, int> digitValue = new Dictionary<string, int> {
    {"zero", 0},
    {"one", 1}
};

// removing entries:
digitValue.Remove("zero");

//the new hash map:
// {
//  "one":  1
//}

If you try to delete a key that is not in the map, it won't do anything.

Deleting an entry from a map takes O(1) time.

Checking if a key exists:

You can check if a key exists in a map using the ContainsKey() method:

Dictionary<string, int> digitValue = new Dictionary<string, int> {
    {"zero", 0},
    {"one", 1}
};


digitValue.ContainsKey("zero"); // returns true since the key exists

digitValue.ContainsKey("three"); // returns false since the key does not exist

Checking if a key exists in the map is O(1) time.

Iterating over the map keys:

If we want to iterate over keys of the map, we can use the foreach loop along with the Keys property as follows:

Dictionary<string, int> digitValue = new Dictionary<string, int> {
    {"zero", 0},
    {"one", 1}
};

foreach (string key in digitValue.Keys) {
    Console.WriteLine(key + " is " + digitValue[key]);
}

// This will print:
// zero is 0
// one is 1

Notice the order: a Dictionary does not guarantee any particular order. In practice you often see insertion order, but don't rely on it.

Iterating over a dictionary takes O(n) time.

Assignment
Follow the Coding Tutorial and let's play with some dictionaries.

Hint
Look at the examples above if you get stuck.