我在 C++ 中使用 boost 散列函数将 3 个双打组合成一个面临冲突的散列

Question

失败我的意思是它为不同的双精度组提供了重复的值。三个双精度是顶点的 x、y 和 z。我有一个顶点列表，并使用从双打创建的哈希作为地图中的键。我想知道是否存在针对此特定应用程序的更可靠的哈希组合函数。

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

Answer 1

我有一个顶点列表，并使用从双打创建的哈希作为地图中的键。

不是散列的最佳用途，就什么std::hash或boost::hash代表什么而言。

您正在寻找独特性。这种意义上的散列不是唯一的。

我想知道是否存在针对此特定应用程序的更可靠的哈希组合函数。

除非哈希空间与 z、y 和 z 的可能值的空间具有 1:1 的相关性——这实质上意味着使用顶点本身作为标识符。

概括：

如果您想要一个由唯一顶点索引的容器，您可能需要考虑 std::unordered_map。您将需要提供一个相等运算符。

一个例子：

#include <boost/functional/hash.hpp> // see below
#include <tuple>
#include <unordered_map>
#include <string>

// a simple Vertex class
struct Vertex
{
    double x, y, z;
};

// a useful general-purpose accessor
auto as_tuple(Vertex const& v) -> decltype(auto)
{
    return std::tie(v.x, v.y, v.z);
}

// equality implemented in terms of tuple, for simplicity
bool operator==(Vertex const& l , Vertex const& r)
{
    return as_tuple(l) == as_tuple(r);
}

// hash_value implemented in terms of tuple, for consistency and simplicity
std::size_t hash_value(Vertex const& v)
{
    using boost::hash_value;
    return hash_value(as_tuple(v));
}

// the boring bit - injecting a hash specialisation into the std:: namespace
// but let's derive from boost's hash class, which is much better
// in that it allows easy hashing using free functions
namespace std {
    template<> struct hash<::Vertex> : boost::hash<::Vertex> {};
}

using vertex_map = std::unordered_map<Vertex, std::string>;

int main()
{
    auto m = vertex_map();

    m[{0, 0, 0}] = "Sol";
    m[{1, 3, 5}] = "Mars";
    m[{100.4, 343.2, 92.44}] = "Pluto";
}

注意：以上数字以 Zargian NonLinear Megaunits 表示 - 您不会在任何有关太阳系的地球教科书中找到它们。