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

Question

我已经定义了一个名为Point的类，它将被用作unordered_map中的一个键。所以，我在课堂上提供了一个operator==函数，我还为template specialization提供了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使用chained hash，而不是开放地址哈希。具有相同散列值的所有条目都放在同一个存储桶中，这是一个链接列表。因此，低质量的哈希不会在桶之间很好地分配条目。

很明显，你的哈希为{x, y}和{y, x}提供了相同的哈希值。更严重的是，小矩形中的任何点集合将共享相同数量的不同散列值，因为散列值的高阶位将全部相同。

Answer 2

Knowing that Point is intended to store coordinates within an image，这里最好的哈希函数是：

pt.x() + pt.y() * width

其中width是图像的宽度。

考虑到x是[0, width-1]范围内的值，上面的哈希函数为pt的任何有效值产生唯一的数字。不可能发生碰撞。

请注意，如果将图像存储为单个内存块，则此哈希值对应于点pt的线性索引。也就是说，如果y也在有限范围内（[0, height-1]），则生成的所有哈希值都在[0, width* height-1]范围内，并且可以生成该范围内的所有整数。因此，请考虑用简单数组（即图像）替换哈希表。图像是将像素位置映射到值的最佳数据结构。