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

Question

我定义了一个名为 Point 的 class，它将用作 unordered_map 中的键。因此，我在 class 中提供了一个 operator== 函数，并且还为 std::hash 提供了一个 template specialization 函数。根据我的研究，这些是我发现必要的两件事。相关代码如图：

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;

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

Answer 1

那是一个糟糕的散列函数。但它是合法的，因此您的实施将有效。

Hash and 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]范围内，并且可以生成该范围内的所有整数。因此，考虑用一个简单的数组（即图像）替换散列 table。图像是将像素位置映射到值的最佳数据结构。

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

C++ Hash Table - How is collision for unordered_map with custom data type as keys resolved?

c++

hashmap

unordered-map

user-defined-types

hash-collision