数据结构: 位图

位图

概念

用一个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;};