位图
概念
用一个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);
}
//将指定的位置为1
void set(size_t x)
{
int i = x / 8;
int j = x % 8;
_bits[i] |= (1 << j);
}
//将指定的位置为0
void 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函数计算出的位置,将其置为1
void 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;
};
