std::hash - built-in타입이 아닌 경우 직접 정의해보기

std::hash

간단히 말하면,
어떤 함수 객체에 단일 인자를 전달했을 때 특정 반환 값이 출력되도록하는 기능이다.

Built-in 타입에 대한 std::hash 특수화 지원

해쉬 테이블 기능을 제공하는 std::unordered_map을 사용할 때

Key로 std::hash<> 특수화가 존재하지 않는 타입을 건내주면 아래와 같은 컴파일 에러가 발생한다.

Key로 전달된 타입에 대하여
std::hash<> 템플릿 특수화를 수행하지 못하여 발생한 오류이다.

참고로 C++은 몇가지 타입에 대해서는 미리 정의된 std::hash<> 템플릿이 존재한다.

std::hash가 특수화로 지원하는 타입은 다음과 같다.

C++에서&nbsp; std::hash 템플릿 특수화를 지원하는 타입

std::hash<> 특수화 추가 정의하기

std::set<pair<int,int>>을 Key로 사용하는 std::unordered_map을 생성하려고 한다.

std::unordered_map<std::set<pair<int,int>>, int > temp;

std::hash< std::set<pair<int,int>>> 를 정의해주지 않았기 때문에 컴파일 에러가 발생할 것이다.

따라서 std::hash< std::set<pair<int,int>>> 를 정의해보자.

아래 코드는 VS에서 제공하는 Hash 기법을 사용하여 정의하였다.

namespace std
{
	template<>
	struct hash<set<pair<int, int>>>
	{
		size_t operator()(const set<pair<int, int>>& other) const noexcept
		{

			return ArrayHasher(14695981039346656037ULL, other);
		}

		inline size_t ArrayHasher(size_t _Val, const set<pair<int, int>>& other) const noexcept
		{
			for (const auto& it : other)
			{
				_Val ^= static_cast<size_t>(it.first ^ it.second);
				_Val *= 1099511628211ULL;
			}

			return _Val;
		}
	};
}

int main()
{
	unordered_map<set<pair<int, int>>, int> myUmap;
    set<pair<int, int>> mySet;
    
    mySet.insert(make_pair(3, 5));
    myUmap[mySet]++;
}

위와 같이 namespace std에 직접 std::hash<> 특수화를 정의하면,
std::unordered_map에 Hash를 직접 전달하지 않아도 된다.

또는 아래와 같이 std::unordered_map의 Hash인자로 함수 객체를 명시적으로 전달해도 된다.

struct CustomedHasher
{
	size_t operator()(const set<pair<int, int>>& other) const noexcept
	{
		// 숫자 14695981039346656037 : Hash 충돌 최소화 하면서 성능을 극대화하기 위해 사용 됨
		return ArrayHasher(14695981039346656037ULL, other);
	}

	inline size_t ArrayHasher(size_t _Val, const set<pair<int, int>>& other) const noexcept
	{
		for (const auto& it : other)
		{
			_Val ^= static_cast<size_t>(it.first ^ it.second);
            // 숫자 1099511628211 : Hash 충돌 최소화 하면서 성능을 극대화하기 위해 사용 됨
			_Val *= 1099511628211ULL; 
		}

		return _Val;
	}
};

int main()
{
	unordered_map<set<pair<int, int>>, int, CustomedHasher> myUmap;
    set<pair<int, int>> mySet;
    
    mySet.insert(make_pair(3, 5));
    myUmap[mySet]++;
}

 

해시 함수 입력 값이 배열이 아닌 경우 다음과 같이 간단하게 만들 수 있음

struct CustomedHasher
{
	size_t operator()(const pair<int, int>& other) const noexcept
	{
		size_t _Val = 14695981039346656037ULL; //offset-basis
		_Val ^= static_cast<size_t>(other.first);
		_Val ^= static_cast<size_t>(other.second);
		_Val *= 1099511628211ULL; // prime

		return _Val;
	}
};

해시 충돌 최소화

struct PoorHasher {
	std::size_t operator()(const std::set<pair<int, int>>& set) const noexcept {
		return std::size_t x1{ std::hash<size_t>{}(set.size()) };
	}
};

누군가의 코드를 봤는데 Hash를 위와 같이 정의해서 전달하더라...

set.size()가 같으면 해시 충돌이 발생할 수 밖에 없다.

std::hash 구현 요구 사항에도 보면 충돌 확률을 1 / 2^64만큼으로 줄이라고 되어 있다.

CustomedHaser에 보면 알 수 없이 긴 숫자가 충돌 최소화 & 성능 극대화 역할을 돕는다.


PoorHasher의 세번째 줄에 std::hash<size_t>{} 뒤에 (set.size()) 가 붙어있는데 이것이 바로
함수 객체 역할을 하는 std::hash가 가지고 있어야할 operator() 함수이다. 

잘 모르고 보면 std::hash<size_t>에 대한 직접 초기화 문법 뒤에
이상하게 (set.size())가 붙어있어서 당황할 수 있다고 생각해서
적어보았다.

std::size_t x1{ std::hash<size_t>{}(set.size()) }; 코드는 아래 코드를 줄인 것이다.

auto hash = std::hash<size_t>{};
std::size_t x1 { hash(set.size()) };  // hash의 operator()를 호출한 것

VS에서 제공하는 std::hash 특수화 관련

