2d索引的良好哈希函数

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中的Programming中引用.有一个素数常数(我们会说53但你可能会发现更大的东西会在这里给出更均匀的分布),并执行乘法和加法如下:

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

对于更多值(比如你添加az坐标),只需保持嵌套,就像

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

int_hash用于散列单个整数的函数在哪里.您可以访问此页面以查找一组用于单个整数的良好哈希函数.