一、概念
1.1 简介
布隆过滤器（Bloom Filter）是1970年由
布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。
- 可用于
检索一个元素是否在一个集合中；- 优点：
空间效率和查询时间都远远超过一般的算法；- 缺点：有一定的
误识别率和删除困难；
1.2 原理
当元素被加入到集合内部，通过
K个散列函数将改元素映射成一个位数组中的K个点，且将其置为1；当我们检索元素时，只需通过散列函数查看这些点是否为1即可，若其中任意一点为0，则即可判断一定不在集合里面；
- 【注意】：若检索都为1，只能说
很可能在集合内部。因为集合具有一定的误识别率，需要通过结合集合的大小以及散列函数的个数来降低错误率；
1.3 复杂度
时间复杂度:
插入以及查询 ==》常数
O(k)；
1.4 使用步骤
- 需要先确定布隆过滤器的元素需要多少位；
- 确定集合需要多少空间【m】，根据提供的失误率【p】和样本数量【n】得出；
- 通过样本数量即空间大小【m】确定出使用散列函数个数【k】；
- 计算真实失误率【p】；
ln2 近似为0.7
p、m、k之间的关系
- 当样本量n不变时，此时集合
空间m越大，则失误率越低；- 当样本量、空间不变时，当
k较小时，会导致散列的点分布较少，即可能出现局部密集的点，导致失误率降低，若k较大时，会出现在在整个空间内密集，从而降低失误率，故k需要选择一个较为合适的大小；
1.5 扩展和应用
黑名单系统：
缓存过滤：
网络部署
Web缓存以更高的性能和可靠性缓存并为用户提供 Web 内容；
- 用于有效地确定将哪些Web 对象存储在这些 Web 缓存中。访问一次，后续不在访问的用户缓存显然是
浪费磁盘资源，因为它将不会被再次访问。即用于跟踪用户访问的所有 URL。Web 对象仅在之前至少被访问过一次时才被缓存，即对象在其第二次请求时被缓存。减少了磁盘写入工作量。此外，节省磁盘上的缓存空间，从而提高缓存命中率；
分布式过滤器
可以实现并行布隆过滤器以利用
并行无共享机器中存在的多个处理元素(PE) ；
- 并行布隆过滤器的主要障碍之一是
无序数据的组织和通信，通常在启动或批量插入时均匀分布在所有 PE 上。要对数据进行排序，可以使用两种方法，一种是对存储在每个 PE 上的所有数据进行布隆过滤器，称为复制布隆过滤器，或者对所有数据进行布隆过滤器分成相等的部分，每个 PE 存储它的一部分对于这两种方法，都使用“Single Shot”布隆过滤器，它只计算一个哈希，导致每个元素一个翻转位，以减少通信量；
二、简单模拟构建bit数组
/*----------------------------------------------------------------------
> File Name: bitMap.cpp
> Author: Jxiepc
> Mail: Jxiepc
> Created Time: Thu 03 Mar 2022 11:14:50 AM CST
----------------------------------------------------------------------*/
#include <iostream>
template<class T>
class bitMap {
public:
bitMap() {
T a;
bitNum(a);
}
/** 数据类型的bit */
int bitNum(T a) {
std::cout << sizeof(a) * 8 << std::endl;
return sizeof(a) * 8;
}
/** 要取出的bit数，对应列表中的哪个数值 */
void setNumIdx(T bit) const {
numIdx = bit/m_bit;
}
int getNumIdx(T bit) {
return numIdx;
}
/** 取出的bit数种，对应列表中数值的哪一位上 */
void setbitIdx(T bit) const {
bitIdx = bit % m_bit;
}
int getbitIdx() {
return bitIdx;
}
/** 取出该位的状态 */
int getStatus() {
return ((arr[numIdx] >> (bitIdx)) &1);
}
/** 设置状态为0 */
void setFalse() {
arr[numIdx] = arr[numIdx] & (~ (1 << bitIdx));
}
/** 设置状态为1 */
void setTrue() {
arr[numIdx] = arr[numIdx] | (1<<bitIdx);
}
private:
int m_bit = 0;
int numIdx = -1;
int bitIdx = -1;
T arr[];
};
int main(int argc, char* argv[])
{
return 0;
}