How to Use HashMap in C++

1. Use HashMap With std::map in C++
2. Use HashMap With std::unordered_map in C++
3. Key Differences and When to Use Each Map in C++

The HashMap is a vital data structure containing key-value pairs where a value can be retrieved using the relevant key. Every key is mapped to one particular value in a HashMap.

Using keys during iterations, we can access the corresponding values much faster. Hence, the HashMap is considered an efficient and essential data structure when retrieving values, with both key and value of any type.

Before C++ 11, a standard-defined hash table was not present in the standard library of C++, but somewhat different implementors had non-standard variants of the hash table, often called HashMap. Along with C++ 11, a standard implementation of the hash table was added to the standard library.

Still, due to having various variations of the hash table as HashMap from different libraries, it was decided to use a separate name to call the new implementation to avoid confusion.

Therefore, in C++, std::unordered_map is the alternate name for the HashMap, but another map uses the key-value pair concept, the std::map.

There are key differences between std::unordered_map and std::map. As the name suggests, the elements inside the std::unordered_map are unordered while the elements in the std::map are ordered.

Use HashMap With std::map in C++

std::map belongs to the category of associative containers where the elements are stored in mapped key-value pairs. In std::map and std::unordered_map, the key should always be unique, but there can be several unique keys where the mapped value is similar.

The std::map is implemented using Self-Balancing Binary Search Tree (AVL tree/ Red-black tree). The main feature of BST (Self-Balancing Binary Search Tree) is that the height is always automatically kept to a minimum when insertion and deletion of elements happen.

In std::map, the average time complexity depends logarithmically on the number of elements being stored; therefore, it takes O(log n) time on average for an operation to happen. In O(log n), O refers to the Big O notation, and n refers to the number of elements stored.

Therefore, BSTs are helpful when creating and maintaining ordered lists.

Example:

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main() {
  map<int, string> Players;

  Players.insert(std::pair<int, string>(2, "Lin Dan"));
  Players.insert(std::pair<int, string>(1, "Chen Long"));

  cout << "Number of Players " << Players.size() << endl;
  for (map<int, string>::iterator it = Players.begin(); it != Players.end();
       ++it) {
    cout << (*it).first << ": " << (*it).second << endl;
  }
}

Output:

Number of Players 2
1: Chen Long
2: Lin Dan

Use HashMap With std::unordered_map in C++

std::unordered_map is implemented using the hash table in C++. Hash tables also belong to associative containers. The mapped values are stored in a hash table in an array of buckets or slots, from which necessary values can be retrieved.

This indexing is done using the hash function, hash code. The average time complexity for search, insertion and deletion of a std::unordered_map is O(1), where O is the Big O notation, this is the main reason why the std::unordered_map is very efficient.

Example:

#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
  unordered_map<string, int> info;

  info["Age"] = 18;
  info["Year"] = 2022;
  info["Number of Players"] = 15;

  for (auto x : info) cout << x.first << " " << x.second << endl;
}

Output:

Number of Players 15
Year 2022
Age 18

Key Differences and When to Use Each Map in C++

When std::unordered_map and std::map are compared, the gap in efficiency between the two is huge.

std::unordered_map clearly does have a considerable performance edge over std::map. This is mainly because std::unordered_map can directly address value as they are placed in slots and, therefore, has no order that needs to be preserved.

On the other hand, a std::map has an order that needs to be preserved; therefore, it consumes more time. This efficiency might not be visible for small data sets, but this difference is huge for large data sets.

std::unordered_map can be used when accessing a single element from a data set or keeping a count of elements when no order is required.

std::map also does have a few advantages over the std::unordered_map. Generally, BSTs can be implemented more quickly than a hash table, and we can do this in our preferred way, but for hashing, we need to rely heavily on libraries.

Therefore, std::map can be implemented easily compared to the std::unordered_map. Also, when it comes to sorting, it’s much easier to sort keys in std::map than in std::unordered_map is because inorder traversing is not a natural operation for hash tables but it is for BSTs.

std::map can be used in situations such as printing data in sorted order, where the data needs to be ordered for search queries, order statistics, etc.

Both std::map and std::unordered_map have certain similarities and differences that can be manipulated according to the need of that moment.