好的哈希函数2d索引 [英] Good hash function for a 2d index

问题描述

我有一个名为Point的结构体。点很简单：

  struct Point 
 {
行row; 
列列; 
 
 //其他用于加减点的代码也有
} 
  

行和列基本上是美化的 int



现在我使用了一个，但是我没有意识到将输入参数转换为函数并给它们一个包装器类。设置点，但重复的查找真的减慢了事情。我想切换到 unordered_set 。

所以，我想有一个 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（）; 
} 
}; 
  

但是，我不确定这是不是一个很好的哈希函数。我想要的东西快，因为我需要做很多查找非常快。是否有更好的散列函数我可以使用，或者是这个确定？

解决方案

Java （第2版），并在 中进行编程。有一个素数常数（我们会说53，但你可能会发现更大的将在这里给更多的均匀分布），并执行乘法和加法如下：

 （53 + int_hash（row））* 53 + int_hash（col）
  

对于更多的值（比如你添加az坐标），只需保持嵌套，例如

 （（53 + int_hash 53 + int_hash（col））* 53 + int_hash（z）
  

int_hash 是一个散列一个整数的函数。您可以访问此网页，以查找单个整数的一堆好的哈希函数 。

I have a struct called Point. Point is pretty simple:

struct Point
{
    Row row;
    Column column;

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

Row and Column are basically glorified ints, but I got sick of accidentally transposing the input arguments to functions and gave them each a wrapper class.

Right now I use a set of points, but repeated lookups are really slowing things down. I want to switch to an unordered_set.

So, I want to have an unordered_set of Points. Typically this set might contain, for example, every point on a 80x24 terminal = 1920 points. I need a good hash function. I just came up with the following:

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();
    }
};

However, I'm not sure that this is really a good hash function. I wanted something fast, since I need to do many lookups very quickly. Is there a better hash function I can use, or is this OK?

解决方案

Following the technique is given in Effective Java (2nd edition), and quoted from there in Programming in Scala. Have a prime constant (we'll say 53 but you may find something larger will give more even distribution here), and perform multiplication and addition as follows:

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

For more values (say you add a z coordinate), just keep nesting, like

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

Where int_hash is a function for hashing a single integer. You can visit this page to find a bunch of good hash functions for single integers.

这篇关于好的哈希函数2d索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！