数据结构: 位图
位图
概念
用一个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] |= (1<<j)
- reset:将对应的bit位置为0 ~~>标识数据不存在 _bit[i] &= ~(1<<j)
- test :查看该bit位是不是位1~~>查看数据在不在 _bit[i] &= (1<<j)
set的实现:让对应bit位置1,其它位不变. 让该位 | 上1 , 其它位 | 上0
rest的实现:让对应bit位置1,其它位不变. 让该位 & 上0, 其它位 & 上1
test的实现:让对应位&上1
4.代码
namespace code
{template<size_t N>class bitset{public:bitset(){_bits.resize(N/8+1,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:vector<char> _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数据的个数template<size_t N,class K = string,class Hash1 = BKDRHash,class Hash2 = APHash,class Hash3 = DJBHash>class 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;bitset<N* _X> _bs;};