std::bitset哈希函数算法

Question

std::bitset哈希函数算法

6

有人知道bitset哈希函数使用的算法吗？

这来自于网站：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

而且为什么不将比特转换为无符号长整型并生成哈希值？

- JimBamFeng

7

C++标准没有规定任何特定的算法。如果你想了解你所使用的C++库具体做了什么，你可以查看其源代码，或者使用调试器进行步入调试。 - Igor Tandetnik

这就是为什么g++和clang++会给出不同的结果，...，它是否可以修改？ - JimBamFeng

3

您的问题是您实际上想要最小化取决于std::bitfield大小的值吗？也许是因为您想通过MPI发送它们。请在提问时提供完整的使用案例和背景信息，不要让我从您的个人资料中去猜测这一切。同时，请不要称那些花费自愿时间帮助您解决问题的人为“傲慢”。 - πάντα ῥεῖ

@DrJ 总的来说，这是一个有趣的问题。 - πάντα ῥεῖ

好的，谢谢澄清，谢谢。 - JimBamFeng

1

@DrJ，我希望设置赏金对你有所帮助。 - πάντα ῥεῖ

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- osgx · Accepted Answer

根据Igor的注释，C++标准没有指定算法，它仅要求哈希值仅依赖于对象，并且在程序运行期间保持不变：http://eel.is/c++draft/hash.requirements。

20.5.3.4 哈希要求 [hash.requirements] 1 如果类型H满足以下条件，则类型H符合哈希要求:

(1.1) 它是一个函数对象类型

(1.2) 它满足可复制构造和可销毁的要求

(1.3) 表29中显示的表达式有效并具有指示的语义。

2 给定Key是类型H的函数对象的参数类型，在表29中，h是类型(可能是const) H的值，u是类型Key的左值，k是可转换为(可能是const) Key的类型的值。

表29 - 哈希要求

表达式返回类型要求

h(k) size_t 返回值仅取决于程序期间的参数k。[注意：因此，对于程序的给定执行，具有相同k值的所有h(k)表达式的评估都产生相同的结果。-end note] [注意：对于两个不同的值t1和t2，使得h(t1)和h(t2)比较相等的概率应该非常小，接近于1.0 / numeric_limits::max()。-end note]

h(u) size_t 不得修改u。

Gcc的libstdc++实现使用std::hash的bitset：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使用自己的实现方式来处理bitset，将所有的单词进行异或操作：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;
}

并且对于一个单词的位集，有一个更简单的变体:

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