的std :: bitset的散列函数算法

Question

是否有人知道什么算法THW哈希函数位集使用，

这是从网站：http://en.cppreference.com/w/cpp/utility/bitset/hash

#include <iostream> 
#include <bitset> 
#include <functional> 

int main() 
{ 
    std::bitset<4> b1(1); 
    std::bitset<4> b2(2); 
    std::bitset<4> b3(b2); 
    std::bitset<4> b4(8); 
    std::cout<<b4<<'\n'; 
    std::hash<std::bitset<4>> hash_fn; 

    size_t h1 = hash_fn(b1); 
    size_t h2 = hash_fn(b2); 
    size_t h3 = hash_fn(b4); 

    std::cout << h1 << '\n'; 
    std::cout << h2 << '\n'; 
    std::cout << h3 << '\n'; 
} 

和输出

1000 
4334672815104069193 
16667047557902998627 
2258353126044249582 

http://en.cppreference.com/w/cpp/utility/bitset/hash

而且，为什么不把它转换ŧ他比特长，并生成一个哈希值？

Answer 1

作为noted by Igor，C++标准没有规定的算法，它onlyrequires该散列值只在对象依赖和将是相同的节目的持续时间：http://eel.is/c++draft/hash.requirements

20.5.3.4哈希要求[散列。要求] 1所述的H型满足哈希要求，如果：

• （1.1）是一个函数的对象类型，
• （1.2）它satisfi ES表29所示复制构造和可破坏，和
• （1.3） 表达式的要求是有效的，并具有指明的语义。

2给定Key是类型H的函数对象的参数类型，在表29中，h是类型（可能是const）H的值，u是类型为Key的左值，并且k是键入convertible（可能是const）键。

表29 - 哈希要求

• 表达式返回类型要求
• H（K）为size_t返回的值应在该程序的持续时间参数ķ仅依赖。 [注：因此， 表达H（K）与对于k产生相同的结果的程序的 给定执行相同的值的所有的评价。 - 注完] [注：对于两个不同 值t1和t2，使得h（t1）和H（T2）比较相等 应非常小的概率，接近1.0/ numeric_limits :: MAX（）。 - 注完]
• H（U）为size_t不得修改ü。

海湾合作委员会的libstdC++实现的bitset的使用的std ::哈希：https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/debug/bitset

#if __cplusplus >= 201103L 
    // DR 1182. 
    /// std::hash specialization for bitset. 
    template<size_t _Nb> 
    struct hash<__debug::bitset<_Nb>> 
    : public __hash_base<size_t, __debug::bitset<_Nb>> 
    { 
     size_t 
     operator()(const __debug::bitset<_Nb>& __b) const noexcept 
     { return std::hash<_GLIBCXX_STD_C::bitset<_Nb>>()(__b._M_base()); } 
    }; 
#endif 

https://github.com/gcc-mirror/gcc/blob/1cb6c2eb3b8361d850be8e8270c597270a1a7967/libstdc%2B%2B-v3/include/std/bitset#L1561

// DR 1182. 
    /// std::hash specialization for bitset. 
    template<size_t _Nb> 
    struct hash<_GLIBCXX_STD_C::bitset<_Nb>> 
    : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<_Nb>> 
    { 
     size_t 
     operator()(const _GLIBCXX_STD_C::bitset<_Nb>& __b) const noexcept 
     { 
     const size_t __clength = (_Nb + __CHAR_BIT__ - 1)/__CHAR_BIT__; 
     return std::_Hash_impl::hash(__b._M_getdata(), __clength); 
     } 
    }; 

LLVM的libcxx使用自己的实现为位集，异或所有的词：https://github.com/llvm-mirror/libcxx/blob/2c4b8af9aada61d83610330416eb8a39a8aa5494/include/bitset#L417

template <size_t _Size> 
struct _LIBCPP_TEMPLATE_VIS hash<bitset<_Size> > 
    : public unary_function<bitset<_Size>, size_t> 
{ 
    _LIBCPP_INLINE_VISIBILITY 
    size_t operator()(const bitset<_Size>& __bs) const _NOEXCEPT 
     {return __bs.__hash_code();} 
}; 

template <size_t _N_words, size_t _Size> 
inline 
size_t 
__bitset<_N_words, _Size>::__hash_code() const _NOEXCEPT 
{ 
    size_t __h = 0; 
    for (size_type __i = 0; __i < _N_words; ++__i) 
     __h ^= __first_[__i]; 
    return __h; 
} 

和更简单的变体为1个字位集：

inline 
size_t 
__bitset<1, _Size>::__hash_code() const _NOEXCEPT 
{ 
    return __first_; 
}