我正在使用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";
}

注:上面的数字是在扎尔根NonLinear超级单位--你不会在太阳系的任何地球教科书中找到它们。