当前位置： 文江博客话题详情

如何组合 C++0x 中的哈希值？

发布于 2024-08-27 22:52:26 字数 283 浏览 4 评论 0原文

C++0x 添加hash<...>(...)。

不过，我找不到 hash_combine 函数，如 提升。实现这样的事情最干净的方法是什么？也许，使用 C++0x xor_combine？

原文

C++0x adds hash<...>(...).

I could not find a hash_combine function though, as presented in boost. What is the cleanest way to implement something like this? Perhaps, using C++0x xor_combine?

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（9）

怎樣才叫好 2024-09-03 22:52:26

好吧，就像助推者那样做：

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

Well, just do it like the boost guys did it:

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);
}
回复 原文
寂寞花火° 2024-09-03 22:52:26

我将在这里分享它，因为它对于寻找此解决方案的其他人来说可能很有用：从 @KarlvonMoor 答案开始，这里有一个可变参数模板版本，如果您必须组合多个值，那么它的用法会更简洁一起：

inline void hash_combine(std::size_t& seed) { }

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

用法：

std::size_t h=0;
hash_combine(h, obj1, obj2, obj3);

这最初是为了实现可变参数宏而编写的，以便轻松地使自定义类型可哈希（我认为这是 hash_combine 函数的主要用法之一）：

#define MAKE_HASHABLE(type, ...) \
    namespace std {\
        template<> struct hash<type> {\
            std::size_t operator()(const type &t) const {\
                std::size_t ret = 0;\
                hash_combine(ret, __VA_ARGS__);\
                return ret;\
            }\
        };\
    }

用法：

struct SomeHashKey {
    std::string key1;
    std::string key2;
    bool key3;
};

MAKE_HASHABLE(SomeHashKey, t.key1, t.key2, t.key3)
// now you can use SomeHashKey as key of an std::unordered_map

I'll share it here since it can be useful to others looking for this solution: starting from @KarlvonMoor answer, here's a variadic template version, which is terser in its usage if you have to combine several values together:

inline void hash_combine(std::size_t& seed) { }

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

Usage:

std::size_t h=0;
hash_combine(h, obj1, obj2, obj3);

This was written originally to implement a variadic macro to easily make custom types hashable (which I think is one of the primary usages of a hash_combine function):

#define MAKE_HASHABLE(type, ...) \
    namespace std {\
        template<> struct hash<type> {\
            std::size_t operator()(const type &t) const {\
                std::size_t ret = 0;\
                hash_combine(ret, __VA_ARGS__);\
                return ret;\
            }\
        };\
    }

Usage:

struct SomeHashKey {
    std::string key1;
    std::string key2;
    bool key3;
};

MAKE_HASHABLE(SomeHashKey, t.key1, t.key2, t.key3)
// now you can use SomeHashKey as key of an std::unordered_map
回复 原文
花落人断肠 2024-09-03 22:52:26

我真的很喜欢 vt4a2h 的回答中的 C++17 方法，但是它遇到了一个问题： Rest 通过值传递，而通过 const 引用传递它们会更可取（如果它可与仅移动类型一起使用，这是必须的）。

这是改编后的版本，仍然使用 折叠表达式 （这就是为什么它需要 C++17 或更高版本）并使用 std::hash （而不是 Qt 哈希函数）：

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

为了完整起见：此版本的 hash_combine 可用的所有类型 必须具有 hash模板专业化 > 注入到 std 命名空间中。

示例：

namespace std // Inject hash for B into std::
{
    template<> struct hash<B>
    {
        std::size_t operator()(B const& b) const noexcept
        {
            std::size_t h = 0;
            cgb::hash_combine(h, b.firstMember, b.secondMember, b.andSoOn);
            return h;
        }
    };
}

因此，上例中的类型 B 也可以在另一个类型 A 中使用，如以下使用示例所示：

struct A
{
    std::string mString;
    int mInt;
    B mB;
    B* mPointer;
}

