c++ - 为 boost::dynamic_bitset 生成哈希并将哈希转换回 boost::dynamic_bitset

Question

我希望生成一个 boost::dynamic_bitset 散列，以便我可以将值存储在 boost::bimaps 中。我尝试了以下代码，Test code here.

#include <iostream>
#include <boost/dynamic_bitset.hpp>
#include <unordered_map>
#include <boost/bimap.hpp>
#include <boost/bimap/unordered_set_of.hpp>
#include <boost/bimap/unordered_multiset_of.hpp>
#include <boost/bimap/set_of.hpp>
#include <boost/bimap/multiset_of.hpp>

#define BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS

namespace boost {
    template <typename B, typename A>
    std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) {
        return boost::hash_value(bs.m_bits);
    }
    }

namespace bimaps = boost::bimaps;
typedef boost::bimap<bimaps::unordered_set_of<unsigned long long int>,
        bimaps::unordered_multiset_of<size_t> > bimap_reference;
typedef bimap_reference::value_type position;
bimap_reference reference_index_vector;

int main()
{

    std::string str = "1011010001101101000001101101000011111111011010000011011010000111111111110110100011011010000011011010000111111110110100000110110100001111111111";
    boost::dynamic_bitset<>  bits = boost::dynamic_bitset<> (str);
    std::cout << "bitmap " << bits << std::endl;
    std::cout << "Number of bits " << bits.count() << std::endl;

    size_t hash1 = boost::hash_value (bits);
    std::cout << "Hash value "  << hash1 << std::endl;


/* Insert hash value in bimap
 *
 */

//    reference_index_vector.insert(position(10000000000, hash1));
//    for( bimap_reference::const_iterator iter = reference_index_vector.begin(), iend = reference_index_vector.end();
//            iter != iend; ++iter ) {
//        std::cout << iter->left << " <--> "<< iter->right <<std::endl;
//    }

    return 0;
}

我得到了错误

In file included from /usr/include/boost/dynamic_bitset.hpp:15:0, from 3: In instantiation of 'std::size_t boost::hash_value(const boost::dynamic_bitset&) [with B = long unsigned int; A = std::allocator; std::size_t = long unsigned int]': 34:40: required from here /usr/include/boost/dynamic_bitset/dynamic_bitset.hpp:422:17: error: 'boost::dynamic_bitset<>::buffer_type boost::dynamic_bitset<>::m_bits' is private buffer_type m_bits; ^ 16:37: error: within this context

不确定出了什么问题。

1. 如何散列 boost::dynamic_bitset
2. 如何将散列转换回原始位集。
3. 所需的总空间(0 和 1 的计数或仅 1)。上面的代码仅通过 bits.count() 显示了 80 位。我尝试了以下方法来生成哈希值，但不确定需要多少空间。

另外，我尝试通过以下代码生成bitset的哈希值

/*Generating hash by bitset
     * 
     */
    std::bitset<142> seq (str);
    std::hash<std::bitset<142>> hash_bitset;
    std::cout << "Bitset " << seq << std::endl;
    std::cout << "Hash value " << hash_bitset(seq) << std::endl; 

    #Bitset 1011010001101101000001101101000011111111011010000011011010000111111111110110100011011010000011011010000111111110110100000110110100001111111111
    #Hash value 4886653603414440856

Answer 1

好的，我发现很多关于“散列”本质的混淆，所以一些友好的入门指南:

Q. 2. How to convert the hash back to orignial bitset.

那是不可能的。哈希是有损摘要。你只能在散列是 Perfect Hash 时这样做由于熵定律，如果位集容量超过 size_t 的大小，则不会发生这种情况。在您的平台上(通常为 32 或 64 位)。

Q. I also tried creating a hash by ...

 std::bitset<142> seq (str);
 ....

我希望你意识到std::bitset<>是一种完全不同的类型，所以它与任务并没有真正的关系。而且，由于它不是动态的，因此即使作为解决方法，它对任务也毫无帮助。

但最重要的是:

散列表使用散列(如 unordered_*<> )但它们不存储。哈希是有损摘要，仅用于在内部桶中获得良好的分布¹。对于实际元素相等，std::equal<T> 仍在使用。

换句话说:

typedef boost::bimap<bimaps::unordered_set_of<unsigned long long int>,
        bimaps::unordered_multiset_of<size_t> > bimap_reference;

不适合创建除 size_t 以外的任何 map 或 unsigned long long ².如果您在那里存储事物的哈希值:

reference_index_vector.insert(position(10000000000, hash1));

，你丢失了原始信息。无法从 hash1 获取位集.

编译错误

你的 hash_value实现错误地使用了 dynamic_bitset<> 的私有(private)成员.你不能，因为它不可访问。

这是 std::hash<> 的简单实现使用公共(public)接口(interface):

Live On Coliru

#include <boost/dynamic_bitset.hpp>
#include <boost/functional/hash.hpp>
#include <unordered_map>
#include <sstream>

namespace std {

    template <typename Block, typename Alloc> struct hash<boost::dynamic_bitset<Block, Alloc> > {
        size_t operator()(boost::dynamic_bitset<Block, Alloc> const& bs) const {
            size_t seed = boost::hash_value(bs.size());

            std::vector<Block> blocks(bs.num_blocks());
            boost::hash_range(seed, blocks.begin(), blocks.end());

            return seed;
        }
    };

}

int main() {
    boost::dynamic_bitset<> x, y;
    x.resize(rand()%100, 1);
    y.resize(rand()%100, 0);

    std::unordered_map<boost::dynamic_bitset<>, std::string> m;
    m[x] = "x";
    m[y] = "y";
}

您可以使用这个 std::hash<>改为特化并使用 boost::bimap用它。

注意，使用公共(public)接口(interface)不是最佳选择，因为它复制了 Block s(你也用 std::bitset<> hack 做到了)。您可能对我为 boost::dynamic_bitset<> 所做的 Boost 序列化实现感兴趣之前:

• How to serialize boost::dynamic_bitset?
• 这里的代码展示了如何使用序列化实现有效地实现哈希 Hash an arbitrary precision value (boost::multiprecision::cpp_int)

---

¹ 为简单起见，假设使用存储桶而不是“开放寻址”样式。同样的逻辑也适用于那里，但稍微复杂一些

²(顺便说一下，请说 uintmax_t 或 uint64_t )