C++ 哈希表 - 如何解决 unordered_map 与自定义数据类型作为键的冲突？

Question

我定义了一个名为的类，该类Point将用作unordered_map. 所以，我operator==在类中提供了一个函数，我还提供了一个template specializationfor std::hash。根据我的研究，这是我认为必要的两件事。相关代码如图：

class Point
{
    int x_cord = {0};
    int y_cord = {0};
public:
    Point()
    {

    }
    Point(int x, int y):x_cord{x}, y_cord{y}
    {

    }
    int x() const
    {
        return x_cord;
    }
    int y() const
    {
        return y_cord;
    }
    bool operator==(const Point& pt) const
    {
        return (x_cord == pt.x() && y_cord == pt.y());
    }
};

namespace std
{
    template<>
    class hash<Point>
    {
    public:
        size_t operator()(const Point& pt) const
        {
            return (std::hash<int>{}(pt.x()) ^ std::hash<int>{}(pt.y()));
        }
    };
}

// Inside some function
std::unordered_map<Point, bool> visited;

该程序编译并在我测试的情况下给出了正确的结果。但是，当使用用户定义的类作为键时，我不相信这是否足够。unordered_map在这种情况下如何知道如何解决冲突？我需要添加任何东西来解决冲突吗？

Answer 1

这是一个可怕的哈希函数。但它是合法的，因此您的实施将起作用。

Hash 和 Equals 的规则（实际上也是唯一的规则）是：

• 如果a == b，那么std::hash<value_type>(a) == std::hash<value_type>(b)。

（同样重要的是，Hash 和 Equals 总是为相同的参数产生相同的值。我曾经认为这是不言而喻的，但我已经看到了几个 SO 问题，其中 unordered_map 产生了意想不到的结果，正是因为这些函数中的一个或两个依赖一些外部价值。）

这将由始终返回 42 的哈希函数来满足，在这种情况下，地图在填满时会变得非常慢。但除了速度问题之外，代码可以工作。

std::unordered_map使用链式散列，而不是开放地址散列。所有具有相同哈希值的条目都放在同一个桶中，这是一个链表。所以低质量的散列不能很好地在存储桶之间分配条目。

很明显，你的哈希给人{x, y}和{y, x}相同的哈希值。更严重的是，一个小矩形中的任何点集合都将共享相同数量的不同哈希值，因为哈希值的高位都是相同的。