散列 3d 坐标时频繁散列冲突

Question

我正在尝试对 3d 坐标进行哈希处理，以便为地图的索引创建唯一 ID

我目前的做法是

return hash(x + hash(y + hash(z)));

或者在 c++ 中

struct ChunkHasher
{
    std::size_t operator()(FLOAT3 const& vec) const
    {
        return std::hash<float>()(
            vec.x + std::hash<float>()(
                vec.y + std::hash<float>() (vec.z)
                )
            );
    }
}chunkHasher;

但问题是我遇到了 loads 哈希冲突... 只是运行这个测试， vec(0,0,0) 和 vec(-1,0,0) 相互映射

我觉得这应该工作，根据我的粗略计算，哈希冲突应该只在 2.32831e-08% 的时间内发生...我是否遗漏了什么？

编辑：在我的程序的执行过程中，无论何时计算，给定的输入都应该散列到相同的输出中，因此不可能在每次调用时更改散列器的某种内部状态

Answer 1

您应该使用哈希组合器，使不同的事物不太可能哈希相同。

与 hash(a)+hash(b)+hash(c) 一样，(a,b,c) 是 (1,2,3), (3,1,2)， (2,1,3), (2,3,1) 等

典型的哈希组合看起来像

template <class T>
inline void hash_combine(std::size_t& seed, const T& v)
{
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}

举个例子：制作现场演示

Live on Coliru

#include <functional>
#include <iostream>
#include <iomanip>

template <class T>
inline void hash_combine(std::size_t& seed, const T& v)
{
    std::hash<T> constexpr hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}

struct FLOAT3 { float x, y, z; };

template <> struct std::hash<FLOAT3> {
    size_t operator()(FLOAT3 const& f3) const {
        size_t v = 0x778abe;
        hash_combine(v, f3.x);
        hash_combine(v, f3.y);
        hash_combine(v, f3.z);
        return v;
    }
};

int main() {
    std::hash<FLOAT3> constexpr h;
    using std::setw;

    for (auto x : {.1f, 1e19f, 8e-9f })
    for (auto y : {.1f, 1e19f, 8e-9f })
    for (auto z : {.1f, 1e19f, 8e-9f })
        std::cout
            << setw(6) << x << "\t"
            << setw(6) << y << "\t"
            << setw(6) << z << " -> "
            << std::hex << h({x,y,z}) << "\n";
}

版画

   0.1     0.1     0.1 -> 2022fc2207a6ab25
   0.1     0.1   1e+19 -> 919c9922fe821886
   0.1     0.1   8e-09 -> 960d84a2d4678d2b
   0.1   1e+19     0.1 -> 684a4180fc444de
   0.1   1e+19   1e+19 -> 596abb1854ebd77d
   0.1   1e+19   8e-09 -> 5cfb5c987a856ae0
   0.1   8e-09     0.1 -> f145ea71ac741736
   0.1   8e-09   1e+19 -> 26f7c77185489897
   0.1   8e-09   8e-09 -> 3b66a3f1d8b53520
 1e+19     0.1     0.1 -> c80abe72bee6c866
 1e+19     0.1   1e+19 -> 39789b73658d5881
 1e+19     0.1   8e-09 -> 32e9f6f35327e674
 1e+19   1e+19     0.1 -> 373b5488877d347d
 1e+19   1e+19   1e+19 -> c6cd7b88d050a5da
 1e+19   1e+19   8e-09 -> f95d9f082a3a124f
 1e+19   8e-09     0.1 -> 94a1f8f73e8fa675
 1e+19   8e-09   1e+19 -> 255fe5f0c5b43694
 1e+19   8e-09   8e-09 -> 2acec070ea4e8067
 8e-09     0.1     0.1 -> 799dd2b873ce62ba
 8e-09     0.1   1e+19 -> c82fb7b808ea9215
 8e-09     0.1   8e-09 -> c3bc9a39de8d3ca8
 8e-09   1e+19     0.1 -> 9112c88effbc9643
 8e-09   1e+19   1e+19 -> 6080eb8ec690671c
 8e-09   1e+19   8e-09 -> 6f70100e28fdf071
 8e-09   8e-09     0.1 -> f660883bf4d4c4ac
 8e-09   8e-09   1e+19 -> 48f6ed3badf8b40b
 8e-09   8e-09   8e-09 -> 4c41c0bb9b1522be

Answer 2

vec.y + std::hash<float>() (vec.z) 正在添加 std::size_t 和 float。结果将是一个浮点数，但由于整数的平均长度为 32 位，因此向其添加一个 7 位的小浮点数将很容易产生相同的浮点值。

std::size_t operator()(FLOAT3 const& vec) const
{
    std::hash<float> h;

    return h(h(vec.x)+ h(h(vec.y)+ h(vec.z)));
}

可以使用类似这样的东西，它散列各个元素并使用嵌套方案打破顺序独立性，只需添加 3 个散列。

散列 3d 坐标时频繁散列冲突

Frequent hash collisions when hashing 3d coordinates

c++

hash

hash-collision