hash_value/hash_combine 在干什么

hash_value 定义

1) basic_numbers

template <typename T>
typename boost::hash_detail::basic_numbers<T>::type hash_value(T v)
{
    return static_cast<std::size_t>(v);
}

2) string

template <class Ch, class A>
inline std::size_t hash_value(
    std::basic_string<Ch, std::BOOST_HASH_CHAR_TRAITS<Ch>, A> const& v)
{
    return hash_range(v.begin(), v.end());
}

3) hash_range

template <class It>
inline std::size_t hash_range(It first, It last)
{
    std::size_t seed = 0;

    for(; first != last; ++first)
    {
        hash_combine(seed, *first);
    }

    return seed;
}

---

试验一下 ¹

#include <boost/functional/hash.hpp>
#include <boost/assert.hpp>

int main() {
    using boost::hash_value;

    int i = 3;
    std::size_t hash_value_i = hash_value(i);
    BOOST_ASSERT(i == hash_value_i);
}

其中 basic_numbers 包括:

template <> struct basic_numbers<bool> :
    boost::hash_detail::enable_hash_value {};
template <> struct basic_numbers<char> :
    boost::hash_detail::enable_hash_value {};
template <> struct basic_numbers<unsigned char> :
    boost::hash_detail::enable_hash_value {};
template <> struct basic_numbers<signed char> :
    boost::hash_detail::enable_hash_value {};
template <> struct basic_numbers<short> :
    boost::hash_detail::enable_hash_value {};
template <> struct basic_numbers<unsigned short> :
    boost::hash_detail::enable_hash_value {};
template <> struct basic_numbers<int> :
    boost::hash_detail::enable_hash_value {};
template <> struct basic_numbers<unsigned int> :
    boost::hash_detail::enable_hash_value {};
template <> struct basic_numbers<long> :
    boost::hash_detail::enable_hash_value {};
template <> struct basic_numbers<unsigned long> :
    boost::hash_detail::enable_hash_value {};

---

hash_combine

template <class T>
inline void hash_combine(std::size_t& seed, T const& v)
{
    boost::hash<T> hasher;

    return boost::hash_detail::hash_combine_impl(seed, hasher(v));
}

其中 boost::hash<T>

    template <class T> struct hash
        : boost::hash_detail::hash_base<T>
    {
#if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)
        std::size_t operator()(T const& val) const
        {
            return hash_value(val);
        }
#else
        std::size_t operator()(T const& val) const
        {
            return hash_detail::call_hash<T>::call(val);
        }
#endif
    };

hash_base

struct hash_base : std::unary_function<T, std::size_t> {};

hash_combine_impl 在干什么

template <typename SizeT>
inline void hash_combine_impl(SizeT& seed, SizeT value)
{
    seed ^= value + 0x9e3779b9 + (seed<<6) + (seed>>2);
}

• When using boost::hash_combine the order of the calls matters.
• Called repeatedly to incrementally create a hash value from several variables.

---

1. assert . ↩