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 an unordered_map from the Standard Library.

Creation:

You create an empty Hash Map by declaring an unordered_map<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 represing digits to their numerical value (e.g. "two" => 2). We wil map strings to integers, so the two types are string and int. We will name the map digitValue

#include <unordered_map>
#include <string>
using namespace std;

unordered_map<string, int> digitValue;

Creating an empty dictionary takes O(1) time.

Initialization:

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

unordered_map<string, int> digitValue({
	{"zero", 0},
	{"one", 1}
});

Accessing values:

A value is retrieved from a map by specifying its corresponding key in square brackets ([]):

unordered_map<string, int> digitValue({
	{"zero", 0},
	{"one", 1}
});

// Accessing values:
cout << digitValue["zero"]; // prints 0
cout << digitValue["one"]; // prints 1

cout << digitValue["three"]; // prints 0

As you can see, if you refer to a key that is not in the map, C++ returns a default value (0 for numbers, empty string for strings). Also when accessing a non-existing value, it also adds it to the map!

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

Adding an entry:

Adding an entry to an existing map is simply a matter of assigning a new key and value, via the assignment operator:

unordered_map<string, int> digitValue({
	{"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:

If you want to update an entry, you can just assign a new value to an existing key:

unordered_map<string, int> digitValue({
	{"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 erase() method allows you to remove a key from a map:

unordered_map<string, int> digitValue({
	{"zero", 0},
	{"one", 1}
});

// Removing an entry
digitValue.erase("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 count() method:

unordered_map<string, int> digitValue({
	{"zero", 0},
	{"one", 1}
});

cout << digitValue.count("zero"); // prints 1 since the key appears once

cout << digitValue.count("three"); // prints 0 since the key does not exist in the map

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 for loop along with the : operator:

unordered_map<string, int> digitValue({
	{"zero", 0},
	{"one", 1}
});

for (const auto& key : digitValue) {
    cout << key.first << " is " << key.second << endl;
}

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

Notice the order is not the same as initiated. unordered_map keeps the data in random order

Iterating over a dictionary takes O(n) time.

Iterating using both the key and the value for simplicity:

If we want to iterate over both keys and values of the map, we can use the for loop along with the : operator as follows:

unordered_map<string, int> digitValue({
	{"zero", 0},
	{"one", 1}
});

for (const auto& [key, val] : digitValue) {
    cout << key << " is " << val << endl;
}

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

Notice the order is not the same as initiated. unordered_map keeps the data in random order

Iterating over an unordered_map takes O(n) time.

Assignment
Follow the Coding Tutorial and let's practice with unordered_maps.

Hint
Look at the examples above if you get stuck.