Using Standard Library Hash Tables

Section 33.11 Using Standard Library Hash Tables

The C++ standard library provides unordered_set and unordered_map classes that implement hash table based sets and maps. (As opposed to the set and map classes that implement BST based sets and maps.)

🔗

The standard library specifications require that elements are not moved in memory even when the hash table grows. This essentially requires that implementations use open hashing and do not store elements directly in the array. Because this approach may not be as efficient for small data types, there are popular third-party libraries like boost::unordered_flat_map and robin_hood::map that provide hash table implementations that are work just like the standard library version but use closed hashing and store elements directly in the array.

🔗

The most significant requirement for using the std::unordered_set and std::unordered_map classes is that the key type must be hashable and comparable for equality.

🔗

If a custom type already has an equality operator defined, it is possible to provide a specialization of std::hash for that type. Although normally you do not want to add things to the std namespace, specializing std::hash for a custom data type is an exception to that rule. The listing below shows this being done for a simple Person struct.

🔗

Listing 33.11.1.

🔗

#include <functional>
#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

// A type that defines ==
struct Person {
    string name;
    int age;
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

// Add a specialization of std::hash for our Person type
// Adding to the std namespace
namespace std {

// There is no "type T" as we are fully specializing the template
  template<>
  struct hash<Person> {
      // store hashers as member variables to avoid constructing them every time
      std::hash<string> stringHasher;
      std::hash<int> intHasher;
      size_t operator()(const Person& p) const {
          size_t h1 = stringHasher(p.name);
          size_t h2 = intHasher(p.age);

return h1 ^ (h2 << 1);
      }
  };

} // namespace std

int main() {
    std::unordered_map<Person, string> personToCity;

Person alice{"Alice", 30};
    Person bob{"Bob", 25};

personToCity.emplace(alice, "New York");
    personToCity.emplace(bob, "Los Angeles");

cout << alice.name << " lives in " << personToCity.at(alice) << endl;
    cout << bob.name << " lives in " << personToCity.at(bob) << endl;
}

Because we have an equality operator, and now there is a definition for std::hash<Person>, on line 38, we can simply declare:

🔗

std::unordered_map<Person, string> personToCity;

The standard library will use our specialization of std::hash<Person> to hash the keys and the equality operator to compare keys for equality when needed.

🔗

Alternatively, we can define our own functor for hashing and pass it as a template argument to std::unordered_map. We can also pass in a functor that determines equality if we don’t want to use the default equality operator. This second version of the program uses this approach:

🔗

Listing 33.11.2.

🔗

#include <functional>
#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

// A type that defines ==
struct Person {
    string name;
    int age;
    // built in equality operator that compares both name and age
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

// Custom hash functor for Person that only uses the name for hashing
struct PersonHash {
    std::hash<string> stringHasher;
    size_t operator()(const Person& p) const {
        return stringHasher(p.name);
    }
};

// Custom equality determiner for Person that only uses the name for equality
struct PersonEqual {
    bool operator()(const Person& p1, const Person& p2) const {
        return p1.name == p2.name;
    }
};

int main() {
    // Create an unordered_map that uses our custom hash and equality functors
    std::unordered_map<Person, string, PersonHash, PersonEqual> personToCity;
    Person alice{"Alice", 30};
    Person bob{"Bob", 25};

personToCity.emplace(alice, "New York");
    personToCity.emplace(bob, "Los Angeles");

cout << alice.name << " lives in " << personToCity.at(alice) << endl;
    cout << bob.name << " lives in " << personToCity.at(bob) << endl;
}

This time, on like 36 we declare the unordered map with our custom hash and equality functors:

🔗

std::unordered_map<Person, string, PersonHash, PersonEqual> personToCity;

Note that the hash and equality functors we defined are consistent with each other. They both rely on just the name to determine the hash value and equality. If the Person == used the same logic, we could skip the equality functor and just use the default equality operator. In that case, we could declare the unordered map like this:

🔗

std::unordered_map<Person, string, PersonHash> personToCity;

Note 33.11.1.

Always remember that a hash function and equality operation for objects in a hash table always should be based on the same attributes.

🔗

You have attempted of activities on this page.

🔗

Prev Top Next