16、哈希表与布隆过滤器：布隆过滤器原理、哈希函数在布隆过滤器中的作用、布隆过滤器的实现

一、从哈希表到布隆过滤器——我们遇到了什么问题？

讲布隆过滤器之前，我想先聊聊一个实际场景。

几年前我在做一个爬虫系统，需要判断一个URL是否已经被抓取过。用哈希表存？可以，但几亿个URL存进去，内存直接爆炸。用数据库？每次查询都要磁盘IO，速度跟不上。

这时候就需要一种「用少量错误率换大量内存」的数据结构。说白了，就是布隆过滤器。

布隆过滤器不是精确的数据结构。它可能会误判——把没见过的元素说成见过。但它绝不会漏判——见过的元素一定说见过。这个特性在很多场景下完全够用。

二、布隆过滤器的原理——一张图讲清楚

我习惯用一张图来理解布隆过滤器。你看下面这个结构：

你看，元素A、B、C分别通过3个哈希函数，在位数组上标记了多个位置。查询元素D时，虽然D没被插入过，但它哈希出来的位置恰好都被标记了——这就产生了误判。

三、哈希函数在布隆过滤器中的作用

哈希函数是布隆过滤器的灵魂。为什么这么说？

你想想看，如果哈希函数质量不好，不同元素算出来的位置高度重叠，那位数组很快就全变成1了——所有查询都返回「可能存在」，过滤器直接报废。

我常用的哈希函数有几种：

哈希函数	特点	适用场景
MurmurHash	速度快，分布均匀	通用场景，我最常用
FNV系列	实现简单，适合短字符串	URL去重、关键词过滤
CityHash	Google出品，对长字符串优化	大数据量场景
双哈希法	用两个哈希函数模拟k个	减少计算开销

四、布隆过滤器的实现——手写一个简易版

理论讲完了，咱们直接上代码。我习惯用C语言实现，因为能精确控制内存和位操作。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

// 布隆过滤器结构体
typedef struct {
    unsigned char *bits;   // 位数组
    int m;                 // 位数组大小（位）
    int k;                 // 哈希函数个数
    int n;                 // 已插入元素个数
} BloomFilter;

// 创建布隆过滤器
BloomFilter* bloom_create(int m, int k) {
    BloomFilter *bf = (BloomFilter*)malloc(sizeof(BloomFilter));
    bf->m = m;
    bf->k = k;
    bf->n = 0;
    // 位数组按字节分配，向上取整
    bf->bits = (unsigned char*)calloc((m + 7) / 8, 1);
    return bf;
}

// 设置某一位为1
void bloom_set_bit(BloomFilter *bf, int pos) {
    int byte_idx = pos / 8;
    int bit_idx = pos % 8;
    bf->bits[byte_idx] |= (1 << bit_idx);
}

// 检查某一位是否为1
int bloom_get_bit(BloomFilter *bf, int pos) {
    int byte_idx = pos / 8;
    int bit_idx = pos % 8;
    return (bf->bits[byte_idx] >> bit_idx) & 1;
}

// 简单的哈希函数（实际项目请用MurmurHash等）
uint32_t hash_func(const char *str, int seed) {
    uint32_t hash = seed;
    while (*str) {
        hash = hash * 31 + (*str++);
    }
    return hash;
}

// 插入元素
void bloom_insert(BloomFilter *bf, const char *key) {
    for (int i = 0; i < bf->k; i++) {
        uint32_t h = hash_func(key, i * 100 + 7);
        int pos = h % bf->m;
        bloom_set_bit(bf, pos);
    }
    bf->n++;
}

// 查询元素
int bloom_query(BloomFilter *bf, const char *key) {
    for (int i = 0; i < bf->k; i++) {
        uint32_t h = hash_func(key, i * 100 + 7);
        int pos = h % bf->m;
        if (!bloom_get_bit(bf, pos)) {
            return 0;  // 一定不存在
        }
    }
    return 1;  // 可能存在
}

// 释放布隆过滤器
void bloom_destroy(BloomFilter *bf) {
    free(bf->bits);
    free(bf);
}

int main() {
    // 创建一个位数组大小1000位、3个哈希函数的布隆过滤器
    BloomFilter *bf = bloom_create(1000, 3);
    
    bloom_insert(bf, "hello");
    bloom_insert(bf, "world");
    bloom_insert(bf, "bloom");
    
    printf("查询 'hello': %s\n", 
           bloom_query(bf, "hello") ? "可能存在" : "一定不存在");
    printf("查询 'world': %s\n", 
           bloom_query(bf, "world") ? "可能存在" : "一定不存在");
    printf("查询 'test': %s\n", 
           bloom_query(bf, "test") ? "可能存在" : "一定不存在");
    
    bloom_destroy(bf);
    return 0;
}

五、布隆过滤器的参数选择——怎么调才靠谱？

布隆过滤器有三个关键参数：位数组大小m、哈希函数个数k、预期插入元素数n。它们之间的关系有公式：

误判率 p ≈ (1 - e^-kn/m)^k

最优哈希函数个数：k = (m/n) * ln2

我一般这样选参数：

• 先确定n：预估你要存多少元素
• 再定误判率p：一般取0.01（1%）或0.001（0.1%）
• 计算m：m = -n * ln(p) / (ln2)^2
• 最后算k：k = (m/n) * ln2

举个例子：要存100万个元素，误判率1%，那么m≈958万位（约1.14MB），k≈7个哈希函数。你看，1MB内存就能处理100万条数据，哈希表至少得几十MB吧？

嗯，布隆过滤器的原理和实现就讲到这里。记住它的核心：宁可误报，绝不漏报。这个特性决定了它的应用边界，也决定了它的价值所在。

---

公众号：蓝海资料掘金营，微信deep3321