一个适合2D索引的好哈希函数。

Question

我有一个叫做Point的结构体，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。

所以，我想要有一个Point的unordered_set。通常这个集合可能包含比如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();
    }
};

然而，我不确定这是否是一个好的哈希函数。我需要一个快速的函数，因为我需要非常快速地进行许多查找。有更好的哈希函数可以使用吗，还是这个可以吗？

- rlbond

Answer 1

以下技巧摘自Effective Java（第2版），并在Programming in 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 对单个整数进行哈希。您可以访问此页面查找适用于单个整数的大量优秀的哈希函数。

- Ken Bloom

Answer 2

我认为使用位移运算符将数字左移10位比乘以1000更高效。

return (val.row.value()<<10) + val.col.value();

- Brian R. Bondy

---

不要过早优化。#1 这是一种微观优化，不太可能为您节省很多时间。#2 它只会使代码更加晦涩难懂。#3 如果您的编译器聪明的话，你可以选择像1024这样的数字而不是1000，如果在您的计算机指令集上实际上有意义，您的编译器会自动进行优化。 - Ken Bloom

@Ken：我同意一般情况下不要过早优化，但对于一个简单的哈希函数，我不同意。它是一个哈希函数或数学函数。 - Brian R. Bondy

此外，val.row.value() * 1000 是否大于 val.column.value() 并不重要，因为这是哈希码，计算的唯一原因是将点放置在哈希表中的随机位置。有重叠和类似的情况可以帮助事情更顺利。 - Ken Bloom

我同意这不太可能产生任何（或很少的）性能差异，但在我看来，位移形式更清晰，因为它恰好是他想要做的 - 他实际上不想知道乘以1000时的结果，他想要把一些位移到其他位上，这正是位移所表示的。如果尝试调试哈希函数，我会发现这更直观，而不是乘法。 - Peter

@Brian 为了证明第二点，你的运算符优先级是错误的。你的代码等价于 val.row.value() << (10 + val.col.value())（这将是一个非常糟糕的哈希函数，因为大多数值在取模后都会映射到桶0）。这就是为什么不建议混合位运算和算术运算，以及为什么总体上不建议过早地进行优化。 - Ken Bloom

@Ken: 我已经修改了，但我不同意你的任何观点。但这就是你对我投反对票的原因，基本上我认为这不是一种优化方式，也不明白为什么使用乘法更清晰。如果你想要4倍的苹果，那么你会使用乘法，如果你在计算数学函数，那么谁会在意呢？总之，我们继续吧... - Brian R. Bondy

Answer 3

如果域很小，您可能能够找到一个完美的哈希函数。或者只需使用二维数组即可。对于更大的数据量，请使用基于质数的乘法和模运算来确定表格大小（如果您的表格大小是2的幂）。这消除了在较小的嵌入式系统上可能会产生代价的除法/模数。

或者找到现有的任何基于整数的哈希函数。确保您为创建的任何哈希函数测量碰撞。足够的冲突将消除比像映射/树这样的O（n log n）方法所获得的任何收益。

- Michael Dorgan