的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_; 
}