c++ - 二维索引的良好哈希函数

Question

我有一个名为 Point 的结构。要点很简单:

struct Point
{
    Row row;
    Column column;

    // some other code for addition and subtraction of points is there too
}

Row 和 Column 基本上是美化的 int，但我厌倦了不小心将输入参数转换为函数并给它们每个包装类。

现在我使用 set 点，但重复查找确实会减慢速度。我想切换到 unordered_set。

所以，我想要一个 unordered_set 的 Point。通常，该集合可能包含例如 80x24 终端上的每个点 = 1920 个点。我需要一个好的散列函数。我刚刚想出了以下内容:

struct PointHash : public std::unary_function<Point, std::size_t>
{
    result_type operator()(const argument_type& val) const
    {
        return val.row.value() * 1000 + val.col.value();
    }
};

但是，我不确定这是否真的是一个很好的哈希函数。我想要一些快速的东西，因为我需要非常快速地进行许多查找。有没有更好的哈希函数我可以使用，或者这样可以吗？

Answer 1

Effective Java(第 2 版)中给出了该技术，并在 Scala 编程中引用了该技术。有一个素数常数(我们会说 53，但您可能会发现更大的值会在这里得到更均匀的分布)，并按如下方式执行乘法和加法:

(53 + int_hash(row)) * 53 + int_hash(col)

对于更多的值(比如你添加一个 z 坐标)，继续嵌套，就像

((53 + int_hash(row)) * 53 + int_hash(col)) * 53 + int_hash(z)

其中 int_hash 是一个用于散列单个整数的函数。您可以访问此页面查找a bunch of good hash functions对于单个整数。