C ++ 0x에서 해시 값을 어떻게 결합합니까?

<질문>

C ++ 0x는 hash <...> (...)를 추가합니다.

그러나 부스트에 제시된 것처럼 hash_combine 함수를 찾을 수 없습니다. 이와 같은 것을 구현하는 가장 깨끗한 방법은 무엇입니까? 아마도 C ++ 0x xor_combine을 사용하고 계십니까?

---

<답변1>

글쎄, 그냥 부스트 녀석들이했던 것처럼하세요 :

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

---

<답변2>

이 솔루션을 찾는 다른 사람들에게 유용 할 수 있으므로 여기에서 공유하겠습니다. @KarlvonMoor 답변에서 시작하여 여러 값을 함께 결합해야하는 경우 사용이 더 간결한 가변 템플릿 버전이 있습니다.

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

template 
inline void hash_combine(std::size_t& seed, const T& v, Rest... rest) {
    std::hash 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 {\
            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

---

<답변3>

이는 다음과 같이 가변 템플릿을 사용하여 해결할 수도 있습니다.

#include 

template  struct hash;

template 
struct hash 
    : public std::hash
{
    using std::hash::hash;
};


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

용법:

#include 

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

확실히 템플릿 함수를 만들 수는 있지만, 이로 인해 불쾌한 유형 추론이 발생할 수 있습니다. 예를 들어 hash ( "Hallo World!")는 문자열이 아닌 포인터에서 해시 값을 계산합니다. 이것이 아마도 표준이 구조체를 사용하는 이유 일 것입니다.

---

<답변4>

며칠 전에이 답변의 약간 개선 된 버전을 생각해 냈습니다 (C ++ 17 지원이 필요합니다).

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

위의 코드는 코드 생성 측면에서 더 좋습니다. 내 코드에서 Qt의 qHash 함수를 사용했지만 다른 해시를 사용할 수도 있습니다.

---

<답변5>

나는 vt4a2h의 답변에서 C ++ 17 접근 방식을 정말 좋아하지만 문제가 있습니다. Rest는 값으로 전달되는 반면 const 참조로 전달하는 것이 더 바람직 할 것입니다. 이동 전용 유형과 함께 사용할 수 있음).

다음은 여전히 fold 표현식 (C ++ 17 이상이 필요한 이유)을 사용하고 std :: hash (Qt 해시 함수 대신)를 사용하는 개조 된 버전입니다.

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

완전성을 위해 :이 버전의 hash_combine에서 사용할 수있는 모든 유형에는 std 네임 스페이스에 삽입 된 해시에 대한 템플릿 전문화가 있어야합니다.

예:

namespace std // Inject hash for B into std::
{
    template<> struct hash
    {
        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
    {
        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;
        }
    };
}

---

<답변6>

vt4a2h의 대답은 확실히 좋지만 C ++ 17 접기 표현식을 사용하며 모든 사람이 새로운 도구 모음으로 쉽게 전환 할 수있는 것은 아닙니다. 아래 버전은 확장기 트릭을 사용하여 접기 표현식을 에뮬레이트하고 C ++ 11 및 C ++ 14에서도 작동합니다.

또한 함수를 인라인으로 표시하고 가변 템플릿 인수에 대해 완벽한 전달을 사용합니다.

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

컴파일러 탐색기의 라이브 예제