好的哈希函数2d索引 [英] Good hash function for a 2d index
问题描述
我有一个名为Point的结构体。点很简单:
struct Point
{
行row;
列列;
//其他用于加减点的代码也有
}
现在我使用了一个 所以,我想有一个 但是,我不确定这是不是一个很好的哈希函数。我想要的东西快,因为我需要做很多查找非常快。是否有更好的散列函数我可以使用,或者是这个确定? Java (第2版),并在 中进行编程。有一个素数常数(我们会说53,但你可能会发现更大的将在这里给更多的均匀分布),并执行乘法和加法如下: 对于更多的值(比如你添加az坐标),只需保持嵌套,例如 int_hash 行和
列基本上是美化的
是一个散列一个整数的函数。您可以访问此网页,以查找单个整数的一堆好的哈希函数 。 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();
}
};
(53 + int_hash(row))* 53 + int_hash(col)
((53 + int_hash 53 + int_hash(col))* 53 + int_hash(z)
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 int
s, 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 Point
s. 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屋!