文章目录
- 位图
- 位图概念
- 位图使用场景
- 位图的结构
- 构造
- set
- reset
- test
- 完整代码
- 布隆过滤器
- 布隆过滤器概念
- 布隆过滤器结构
- 构造
- set
- reset
- test
- 完整版代码
位图
位图概念
所谓位图,就是用每一位来存放某种状态,适用于海量数据,数据无重复的场景。通常是用
来判断某个数据存不存在的。
位图使用场景
数据是否在给定的整形数据中,结果是在或者不在,刚好是两种状态
,那么可以使用一个二进制比特位来代表数据是否存在的信息,如果二进制比特位为1,代表存在,为0代表不存在
。
这就是位图的使用场景。
那么我们如何判断一个数在不再为图里面呢?
我们只要看这个某个数对应的bit位是不是1就好了。
那么我们如何在位图里删除一个数呢?
比如我们要删除1呢?
我们要删除一个数也是如此,直接把这个数对应的bit位置成0就好。
位图的结构
位图的模板参数和成员变量:
构造
set
reset
test
完整代码
#pragma once
#include<vector>
template<size_t N>
class BitSet
{
public:
BitSet()
{
_bits.resize(N / 8 + 1, 0);
}
void set(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_bits[i] |= (1 << j);
}
void reset(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_bits[i] &= (~(1 << j));
}
bool test(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
return _bits[i] & (1 << j);
}
private:
vector<char> _bits;
};
void testbitset()
{
BitSet<100> bs;
bs.set(10);
bs.set(15);
bs.set(20);
bs.set(31);
cout << bs.test(10) << endl;
cout << bs.test(11) << endl;
cout << bs.test(31) << endl;
}
布隆过滤器
我们在使用新闻客户端看新闻时,它会给我们不停地推荐新的内容,它每次推荐时要去重,去掉那些已经看过的内容。问题来了,新闻客户端推荐系统如何实现推送去重的? 用服务器记录了用户看过的所有历史记录,当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选,过滤掉那些已经存在的记录。 如何快速查找呢?
1. 用哈希表存储用户记录,缺点:浪费空间
2. 用位图存储用户记录,缺点:位图一般只能处理整形,如果内容编号是字符串,就无法处理了
3. 将哈希与位图结合,即布隆过滤器
布隆过滤器概念
布隆过滤器是由布隆(Burton Howard Bloom)在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构,特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”,它是用多个哈希函数,将一个数据映射到位图结构中
。此种方式不仅可以提升查询效率,也可以节省大量的内存空间。
布隆过滤器结构
三个效率较高哈希函数:
布隆过滤器的模板参数和成员变量:
其中N是要存的数据个数,X为碰撞因子,碰撞因子越大,误判概率越小。当然不是越大越好,越大空间浪费也会越大,所以要始终5~10皆可以。
构造
因为布隆过滤器是对位图的封装,所以可以不用实现构造函数。
set
一个值映射多个位置
reset
布隆过滤器不支持实现reset因为,会影响其它值的判断。
举个例子:
比如上图已经存在了一些字符串,如果我们把其中的bit删除了会怎么样?
我们这时候可以看到,bit已经删除了,left、reset和bit有一块共同的空间,bit被删除了,这个共同的空间也被置成0,那么下次我们要判断left和reset存不存在的时候就会出错。所以不能实现删除操作。
test
所有映射位置都为1,才能表示存在
完整版代码
#pragma once
#include <bitset>
#include <string>
#include <time.h>
struct BKDRHash
{
size_t operator()(const string& s)
{
// BKDR
size_t value = 0;
for (auto ch : s)
{
value *= 31;
value += ch;
}
return value;
}
};
struct APHash
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (long i = 0; i < s.size(); i++)
{
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
}
else
{
hash ^= (~((hash << 11) ^ s[i] ^ (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;
}
};
template<size_t N,
size_t X = 8,
class K = string,
class HashFunc1 = BKDRHash,
class HashFunc2 = APHash,
class HashFunc3 = DJBHash>
class BloomFilter
{
public:
void Set(const K& key)
{
size_t len = X * N;
size_t index1 = HashFunc1()(key) % len;
size_t index2 = HashFunc2()(key) % len;
size_t index3 = HashFunc3()(key) % len;
_bs.set(index1);
_bs.set(index2);
_bs.set(index3);
}
bool Test(const K& key)
{
size_t len = X * N;
size_t index1 = HashFunc1()(key) % len;
if (_bs.test(index1) == false)
return false;
size_t index2 = HashFunc2()(key) % len;
if (_bs.test(index2) == false)
return false;
size_t index3 = HashFunc3()(key) % len;
if (_bs.test(index3) == false)
return false;
return true; // е
}
private:
bitset<X* N> _bs;
};