布隆过滤器(BloomFilter)

admin

世界杯决赛直播

2025-10-01 18:21:57

背景在平常生活中，包括在设计计算机软件时，我们经常要判断一个元素是否在一个集合中。

比如在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上；在网络爬虫里，一个网址是否被访问过等等。

最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新元素时，将它和集合中的元素直接比较即可。一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的好处是快速准确，缺点是浪费存储空间。那有没有更优化的数据结构呢？

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是由一个很长的bit数组和一系列哈希函数组成的。布隆过滤器可以用于检索一个元素是否在一个集合中。

原理数组的每个元素都只占1bit空间，并且每个元素只能为0或1。

布隆过滤器还拥有k个哈希函数，当一个元素加入布隆过滤器时，会使用k个哈希函数对其进行k次计算,得到k个哈希值，并且根据得到的哈希值，在维数组中把对应下标的值置位1。

判断某个数是否在布隆过滤器中，就对该元素进行k次哈希计算，得到的值在位数组中判断每个元素是否都为1，如果每个元素都为1，就说明这个值在布隆过滤器中。

False positivies 概率误差率布隆过滤器的误差率是指由于hash冲突，导致原本不再布隆过滤器中的数据，查询时显示在里面

初始化

插入geeks单词

插入nerd单词

查询 cat 单词

发现1,3,7号位均为1,此时需要去后台数查询

推导假设Hash函数以等概率条件选择并设置Bit Array中的某一位.

m是该位数组的大小,

k是 Hash 函数的个数

那么位数组中某一特定的位在进行元素Hash操作中没有被置位1的概率是: $1-\frac{1}{m}$

那么在所有k次 Hash 操作后该位都没有被置1的概率是: $(1-\frac{1}{m})^{k}$

如果我们插入了n个元素，那么某一位仍然为0的概率是: $(1-\frac{1}{m})^{kn}$

因而该位为1的概率是: $1-(1-\frac{1}{m})^{kn}$

现在检测某一元素是否在该集合中。标明某个元素是否在集合中所需的 k 个位置都按照如上的方法设置为1，但是该方法可能会使算法错误的认为某一原本不在集合中的元素却被检测为在该集合中（假阳性），该概率由以下公式确定：

\[\lbrack1-(1-\frac{1}{m})^{kn}\rbrack^{k}\approx(1-e^{-\frac{kn}{m}})^{k}\]

不难看出，随着m（位数组大小）的增加，假阳性（False Positives）的概率会下降，同时随着插入元素个数 n 的增加，假阳性（False Positives）的概率又会上升。

对于给定的m,n。如何选择Hash函数个数k？由以下公式确定

Hash函数选定上文提及误差率主要是由于hash冲突导致的，所以选定一个好的hash函数至关重要。

本文囊括了常见的hash函数，并从时间和冲突率统计各类hash函数测试结果

测试数据随机字符串 : 约 1000000模拟app账号：2～28 个字符，约 45000视频素材主键：1～9 个字符的整型，约 40000测试结果-随机字符哈希函数时间(ns)冲突个数总个数SDBMHash1580628971801000000SimMurMurHash1443562921081000000JSHash1608295232301000000PJW16914242139011000000MurMurHash21446789731291000000ELFHash17396607539011000000BKDRHash1605170552581000000CalcNrHash1804258431241000000APHash1666443692451000000BPHash1446470919200051000000FNVHash1605848601091000000RSHash1603164682401000000DJB185411123971000000DJB2Hash151799803971000000DEKHash1458567521191000000SipHashNoCase2059301991261000000SipHash1879726391261000000

测试结果-视频素材主键哈希函数时间(ns)冲突个数总个数SDBMHash1527902040000SimMurMurHash1346732040000JSHash1575731040000PJW14824113840000MurMurHash21396543040000ELFHash15164433840000BKDRHash1568576040000CalcNrHash1900336140000APHash1631107040000BPHash1388693922740000FNVHash1540261140000RSHash1547968040000DJB1969460040000DJB2Hash1438242140000DEKHash13596232540000SipHashNoCase1727340040000SipHash1480105040000

模拟app账号哈希函数时间(ns)冲突个数总个数SDBMHash1900195145402SimMurMurHash1949347045402JSHash1904775545402PJW202621717045402MurMurHash21937634045402ELFHash204795417045402BKDRHash1905460045402CalcNrHash2084442045402APHash1961953145402BPHash18935232925345402FNVHash1888491045402RSHash1929489045402DJB23515293045402DJB2Hash1867887045402DEKHash18610011745402SipHashNoCase22919592945402SipHash2037517045402

最终我们选择了 MurMurHash2

BloomFilter 实战\[\frac{m}{n}\ln{2}\approx0.7\frac{m}{n}\]实现部分 1

