のstd ::ビットセットのハッシュ関数アルゴリズム

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

また、なぜt彼は長い間unsigendとハッシュ値を生成するビット？値をハッシュ

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 CopyConstructibleとDestructibleの要件、および
• （1.3） 表29に示す式は有効であり、示されたセマンティクスを持っています。

2与えられたキーは、タイプHの関数オブジェクトの引数型であり、表29では、hは型（おそらくconst）の値であり、H、uはKey型のlvalueであり、kはa convertible（おそらくconst）キーをタイプします。

表29 - ハッシュ要件

• 返される値は、プログラムの継続期間の引数kにのみ依​​存するものSIZE_T式の戻り型要件
• H（K）
  。 [注：kの同じ値を持つ式h（k）のすべての評価は、プログラムが実行されたときに同じ結果を返します。 （注）2つの異なる の値t1とt2の場合、h（t1）とh（t2）が等しい を比較する確率は非常に小さく、1.0/ numeric_limits :: max（）に近づくはずです。 - 終了ノート]
• h（u）size_t uを変更しないでください。ビットセットの

GCCのにlibstdC++実装はSTDを使用しています::ハッシュ：https://github.com/llvm-mirror/libcxx/blob/2c4b8af9aada61d83610330416eb8a39a8aa5494/include/bitset#L417

： 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はすべての単語をXOR演算、ビットセットのための独自の実装を使用しています

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