# C++ HashMaps

## Introduction

In C programming, since there is no advanced data structure, to use hash table or hashmap, we would have to implement them by ourselves. In C++ programming, fortunately, there are standard containers or abstractions, such as std::unordered_map and std::unordered_set, that have been implemented for us.

In this blog post, I would like to discuss std::unordered_map, std::unordered_set, and some of the caveats.

## HashMaps

### Unordered Map

std::unordered_map is very like Python’s dict except that the type of key and value in std::unordered_map have to be uniform for all the keys and values, respectively.

### Unordered Set

Sometimes, we would like to only care about the keys and the values are useless. Instead of putting a dummy value into std::unordered_map, we would just use std::unordered_set. Its usages are also similar to std::unordered_map.

### Unhashable Types

To use std::unordered_map, and std::unordered_set, the key type has to be hashable by std::hash<Key>. What if the key type is unhashable?

According to the definition of the std::unordered_map, we could implement our own hash class for Hash in replace of the default std::hash<Key> in the template.

For example, std::tuple<int, std::string> is not supported by std::hash, so we implemented a functor CustomHash to hash the variables of this specific type.

### Caveats

The usages of std::map the same as std::unordered_map. Simply replacing unordered_map to map in the last example would work. What’s different from std::unordered_map is that std::map preserves the order of the keys and it uses tree data structure instead of using hash. So it is not useful for latency demanding queries. In principle, we should not consider std::map as a hashmap.

### Average Complexities

Search Insert Delete
std::unordered_map O(1) O(1) O(1)
std::map O(log n) O(log n) O(log n)
std::unordered_set O(1) O(1) O(1)

## Conclusions

Making good use of std::unordered_map and std::unordered_set would make your development in C++ much more efficient.

Lei Mao

02-15-2020

02-15-2020