User-defined Types as Hash Keys in C++

User-defined types can not be used as keys in containers like std::unordered_map unless we provide some extra features to them.

First, we need to figure out what does hashmap do under the hood. There are two important features in hashmap structure.

1. To find out where to put the key-value pairs in the hash table.
2. How to tell if two keys are identical.

That’s exactly what we need to provide to our user-defined types to help hash map do its work easily. Basically, We need to implement these two:

1. A equality operator.
2. A hash function.

If we directly use struct Pointer as the key type in std::unordered_map, we will get tons of compile errors.

struct Point {
    int x, y;
};

std::unordered_map<Point, int> map;

To make the Point type hashable, we need to modify the code to be:

struct Point {
    int x, y;

    bool operator==(const Point& other) const {
        return other.x == x && other.y == y;
    }
};

template<>
struct std::hash<Point> {
    std::size_t operator()(const Point& p) const noexcept {
        std::size_t h1 = std::hash<int>{}(p.x);
        std::size_t h2 = std::hash<int>{}(p.y);
        return h1 ^ (h2 + 0x9e3779b97f4a7c15ULL + (h1<<6) + (h1>>2));
    }
};

int main() {
    std::unordered_map<Point, int> map;
    map[{1, 2}] = 1;
    std::cout << "key: {1, 2}, value: " << map[{1, 2}] << std::endl;
    map[{1, 2}] = 3;
    std::cout << "key: {1, 2}, value: " << map[{1, 2}] << std::endl;
}

output:

key: {1, 2}, value: 1
key: {1, 2}, value: 3