What is a hash map in C++?

In computer science, a hash map, often called a hash table, is a common data structure that offers effective key-value pair storing and retrieval. It is an attractive choice for several applications since it provides constant-time complexity for average-case scenarios. In this Answer, we shall examine the C++ hash map idea, its implementation, and its usefulness. For better understanding, we will provide examples from codes and visuals.

Overview of a hash map

A hashmap is an associative container that stores elements in a key-value format. It utilizes a hash function to map keys to indices in an array, known as a bucket. This hashing technique allows for fast retrieval of values based on their associated keys. In C++, hash maps are implemented using the unordered_map container class from the Standard Template Library (STL).

Hash function

The hash function is a crucial component of a hashmap that takes a key as input and returns an index within the range of the hashmap’s underlying array. An ideal hash function should evenly distribute keys across the available indices, reducing collisions (when two keys map to the same index). The unordered_map class in C++ provides a default hash function for primitive types, but custom hash functions can be defined for user-defined types.

Collision resolution

Collisions occur when multiple keys generate the same hash value and map to the same index in the array. Various collision resolution techniques are employed to handle such scenarios. The two primary approaches are chaining and open addressing. Chaining involves creating a linked list at each bucket to store multiple key-value pairs, while open addressing aims to find alternative locations within the hash map to store colliding elements.

Code implementation with unordered map

Let’s explore the implementation of a hash map using C++ and the unordered_map class.

#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
  // Create a hashmap
  unordered_map < int, string > hashmap;
  // Insert key-value pairs
  hashmap.insert({ 1, "Value 1"});
  hashmap.insert({ 2, "Value 2"});
  hashmap.insert({ 3, "Value 3"});
  // Access values using keys
  cout << "Value associated with key 1: " << hashmap[1] << endl;
  cout << "Value associated with key 2: " << hashmap[2] << endl;
  cout << "Value associated with key 3: " << hashmap[3] << endl;
  // Check if a key exists
  if (hashmap.find(4) != hashmap.end()) {
    cout << "Key 4 found!" << endl;
  } else {
    cout << "Key 4 not found!" << endl;
  }
  // Remove a key-value pair
  hashmap.erase(2);
  // Iterate over key-value pairs
  for (const auto & pair: hashmap) {
    cout << "Key: " << pair.first << ", Value: " << pair.second << endl;
  }
  return 0;
}

Code explanation

Line 9: unordered_map is called and hashmap is declared to store key-value pairs. The keys will be of type int, and the values will be of type string.
Line 12–14: These lines insert key-value pairs into the hashmap using the insert() function.
Line 22–26: These lines check if a key, in this case, key 4, exists in the hash map using the find() function. If the key is found, it prints “Key 4 found!” to the console; otherwise, it prints “Key 4 not found!”.
Line 29: It removes the key-value pair with key 2 from the hash map using the erase() function.

#include <iostream>
#include <map>
#include <string>
int main() {
  
    std::map<std::string, int> OrderedMap;
    
    OrderedMap["Squares"] = 10;
    OrderedMap["Circles"] = 5;
    OrderedMap["Triangles"] = 8;
    std::cout << "There are  " << OrderedMap["Squares"] << " Squares"<< std::endl;
    std::cout << "There are  " << OrderedMap["Circles"] << " Circles"<< std::endl;
    std::cout << "There are  " << OrderedMap["Triangles"] << " Triangles"<< std::endl;
    // Iterate over all key-value pairs in the map
    for (const auto& pair : OrderedMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    return 0;
}

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

What is a hash map in C++?

Overview of a hash map

Hash function

Collision resolution

Code implementation with unordered map

Code explanation

Code implementation with ordered map

Code explanation