CODEWITHSUNDEEP
c++hashhash-collision
Jay
Jay

Reputation: 2946

Frequent hash collisions when hashing 3d coordinates

I'm trying to hash a 3d coordinate to make a unique ID for an index to a map

my approach is currently

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

Or in 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;

but the problem is i'm getting loads of hash collisions... just running this test, both vec(0,0,0) and vec(-1,0,0) map onto each other

I feel like this should work, hash collisions should approach happening only 2.32831e-08% of the time by my rough calculations... am I missing something?

Edit: Within an execution of my program a given input should hash into the same output whenever calculated, so having some kind of internal state to the hasher that is changed with each call is not possible

Upvotes: 3

Views: 373

Answers (2)

sehe
sehe

Reputation: 392979

You should use a hash combiner that makes it unlikely that different things hash the same.

Like with hash(a)+hash(b)+hash(c) will be the same for (a,b,c) is (1,2,3), (3,1,2), (2,1,3), (2,3,1) etc.

The typical hash combine looks like e.g.

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

So example: making live demo

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";
}

Prints

   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

Upvotes: 5

Quimby
Quimby

Reputation: 19113

vec.y + std::hash<float>() (vec.z) is adding std::size_t and float. The result will be a float, but since the integer will be on average 32-digit long, adding a small float with 7 digits to it will easily yield the same float value.

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

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

Something like this could be used, it hashes the individual elements and uses the nested scheme to break the order in-dependency of simply adding the 3 hashes.

Upvotes: 2

Related Questions