Частые коллизии хэшей при хэшировании 3D-координат

Я пытаюсь хешировать 3D-координату, чтобы создать уникальный идентификатор для индекса карты.

мой подход в настоящее время

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;

но проблема в том, что я получаю много коллизий хешей... просто запускаю этот тест, и vec(0,0,0), и vec(-1,0,0) сопоставляются друг с другом

Я чувствую, что это должно работать, коллизии хэшей должны происходить только в 2.32831e-08% раз по моим приблизительным расчетам... я что-то упустил?

Редактировать: при выполнении моей программы данный ввод должен хэшироваться в один и тот же вывод всякий раз, когда вычисляется, поэтому наличие какого-то внутреннего состояния для хэша, которое изменяется при каждом вызове, невозможно.


c++ hash hash-collision
person Jay    schedule 15.12.2020    source источник

Ответы (2)


arrow_upward
2
arrow_downward

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 хэшей.

person Quimby    schedule 15.12.2020

arrow_upward
5
arrow_downward

Вы должны использовать объединитель хэшей, который делает маловероятным, что разные вещи хешируют одно и то же.

Как и в случае с хэш(а)+хэш(б)+хеш(с) будет то же самое, ибо (а,б,в) это (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);
}

Итак, пример: создание живого демо

Прямая трансляция на 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
person sehe    schedule 15.12.2020
comment
Добавлено несколько тестовых входных данных для демонстрации - person sehe; 15.12.2020