hash map in c++

Lussy04

3 min read

·

23-01-2025

1

0

Share

Hash maps, also known as hash tables, are powerful data structures that provide efficient key-value storage and retrieval. They offer average-case constant time complexity for insertion, deletion, and lookup operations, making them ideal for scenarios requiring fast access to data. This article will explore the implementation and usage of hash maps in C++.

What is a Hash Map?

A hash map uses a hash function to map keys to indices in an underlying array (often called a bucket array). This function takes a key as input and generates an index. When you want to insert a key-value pair, the hash function determines the bucket where the pair will be stored. When retrieving a value, the same hash function is used to locate the correct bucket.

However, hash functions aren't perfect; sometimes different keys can produce the same index (a "collision"). Various collision resolution techniques are employed to handle these situations, such as separate chaining (using linked lists within buckets) or open addressing (probing for empty slots).

Implementing Hash Maps in C++

C++ provides std::unordered_map in the <unordered_map> header file, offering a ready-made hash map implementation. This is generally the preferred approach over manually building one, as it's optimized and thoroughly tested.

Using std::unordered_map

Let's illustrate with a simple example:

#include <iostream>
#include <unordered_map>

int main() {
  // Create a hash map to store strings as keys and integers as values.
  std::unordered_map<std::string, int> myMap;

  // Insert key-value pairs.
  myMap["apple"] = 1;
  myMap["banana"] = 2;
  myMap["cherry"] = 3;

  // Access values using keys.
  std::cout << "Value of apple: " << myMap["apple"] << std::endl; // Output: 1

  // Check if a key exists.
  if (myMap.count("banana")) {
    std::cout << "banana exists in the map" << std::endl;
  }

  // Iterate through the map.
  for (const auto& pair : myMap) {
    std::cout << pair.first << ": " << pair.second << std::endl;
  }

  // Remove a key-value pair.
  myMap.erase("banana");

  return 0;
}

This code demonstrates basic operations: insertion, access, existence check, iteration, and deletion. std::unordered_map handles collisions internally, making the code concise and efficient.

Choosing Hash Functions

The performance of a hash map significantly depends on the quality of its hash function. A good hash function minimizes collisions, distributing keys uniformly across the buckets. std::unordered_map uses a default hash function suitable for many common key types. However, for custom key types, you might need to provide a custom hash function. This is done by specializing the std::hash struct:

#include <functional> // for std::hash

struct MyCustomKey {
  int a;
  std::string b;
};

namespace std {
  template <>
  struct hash<MyCustomKey> {
    size_t operator()(const MyCustomKey& key) const {
      // Implement your custom hash function here.  A simple example:
      size_t h1 = std::hash<int>{}(key.a);
      size_t h2 = std::hash<std::string>{}(key.b);
      return h1 ^ (h2 << 1); // Combine hashes
    }
  };
}

This example shows a custom hash function for a struct MyCustomKey. The quality of your custom hash function is crucial for optimal performance. Poorly designed hash functions can lead to many collisions, degrading performance to O(n) for worst-case scenarios.

When to Use Hash Maps

Hash maps are an excellent choice when:

• Fast lookups are crucial: The O(1) average-case time complexity for lookups is a major advantage.
• You need to store key-value pairs: They're designed for this purpose.
• Keys are unique: While you can have multiple values associated with a single key (using e.g., std::unordered_multimap), the primary use case is unique keys.
• Memory usage is not a primary concern: Hash maps have some overhead compared to simpler data structures.

Choosing Between std::unordered_map and std::map

C++ offers another map-like container, std::map, which is a tree-based implementation providing sorted keys. While std::map offers logarithmic time complexity for operations, std::unordered_map generally outperforms it in speed for average-case scenarios. Choose std::unordered_map when speed is paramount; choose std::map if you need sorted keys or guaranteed logarithmic time complexity.

Conclusion

Hash maps are valuable tools in a C++ programmer's arsenal. std::unordered_map provides a powerful and efficient implementation, ready to handle various use cases requiring fast key-value storage and retrieval. Understanding its capabilities and limitations allows you to leverage its strengths in your projects. Remember to consider the implications of hash function choice, especially when working with custom key types, to maximize performance.