C++ pair을 위한 hashing

이 글을 쓰게 된 경위는 이 문제를 풀면서 발생

위 문제를 풀다보니 pair<string, string>을 위한 hash를 구해야 할 일이 생겼다. 문제는 C++에서 primitive type에 기반한 pair을 위한 hashing을 제공하지 않는다는 점.

이거랑 약간 관련된 재밌는 글이 있다. std namespace에다가 사용자가 primitive만으로 이루어진 type에 관한 hashing을 추가하지 못하게 하는 이유.

그럼 hash를 우리가 만들어야 하는데... 어떤 hashing function이 좋을까? 누가 미리 만들어 놓은 좋은 hashing function은 없으려나? 다행히도 있다. boost라는 템플릿 라이브러리 집합에서 제공해준다.

여러개의 element로 이루어진 객체에 대한 hashing

pair 뿐만 아니라 다른 곳에서도 활용이 가능한데 pair을 예시로 들겠다. boost의 hash_combine 함수를 사용해 pair의 각 value를 고려한 hash value를 만들 수가 있다.

struct pair_hash {
public:
    template <typename T, typename U>
    std::size_t operator()(const std::pair<T, U>& x) const
    {
        size_t seed = 0;
        hash_combine(seed, x.first);
        hash_combine(seed, x.second);
        return seed;
    }
};

만약 boost를 사용하지 못한다면 (백준이라든가) 밑과 같은 hash_combine함수를 추가하도록 하자.

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

위 코드는 스택오버플로우에서 가져왔는데 사실 실제 라이브러리에서도 저것을 사용한다. 저 hash_combine이 최선인지에 대한 논의도 해당 글에 있음.

iterator을 활용해서 다수 element의 모음에 대한 hash value를 만드는 것도 가능하다.

std::vector<std::string> some_strings;
std::size_t hash = boost::hash_range(some_strings.begin(), some_strings.end());

위 예제는 이 글에서 가져왔다.