微网站怎么做微名片,wordpress如何分页,代理服务器地址列表,杭州开发公司位图
概念
用一个bit为来标识数据在不在
功能
节省空间快速查找一个数在不在一个集合中排序 去重求两个集合的交集,并集操作系统中的磁盘标记
简单实现
1.设计思想:一个bit位标识一个数据, 使用char(8bit位)集合来模拟
2.预备工作:a.计算这个数在第几个char b.是这个ch…位图
概念
用一个bit为来标识数据在不在
功能
节省空间快速查找一个数在不在一个集合中排序 去重求两个集合的交集,并集操作系统中的磁盘标记
简单实现
1.设计思想:一个bit位标识一个数据, 使用char(8bit位)集合来模拟
2.预备工作:a.计算这个数在第几个char b.是这个char的第几个bit位 第i个char: num/8 第j个bit位: num%8
3.操作:放数据, 删数据, 判断数据在不在
set :将对应的bit位置为1 ~~ 标识数据存在 _bit[i] | (1j) reset:将对应的bit位置为0 ~~标识数据不存在 _bit[i] ~(1j) test :查看该bit位是不是位1~~查看数据在不在 _bit[i] (1j)
set的实现:让对应bit位置1,其它位不变. 让该位 | 上1 , 其它位 | 上0
rest的实现:让对应bit位置1,其它位不变. 让该位 上0, 其它位 上1
test的实现:让对应位上1 4.代码
namespace code
{templatesize_t Nclass bitset{public:bitset(){_bits.resize(N/81,0);}//将指定的位置为1void set(size_t x){int i x / 8;int j x % 8;_bits[i] | (1 j);}//将指定的位置为0void reset(size_t x){int i x / 8;int j x % 8;_bits[i] ~(1 j);}//查看数字在不在bool test(size_t x){int i x / 8;int j x % 8;return _bits[i] (1 j);}private:vectorchar _bits;};
}
布隆过滤器
概念
用多个bit位标识数据在不在(可以映射非整型数据)
功能
布隆过滤器常用于缓存控制、拼写检查、恶意网址过滤等场景能够快速且高效地过滤掉大部分不必要的元素
简单实现
1.复用位图
2.提供多个仿函数,将非整型数据转换为整型, 并映射到不同的位置
3.置为1:根据计算出的位置将其置为1 在不在:映射的多个位置都为1表示在
4.代码 struct BKDRHash{size_t operator()(const string s){size_t hash 0;for (auto ch : s){hash ch;hash * 31;}return hash;}};struct APHash{size_t operator()(const string s){size_t hash 0;for (long i 0; i s.size(); i){size_t ch s[i];if ((i 1) 0){hash ^ ((hash 7) ^ ch ^ (hash 3));}else{hash ^ (~((hash 11) ^ ch ^ (hash 5)));}}return hash;}};struct DJBHash{size_t operator()(const string s){size_t hash 5381;for (auto ch : s){hash (hash 5) ch;}return hash;}};// N最多会插入key数据的个数templatesize_t N,class K string,class Hash1 BKDRHash,class Hash2 APHash,class Hash3 DJBHashclass BloomFilter{public://根据hash函数计算出的位置,将其置为1void set(const K key){size_t len N * _X;size_t hash1 Hash1()(key) % len;_bs.set(hash1);size_t hash2 Hash2()(key) % len;_bs.set(hash2);size_t hash3 Hash3()(key) % len;_bs.set(hash3);}//所有映射的位置都为1才表示在// 在 不准确的存在误判// 不在 准确的bool test(const K key){size_t len N * _X;size_t hash1 Hash1()(key) % len;if (!_bs.test(hash1)){return false;}size_t hash2 Hash2()(key) % len;if (!_bs.test(hash2)){return false;}size_t hash3 Hash3()(key) % len;if (!_bs.test(hash3)){return false;}return true;}private:static const size_t _X 6;bitsetN* _X _bs;};
