二维索引的良好散列函数

Good hash function for a 2d index(二维索引的良好散列函数)

本文介绍了二维索引的良好散列函数的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

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

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
}

RowColumn 基本上是美化的 ints,但我厌倦了不小心将输入参数转换为函数并给它们每个包装类.

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.

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

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

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

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?

推荐答案

遵循 Effective Java (2nd edition) 中给出的技术,并在 Programming in Scala 中引用了该技术em>.有一个素数常数(我们会说 53,但你可能会发现更大的常数会得到更均匀的分布),并按如下方式执行乘法和加法:

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)

对于更多值(假设您添加 z 坐标),只需继续嵌套,例如

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)

其中 int_hash 是用于散列单个整数的函数.您可以访问此页面找到 一堆很好的散列函数用于单个整数.

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.

这篇关于二维索引的良好散列函数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持编程学习网!

本文标题为:二维索引的良好散列函数

基础教程推荐