namespace std // Inject hash for A into std::
{
    template<> struct hash<A>
    {
        std::size_t operator()(A const& a) const noexcept
        {
            std::size_t h = 0;
            cgb::hash_combine(h,
                a.mString,
                a.mInt,
                a.mB, // calls the template specialization from above for B
                a.mPointer // does not call the template specialization but one for pointers from the standard template library
            );
            return h;
        }
    };
}

I really like the C++17 approach from the answer by vt4a2h, however it suffers from a problem: The Rest is passed on by value whereas it would be more desirable to pass them on by const references (which is a must if it shall be usable with move-only types).

Here is the adapted version which still uses a fold expression (which is the reason why it requires C++17 or above) and uses std::hash (instead of the Qt hash function):

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

For completeness sake: All the types which shall be usable with this version of hash_combine must have a template specialization for hash injected into the std namespace.

Example:

namespace std // Inject hash for B into std::
{
    template<> struct hash<B>
    {
        std::size_t operator()(B const& b) const noexcept
        {
            std::size_t h = 0;
            cgb::hash_combine(h, b.firstMember, b.secondMember, b.andSoOn);
            return h;
        }
    };
}

So that type B in the example above is also usable within another type A, like the following usage example shows:

struct A
{
    std::string mString;
    int mInt;
    B mB;
    B* mPointer;
}

namespace std // Inject hash for A into std::
{
    template<> struct hash<A>
    {
        std::size_t operator()(A const& a) const noexcept
        {
            std::size_t h = 0;
            cgb::hash_combine(h,
                a.mString,
                a.mInt,
                a.mB, // calls the template specialization from above for B
                a.mPointer // does not call the template specialization but one for pointers from the standard template library
            );
            return h;
        }
    };
}
回复 原文
萌化 2024-09-03 22:52:26

几天前，我想出了稍微改进的版本这个答案（需要C++ 17支持）：