class BloomFilterPolicy final : public FilterPolicy {

public:

explicit BloomFilterPolicy(int bits_per_key) : bits_per_key_(bits_per_key) {

// We intentionally round down to reduce probing cost a little bit

k_ = static_cast(bits_per_key * 0.69); // 0.69 =~ ln(2)

if (k_ < 1) k_ = 1;

if (k_ > 30) k_ = 30;

}

const char* Name() const override { return "BloomFilter2"; }

/***

* BloomFilter 生成放置到 ${dst} 中

* @param keys

* @param n

* @param dst

void CreateFilter(const std::string* keys, int n,

std::string* dst) override {

/***

* 计算需要多少字节来存储这些 key 的bloom filter 标识

size_t bits = n * bits_per_key_;

if (bits < 64) bits = 64;

size_t bytes = (bits + 7) / 8;

bits = bytes * 8; // 向上对齐

/***

* 初始化 BloomFilter 位, 置空

const size_t init_size = dst->size(); // 获取原始大小

dst->resize(init_size + bytes, 0); // 扩大新的位大小，并且填空新的元素为 0[初始化 bloom 过滤器]

dst->push_back(static_cast(k_)); // 将最后一位存放这个过滤器用了多少个 hash 函数

char* array = &(*dst)[init_size]; // 获取到 bloom 过滤器的首部位置

/***

* 设置每个key的BloomFilter位

for (int i = 0; i < n; i++) {

// 获取 key 的 hash 值

uint32_t h = hash_func_.MurMurHash2(keys[i].c_str(), keys[i].size());

// 高低位转换 : 17 + 15 = 32, 用与 hash 偏移因子

const uint32_t delta = (h >> 17) | (h << 15);

for (size_t j = 0; j < k_; j++) { // k 个hash 函数

// 取bits有效值，并设置对应位为1

const uint32_t bitpos = h % bits;

array[bitpos / 8] |= (1 << (bitpos % 8));

h += delta; // hash 偏移

}

/**

* Bloom 过滤器校验

* @param key 用户校验的key

* @param bloom_filter 存放的bloom 过滤器值

* @return

bool KeyMayMatch(const std::string& key,

const std::string& bloom_filter) override {

/***

* 获取 bloom 过滤器的长度

const size_t len = bloom_filter.size();

if (len < 2) return false;

const char* array = bloom_filter.data();

const size_t bits = (len - 1) * 8;

// 获得有多少个 hash 函数，最多30个

const size_t k = array[len - 1];

if (k > 30) {

return true;

}

uint32_t h = hash_func_.MurMurHash2(key.c_str(), key.size());

const uint32_t delta = (h >> 17) | (h << 15); // Rotate right 17 bits

for (size_t j = 0; j < k; j++) {

const uint32_t bitpos = h % bits;

if ((array[bitpos / 8] & (1 << (bitpos % 8))) == 0) return false;

h += delta;

}

return true;

}

private:

size_t bits_per_key_; // 预估每个key大概需要多少位可以存储

size_t k_; // k 个 hash 函数, 默认 30 个

HashFunc hash_func_; // hash 函数

};

测试程序 1

class BloomTest final {

public:

BloomTest(uint32_t bit_per_key = 10)

: policy_(std::make_unique(bit_per_key)) {}

~BloomTest() {}

void Reset() {

keys_.clear();

filter_.clear();

}

void SetData(std::vector&& keys) { keys_ = std::move(keys); }

void SetData(const std::vector& keys) { keys_ = (keys); }

void Add(const std::string& s) { keys_.emplace_back(s); }

void Build() {

filter_.clear();

policy_->CreateFilter(&keys_[0], static_cast(keys_.size()), &filter_);

keys_.clear();

}

size_t FilterSize() const { return filter_.size(); }

bool Matches(const std::string& s) {

if (!keys_.empty()) {

Build();

}

return policy_->KeyMayMatch(s, filter_);

}

double FalsePositiveRate(const std::vector& data) {

double result = 0;

for (const auto& item : data) {

if (Matches(item)) {

result++;

}

return result / 10000.0;

}

double FalsePositiveRate(const std::string& data) {

double result = 0;

{

if (Matches(data)) {

result++;

}

return result / 10000.0;

}

private:

std::unique_ptr policy_;

std::string filter_;

std::vector keys_;

};

结果统计bit_per_key = 10 数据集原始数据空间占用bf空间占用空间压缩比误差率(/万)视频素材主键7105191000010.85925640.0827模拟app账号363646567540.84393064 bit_per_key = 15 数据集原始数据空间占用bf空间占用空间压缩比误差率(/万)视频素材主键7105191500010.788885310.0074模拟app账号363646851300.7658987 bit_per_key = 20 数据集原始数据空间占用bf空间占用空间压缩比误差率(/万)视频素材主键7105192000010.718514210.0006模拟app账号3636461135060.68786677 结尾使用场景黑名单校验快速去重爬虫URL校验leveldb/rocksdb快速判断数据是否已经block中，避免频繁访问磁盘解决缓存穿透问题缓存穿透缓存穿透是指查询一个数据库中不一定存在的数据.

正常流程是依据key去查询value，数据查询先进行缓存查询，如果key不存在或者key已经过期，再对数据库进行查询,并把查询到的对象，放进缓存。

如果数据库查询对象为空，则不放进缓存。

如果每次都查询一个不存在value的key，由于缓存中没有数据，所以每次都会去查询数据库，对db造成很大的压力。

构建方法使用redis的module加载外部so文件优点：操作简单缺点：需要高版本的redis容易形成大key借助bitmap来实现，k个hash函数，创建n个bitmap(推荐)优点：操作简单缺点：由于redis的字符串要求最大为512M，所以需要拆分多个key扩容稍微复杂可以自己本地来实现布隆过滤器的计算，计算完之后在存入redis优点：自己操作更灵活缺点：流程复杂需要额外服务重启或当机之后布隆过滤器丢失问题优点节省内存空间插入和查询时间复杂度都为O(1)缺点布隆过滤器不支持删除由于哈希冲突的原因，可能会出现假阳性思考布隆过滤器多适用于数据更新较少的场景，如果海量数据模式下，数据量又频繁变化，如何高效构建布隆过滤器呢？布隆过滤器如何支持删除操作呢？计数布隆过滤器布谷鸟过滤器转载内容 :

硬核课堂-布隆过滤器gai

布隆过滤器(BloomFilter)

Other Articles

qq网页版登录入口（电脑版qq登录方法）