代码之家  ›  专栏  ›  技术社区  ›  rlbond

适合二维索引的哈希函数

  •  14
  • rlbond  · 技术社区  · 14 年前

    我有一个名为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 通常,该集合可能包含,例如,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();
        }
    };
    

    但是,我不确定这是否真的是一个好的哈希函数。我想要快一点的,因为我需要很快地做很多查找。是否有更好的哈希函数可以使用,或者这样可以吗?

    3 回复  |  直到 6 年前
        1
  •  18
  •   Peter Krauss    6 年前

    以下技术在 通用程序设计 (第二版),并从中引用 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 是用于散列单个整数的函数。您可以访问此页面以查找 a bunch of good hash functions 对于单个整数。

        2
  •  1
  •   Michael Dorgan    14 年前

    有了足够小的域,您可能就能想出一个完美的哈希函数。或者使用二维数组。对于较大的数据量,使用基于质数的乘法和mod来调整表的大小(如果表的大小是以2为基数的数字)。这就消除了在小型嵌入式系统上成本高昂的划分/修改。

    或者查找已经存在的任何数量的基于整数的哈希函数。确保测量为冲突创建的任何哈希函数。足够的碰撞将消除O(n log n)方法(如地图/树)的任何增益。

        3
  •  1
  •   Brian R. Bondy    14 年前

    我想用10来代替比特移位比用1000来乘以效率更高。

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