template <typename T, typename... Rest>
void hashCombine(uint& seed, const T& v, Rest... rest)
{
    seed ^= ::qHash(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    (hashCombine(seed, rest), ...);
}

上面的代码是在代码生成方面更好。我在代码中使用了 Qt 中的 qHash 函数，但也可以使用任何其他哈希器。

A few days ago I came up with slightly improved version of this answer (C++ 17 support is required):

template <typename T, typename... Rest>
void hashCombine(uint& seed, const T& v, Rest... rest)
{
    seed ^= ::qHash(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    (hashCombine(seed, rest), ...);
}

The code above is better in terms of code generation. I used qHash function from Qt in my code, but it's also possible to use any other hashers.

回复 原文
毁虫ゝ 2024-09-03 22:52:26

vt4a2h 的 答案 当然很好，但使用 C++17 折叠表达式，并不是每个人都能够切换到更新的版本轻松使用工具链。下面的版本使用扩展器技巧来模拟折叠表达式，并且也适用于 C++11 和 C++14。

此外，我将函数标记为内联，并对可变参数模板参数使用完美转发。

template <typename T, typename... Rest>
inline void hashCombine(std::size_t &seed, T const &v, Rest &&... rest) {
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    (int[]){0, (hashCombine(seed, std::forward<Rest>(rest)), 0)...};
}

编译器资源管理器上的实时示例

The answer by vt4a2h is certainly nice but uses the C++17 fold expression and not everyone is able to switch to a newer toolchain easily. The version below uses the expander trick to emulate a fold expression and works in C++11 and C++14 as well.

Additionally, I marked the function inline and use perfect forwarding for the variadic template arguments.

template <typename T, typename... Rest>
inline void hashCombine(std::size_t &seed, T const &v, Rest &&... rest) {
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    (int[]){0, (hashCombine(seed, std::forward<Rest>(rest)), 0)...};
}

Live example on Compiler Explorer

回复 原文
骄兵必败 2024-09-03 22:52:26

这也可以通过使用可变参数模板来解决，如下所示：

#include <functional>

template <typename...> struct hash;

template<typename T> 
struct hash<T> 
    : public std::hash<T>
{
    using std::hash<T>::hash;
};


template <typename T, typename... Rest>
struct hash<T, Rest...>
{
    inline std::size_t operator()(const T& v, const Rest&... rest) {
        std::size_t seed = hash<Rest...>{}(rest...);
        seed ^= hash<T>{}(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        return seed;
    }
};

用法：

#include <string>

int main(int,char**)
{
    hash<int, float, double, std::string> hasher;
    std::size_t h = hasher(1, 0.2f, 2.0, "Hello World!");
}

当然可以创建一个模板函数，但这可能会导致一些令人讨厌的类型推导，例如 hash("Hallo World!") 将计算一个指针上的哈希值而不是字符串上的哈希值。这可能就是标准使用结构的原因。

This could also be solved by using a variadic template as follows:

#include <functional>

template <typename...> struct hash;

template<typename T> 
struct hash<T> 
    : public std::hash<T>
{
    using std::hash<T>::hash;
};


template <typename T, typename... Rest>
struct hash<T, Rest...>
{
    inline std::size_t operator()(const T& v, const Rest&... rest) {
        std::size_t seed = hash<Rest...>{}(rest...);
        seed ^= hash<T>{}(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        return seed;
    }
};

Usage:

#include <string>

int main(int,char**)
{
    hash<int, float, double, std::string> hasher;
    std::size_t h = hasher(1, 0.2f, 2.0, "Hello World!");
}

One could certainly make a template function, but this could cause some nasty type deduction e.g hash("Hallo World!") will calculate a hash value on the pointer rather than on the string. This is probably the reason, why the standard uses a struct.

回复 原文
甜味拾荒者 2024-09-03 22:52:26

许多答案都基于 boost::hash_combine。这是一个使用新的 boost::hash_combine 混合函数的解决方案：

#include <functional>
#include <limits>

// Borrowed from Boost.ContainerHash
// https://github.com/boostorg/container_hash/blob/ee5285bfa64843a11e29700298c83a37e3132fcd/include/boost/container_hash/hash.hpp#L471
template <typename T>
void hash_combine(std::size_t& seed, const T& v) {
    static constexpr auto digits = std::numeric_limits<std::size_t>::digits;
    static_assert(digits == 64 || digits == 32);
    
    if constexpr (digits == 64) {
        // https://github.com/boostorg/container_hash/blob/ee5285bfa64843a11e29700298c83a37e3132fcd/include/boost/container_hash/detail/hash_mix.hpp#L67
        std::size_t x = seed + 0x9e3779b9 + std::hash<T>()(v);
        const std::size_t m = 0xe9846af9b1a615d;
        x ^= x >> 32;
        x *= m;
        x ^= x >> 32;
        x *= m;
        x ^= x >> 28;
        seed = x;
    }
    else { // 32-bits
        // https://github.com/boostorg/container_hash/blob/ee5285bfa64843a11e29700298c83a37e3132fcd/include/boost/container_hash/detail/hash_mix.hpp#L88
        std::size_t x = seed + 0x9e3779b9 + std::hash<T>()(v);
        const std::size_t m1 = 0x21f0aaad;
        const std::size_t m2 = 0x735a2d97;
        x ^= x >> 16;
        x *= m1;
        x ^= x >> 15;
        x *= m2;
        x ^= x >> 15;
        seed = x;
    }
}

我将其作为练习留给读者编写使用表达式折叠的可变参数模板版本。

Many of the answers are based on the old implementation of boost::hash_combine. Here's a solution that uses the new boost::hash_combine mixing functions:

#include <functional>
#include <limits>

// Borrowed from Boost.ContainerHash
// https://github.com/boostorg/container_hash/blob/ee5285bfa64843a11e29700298c83a37e3132fcd/include/boost/container_hash/hash.hpp#L471
template <typename T>
void hash_combine(std::size_t& seed, const T& v) {
    static constexpr auto digits = std::numeric_limits<std::size_t>::digits;
    static_assert(digits == 64 || digits == 32);
    
    if constexpr (digits == 64) {
        // https://github.com/boostorg/container_hash/blob/ee5285bfa64843a11e29700298c83a37e3132fcd/include/boost/container_hash/detail/hash_mix.hpp#L67
        std::size_t x = seed + 0x9e3779b9 + std::hash<T>()(v);
        const std::size_t m = 0xe9846af9b1a615d;
        x ^= x >> 32;
        x *= m;
        x ^= x >> 32;
        x *= m;
        x ^= x >> 28;
        seed = x;
    }
    else { // 32-bits
        // https://github.com/boostorg/container_hash/blob/ee5285bfa64843a11e29700298c83a37e3132fcd/include/boost/container_hash/detail/hash_mix.hpp#L88
        std::size_t x = seed + 0x9e3779b9 + std::hash<T>()(v);
        const std::size_t m1 = 0x21f0aaad;
        const std::size_t m2 = 0x735a2d97;
        x ^= x >> 16;
        x *= m1;
        x ^= x >> 15;
        x *= m2;
        x ^= x >> 15;
        seed = x;
    }
}

I leave it as an exercise to the reader to write a variadic template version that uses expression folding.

回复 原文
淡忘如思 2024-09-03 22:52:26

Henri Menke的回答效果很好，但是如果您将警告视为错误，例如：

add_compile_options(-Werror)

GCC 9.3.0将给出这个错误：

Test.h:223:67: error: ISO C++ forbids compound-literals [-Werror=pedantic]
  223 |     (int[]){0, (hashCombine(seed, std::forward<Rest>(rest)), 0)...};
      |                                                                  ^
cc1plus: all warnings being treated as errors

我们可以更新代码以避免这样的错误：

template <typename T, typename... Rest>
inline void hashCombine(std::size_t &seed, T const &v, Rest &&... rest) {
    std::hash<T> hasher;
    seed ^= (hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2));
    int i[] = { 0, (hashCombine(seed, std::forward<Rest>(rest)), 0)... };
    (void)(i);
}

The answer by Henri Menke works great, but if you treat warnings as errors with for example:

add_compile_options(-Werror)

GCC 9.3.0 will give this error:

Test.h:223:67: error: ISO C++ forbids compound-literals [-Werror=pedantic]
  223 |     (int[]){0, (hashCombine(seed, std::forward<Rest>(rest)), 0)...};
      |                                                                  ^
cc1plus: all warnings being treated as errors

We can update the code to avoid the error like this:

template <typename T, typename... Rest>
inline void hashCombine(std::size_t &seed, T const &v, Rest &&... rest) {
    std::hash<T> hasher;
    seed ^= (hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2));
    int i[] = { 0, (hashCombine(seed, std::forward<Rest>(rest)), 0)... };
    (void)(i);
}
回复 原文
淡莣 2024-09-03 22:52:26

您可以使用 rst C++ 库我开发的目的是：

#include "rst/stl/hash.h"

struct Point {
  Point(const int x, const int y) : x(x), y(y) {}

  int x = 0;
  int y = 0;
};

bool operator==(const Point lhs, const Point rhs) {
  return (lhs.x == rhs.x) && (lhs.y == rhs.y);
}

namespace std {

template <>
struct hash<Point> {
  size_t operator()(const Point point) const {
    return rst::HashCombine({point.x, point.y});
  }
};

}

You can use the rst C++ library that I developed to do that:

#include "rst/stl/hash.h"

struct Point {
  Point(const int x, const int y) : x(x), y(y) {}

  int x = 0;
  int y = 0;
};

bool operator==(const Point lhs, const Point rhs) {
  return (lhs.x == rhs.x) && (lhs.y == rhs.y);
}

namespace std {

template <>
struct hash<Point> {
  size_t operator()(const Point point) const {
    return rst::HashCombine({point.x, point.y});
  }
};

}
回复 原文
~没有更多了~

关于作者

吃颗糖壮壮胆

暂无简介

0 文章
0 评论
942 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

qq_FjTq5B

文章 0 评论 0

18273202778

文章 0 评论 0

WordPress小学生

文章 0 评论 0

〃温暖了心ぐ

文章 0 评论 0

迷乱花海

文章 0 评论 0

niuniu

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文