// These FNV-1a utility functions are extremely performance sensitive,
// check examples like that in VSO-653642 before making changes.
#if defined(_WIN64)
_INLINE_VAR constexpr size_t _FNV_offset_basis = 14695981039346656037ULL;
_INLINE_VAR constexpr size_t _FNV_prime        = 1099511628211ULL;
#else // defined(_WIN64)
_INLINE_VAR constexpr size_t _FNV_offset_basis = 2166136261U;
_INLINE_VAR constexpr size_t _FNV_prime        = 16777619U;
#endif // defined(_WIN64)

// 배열 형태의 자료구조를 해싱하기
_NODISCARD inline size_t _Fnv1a_append_bytes(size_t _Val, const unsigned char* const _First,
    const size_t _Count) noexcept { // accumulate range [_First, _First + _Count) into partial FNV-1a hash _Val
    for (size_t _Idx = 0; _Idx < _Count; ++_Idx) {
        _Val ^= static_cast<size_t>(_First[_Idx]);
        _Val *= _FNV_prime;
    }

    return _Val;
}

template <class _Ty>
_NODISCARD size_t _Fnv1a_append_range(const size_t _Val, const _Ty* const _First,
    const _Ty* const _Last) noexcept { // accumulate range [_First, _Last) into partial FNV-1a hash _Val
    static_assert(is_trivial_v<_Ty>, "Only trivial types can be directly hashed.");
    const auto _Firstb = reinterpret_cast<const unsigned char*>(_First);
    const auto _Lastb  = reinterpret_cast<const unsigned char*>(_Last);
    return _Fnv1a_append_bytes(_Val, _Firstb, static_cast<size_t>(_Lastb - _Firstb));
}

template <class _Kty>
_NODISCARD size_t _Fnv1a_append_value(
    const size_t _Val, const _Kty& _Keyval) noexcept { // accumulate _Keyval into partial FNV-1a hash _Val
    static_assert(is_trivial_v<_Kty>, "Only trivial types can be directly hashed.");
    return _Fnv1a_append_bytes(_Val, &reinterpret_cast<const unsigned char&>(_Keyval), sizeof(_Kty));
}

template <class _Kty>
_NODISCARD size_t _Hash_representation(const _Kty& _Keyval) noexcept { // bitwise hashes the representation of a key
    return _Fnv1a_append_value(_FNV_offset_basis, _Keyval);
}

template <class _Kty>
_NODISCARD size_t _Hash_array_representation(
    const _Kty* const _First, const size_t _Count) noexcept { // bitwise hashes the representation of an array
    static_assert(is_trivial_v<_Kty>, "Only trivial types can be directly hashed.");
    return _Fnv1a_append_bytes(
        _FNV_offset_basis, reinterpret_cast<const unsigned char*>(_First), _Count * sizeof(_Kty));
}

template <class _Kty>
struct hash;

template <class _Kty, bool _Enabled>
struct _Conditionally_enabled_hash { // conditionally enabled hash base
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Kty _ARGUMENT_TYPE_NAME;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef size_t _RESULT_TYPE_NAME;

    _NODISCARD size_t operator()(const _Kty& _Keyval) const
        noexcept(noexcept(hash<_Kty>::_Do_hash(_Keyval))) /* strengthened */ {
        return hash<_Kty>::_Do_hash(_Keyval);
    }
};

template <class _Kty>
struct _Conditionally_enabled_hash<_Kty, false> { // conditionally disabled hash base
    _Conditionally_enabled_hash()                                   = delete;
    _Conditionally_enabled_hash(const _Conditionally_enabled_hash&) = delete;
    _Conditionally_enabled_hash(_Conditionally_enabled_hash&&)      = delete;
    _Conditionally_enabled_hash& operator=(const _Conditionally_enabled_hash&) = delete;
    _Conditionally_enabled_hash& operator=(_Conditionally_enabled_hash&&) = delete;
};

template <class _Kty>
struct hash
    : _Conditionally_enabled_hash<_Kty,
          !is_const_v<_Kty> && !is_volatile_v<_Kty> && (is_enum_v<_Kty> || is_integral_v<_Kty> || is_pointer_v<_Kty>)> {
    // hash functor primary template (handles enums, integrals, and pointers)
    static size_t _Do_hash(const _Kty& _Keyval) noexcept {
        return _Hash_representation(_Keyval);
    }
};

template <>
struct hash<float> {
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef float _ARGUMENT_TYPE_NAME;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef size_t _RESULT_TYPE_NAME;
    _NODISCARD size_t operator()(const float _Keyval) const noexcept {
        return _Hash_representation(_Keyval == 0.0F ? 0.0F : _Keyval); // map -0 to 0
    }
};

template <>
struct hash<double> {
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef double _ARGUMENT_TYPE_NAME;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef size_t _RESULT_TYPE_NAME;
    _NODISCARD size_t operator()(const double _Keyval) const noexcept {
        return _Hash_representation(_Keyval == 0.0 ? 0.0 : _Keyval); // map -0 to 0
    }
};

template <>
struct hash<long double> {
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef long double _ARGUMENT_TYPE_NAME;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef size_t _RESULT_TYPE_NAME;
    _NODISCARD size_t operator()(const long double _Keyval) const noexcept {
        return _Hash_representation(_Keyval == 0.0L ? 0.0L : _Keyval); // map -0 to 0
    }
};

template <>
struct hash<nullptr_t> {
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef nullptr_t _ARGUMENT_TYPE_NAME;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef size_t _RESULT_TYPE_NAME;
    _NODISCARD size_t operator()(nullptr_t) const noexcept {
        void* _Null{};
        return _Hash_representation(_Null);
    }
};