我希望生成一个 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
不知道出了什么问题。
- 如何散列
boost::dynamic_bitset
- 如何将哈希值转换回原始位集。
- 所需的总空间(0 和 1 的计数或仅 1)。上面的代码仅通过
bits.count()
显示 80 位。我尝试了以下方法来生成哈希值,但不确定需要多少空间。
此外,我尝试通过以下代码生成位集的哈希值
/*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
最佳答案
好吧,我发现人们对“散列”的本质很困惑,所以有一些友好的入门指南:
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):
#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
(您也通过 std::bitset<>
hack 做到了这一点)。您可能对我为 boost::dynamic_bitset<>
所做的 Boost Serialization 实现感兴趣之前:
- How to serialize boost::dynamic_bitset?
- 下面的代码展示了如何使用序列化实现来有效地实现哈希 Hash an arbitrary precision value (boost::multiprecision::cpp_int)
为简单起见,假设使用存储桶而不是“开放寻址”样式。同样的逻辑也适用于此,但稍微复杂一些
²(顺便说一句,请直接说 uintmax_t
或 uint64_t
)
关于c++ - 为 boost::dynamic_bitset 生成哈希并将哈希转换回 boost::dynamic_bitset,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45914271/