大数据去重神器：位图与布隆过滤器详解

前言

最近总是在各大技术平台刷到这样一个经典面试题：

如何对40亿QQ号进行去重…

嗯？40亿？这个数字有点恐怖啊，按常规思路光存储起来都要占用不少内存，还要在此之上去重，想到这手就忍不住伸向了投降键…

别急，让咱们一起来看看有没有更聪明的解决方案。

在处理海量数据时，如何高效去重是一个常见问题。想象一下，如何对40亿QQ号进行去重？传统方法可能会占用大量内存，今天咱们就来探讨两种高效的数据结构：位图(Bitmap)和布隆过滤器(Bloom Filter)。

传统存储方式的问题

首先咱们计算一下：存储40亿QQ号需要多少内存？

使用无符号整数存储时，一个整数需要4个字节(Byte)，那么40亿QQ号需要：

4 * 4,000,000,000 / 1024 / 1024 / 1024 ≈ 15GB

在实际业务中往往需要更多空间。而且在Java中并不存在无符号整型，只有几个操作无符号的静态方法。

数据单位换算：1GB = 1024MB，1MB = 1024KB，1KB = 1024Byte, 1Byte = 8b

n个小时后…终于存好了，接下来咱们开始计算吧！等等，存好了？真的吗？15GB的内存空间，普通开发机器根本扛不住啊！

这种方式显然不够优雅。还有没有能用高效的空间就能存这么多数据，还能执行一定的算法…

有的，有的，咱们还可以使用位图(Bitmap)。

位图(Bitmap)详解

什么是位图？

位图(Bitmap)顾名思义，是一种使用比特位来存储信息的数据结构。它的结构类似哈希表，但只允许存储0或1，可以用极少的空间表示大量的数据状态。

当咱们需要判断一个数是否存在时，只需要查看对应索引位置的比特值是否为1。例如，判断QQ号2924357571是否存在，只需检查位图中索引为2924357571的位置是否为1。

位图的内存优势

使用位图存储一次全部的QQ号，每个QQ号只占用1个比特位。假设QQ号的范围是无符号整数(最大为2^32-1)，位图需要的内存是：

4,294,967,295 / 8 / 1024 / 1024 ≈ 512MB

这样的话，给40亿QQ号查重只需要遍历记录value >= 2的下标，而这仅仅只需要O(N)的时间和512MB的内存，奶奶的电脑也算得动啦！

只是稍微用了这种索引存储信息的作弊手段，咱们比传统方式节省了近30倍的空间！数据结构，你这家伙…

Redis中的位图操作

在Redis中，位图通过以下三个命令实现：

命令	功能
SETBIT key offset value	设置指定offset位置的值，value只能是0或1
GETBIT key offset	获取指定offset位置的值
BITCOUNT key start end	获取start到end之间value为1的数量

位图的应用场景

1. 大数据量去重：除QQ号外，还可用于订单号去重、网络爬虫URL去重等
2. 用户行为统计：如在线状态跟踪、签到记录、活跃用户统计等
3. 数据统计：比如在线人员统计，将在线人员id为偏移值，为1表示在线；视频统计，将全部视频的id为偏移存储到Bitmap中。
4. 布隆过滤器（BloomFilter）：布隆过滤器的基础就是使用的位图，只不过布隆过滤器使用了多个哈希函数处理，只有当全部的哈希都为1，才表示这个值存在。

嗯，等等，布隆过滤器？这是什么？

布隆过滤器(Bloom Filter)

为什么要有布隆过滤器？

仔细想想，这种用索引来作弊的手段并非通解。很多时候，咱们的数据是下面这样的样子

字符串："https://www.example.com/page1"

对象：User{id=123, name="张三", email="zhangsan@example.com"}

复杂数据：{"userId": 10086, "visitTime": "2023-11-26 10:30:00"} 

天哪，难道咱们又不能下班了？位图只能处理数值型数据，面对字符串、对象这类非整数数据时就抓瞎了！想到这手就忍不住又伸向了投降键…

别急，咱们还有法宝，哈希算法！哈希算法可以把任意数据映射成一个固定长度的数值。例如：

"https://www.example.com" → 哈希函数 → 3582761045

User{id=123, name="张三"} → 哈希函数 → 1728495613

于是，我们得到了一种处理任意数据类型的去重神器 —— 布隆过滤器 。

什么是布隆过滤器？

布隆过滤器是位图的升级版，它使用多个哈希函数处理同一数据，但是，单一哈希函数容易产生”哈希冲突”（不同的输入得到相同的哈希值）。为了降低冲突概率，布隆过滤器使用了多个哈希函数！只有当所有哈希对应的位置都为1时，才认为该元素可能存在（注意是”可能”）。

布隆过滤器的工作原理

布隆过滤器有三个核心参数决定了其性能和准确性：

• 位数组大小(m): 影响内存使用和误判率
• 哈希函数数量(k): 影响计算性能和误判率
• 预计元素数量(n): 决定上述两个参数的最佳值

布隆过滤器的误判率公式

p ≈ (1 - e^( -k * n/m ) ) ^ k

最佳位数组大小计算

对于给定的元素数量 n 和目标误判率 p，最佳位数组大小为：

m = -n * ln(p) / (ln(2)^2)

最佳哈希函数数量计算

当位数组大小 m 和元素数量 n 确定后，最佳哈希函数数量为：

k = (m/n) * ln(2)

执行流程

当插入一个元素时，布隆过滤器会：

1. 使用多个哈希函数计算该元素的哈希值
2. 将位图中对应位置设为1

当判断一个元素是否存在时：

1. 同样使用这些哈希函数计算哈希值
2. 检查对应位置是否都为1
   • 如果有一个为0，则元素一定不存在
   • 如果全为1，则元素按概率(p)可能存在

记不住？没关系，你只需要知道，想要降低误判率：

> 增加位数组大小 m 能降低误判率
> 优化哈希函数数量 k 能降低误判率
> 控制元素数量 n 不超过设计容量 能降低误判率
> 判定不存在的一定不存在，否则按概率值P的可能性存在
> 误判率越低，内存利用率越低；内存利用率越高，误判率越高，二者不可同兼！

实现示例

在Go语言中，我们可以这样实现一个布隆过滤器:

package bloomfilter

import (
	"hash/fnv"
	"hash/crc32"
	"hash/adler32"
	"math"
)

// BloomFilter 实现了布隆过滤器
type BloomFilter struct {
	bitset    []bool   // 位数组
	size      uint     // 位数组大小
	hashFuncs []func([]byte) uint // 哈希函数列表
	count     uint     // 已添加元素数量
}

// NewBloomFilter 创建一个新的布隆过滤器
// n: 预计元素数量
// p: 期望的误判率，例如0.01表示1%
func NewBloomFilter(n uint, p float64) *BloomFilter {
	// 根据预期元素数量和误判率计算最佳位数组大小
	m := calculateOptimalSize(n, p)
	// 根据位数组大小和预期元素数量计算最佳哈希函数数量
	k := calculateOptimalHashCount(m, n)
	
	// 创建布隆过滤器实例
	bf := &BloomFilter{
		bitset: make([]bool, m),
		size:   m,
		count:  0,
	}
	
	// 初始化哈希函数
	bf.hashFuncs = make([]func([]byte) uint, k)
	
	// 定义多个哈希函数
	bf.hashFuncs[0] = func(data []byte) uint {
		h := fnv.New64()
		h.Write(data)
		return uint(h.Sum64() % uint64(m))
	}
	
	bf.hashFuncs[1] = func(data []byte) uint {
		h := crc32.NewIEEE()
		h.Write(data)
		return uint(h.Sum32() % uint32(m))
	}
	
	bf.hashFuncs[2] = func(data []byte) uint {
		h := adler32.New()
		h.Write(data)
		return uint(h.Sum32() % uint32(m))
	}
	
	// 使用不同的种子生成更多哈希函数
	for i := uint(3); i < k; i++ {
		seed := i
		bf.hashFuncs[i] = func(data []byte) uint {
			h := fnv.New64a()
			h.Write(append(data, byte(seed)))
			return uint(h.Sum64() % uint64(m))
		}
	}
	
	return bf
}

// Add 添加元素到布隆过滤器
func (bf *BloomFilter) Add(data []byte) {
	for _, hashFunc := range bf.hashFuncs {
		position := hashFunc(data)
		bf.bitset[position] = true
	}
	bf.count++
}

// Contains 检查元素是否可能存在于布隆过滤器中
func (bf *BloomFilter) Contains(data []byte) bool {
	for _, hashFunc := range bf.hashFuncs {
		position := hashFunc(data)
		if !bf.bitset[position] {
			return false
		}
	}
	return true
}

// 计算最佳位数组大小
func calculateOptimalSize(n uint, p float64) uint {
	// m = -n*ln(p)/(ln(2)^2)
	m := uint(math.Ceil(-float64(n) * math.Log(p) / math.Pow(math.Log(2), 2)))
	return m
}

// 计算最佳哈希函数数量
func calculateOptimalHashCount(m, n uint) uint {
	// k = (m/n) * ln(2)
	k := uint(math.Ceil(float64(m) / float64(n) * math.Log(2)))
	if k < 3 {
		k = 3 // 至少使用3个哈希函数
	}
	return k
}

// EstimateErrorRate 估算当前误判率
func (bf *BloomFilter) EstimateErrorRate() float64 {
	// 误判率公式: (1 - e^(-k*n/m))^k
	k := float64(len(bf.hashFuncs))
	m := float64(bf.size)
	n := float64(bf.count)
	return math.Pow(1.0 - math.Exp(-k*n/m), k)
}

实际应用示例

package main

import (
	"fmt"
	"./bloomfilter"
)

func main() {
	// 创建一个期望容纳100万元素、误判率为0.01的布隆过滤器
	filter := bloomfilter.NewBloomFilter(1000000, 0.01)
	
	// 添加一些URL
	filter.Add([]byte("https://example.com"))
	filter.Add([]byte("https://example.org"))
	
	// 检查URL是否存在
	fmt.Println("https://example.com 可能存在:", filter.Contains([]byte("https://example.com")))
	fmt.Println("https://unknown.com 可能存在:", filter.Contains([]byte("https://unknown.com")))
	
	// 当前估计误判率
	fmt.Printf("当前估计误判率: %.6f\n", filter.EstimateErrorRate())
	
	// 添加大量元素后...
	for i := 0; i < 500000; i++ {
		filter.Add([]byte(fmt.Sprintf("element-%d", i)))
	}
	
	// 重新检查误判率
	fmt.Printf("添加50万元素后的估计误判率: %.6f\n", filter.EstimateErrorRate())
}

https://example.com 可能存在: true
https://unknown.com 可能存在: false
当前估计误判率: 0.000003
添加50万元素后的估计误判率: 0.004827

布隆过滤器的优缺点

优点：

• 可以处理字符串或复杂对象，不限于整数
• 极高的空间效率
• 检索速度快

缺点：

• 存在误判可能（假阳性），可能判断不存在的元素为存在
• 无法删除元素
• 随着元素增加，误判率上升

总结

在海量数据处理场景中，位图和布隆过滤器通过牺牲一定的准确性，换取极高的空间效率和查询速度。当咱们需要处理大量数据去重、黑名单过滤等场景时，这两种数据结构是非常优秀的选择，而在大数据处理领域，”宁可错杀一千，不可放过一个”的场景，布隆过滤器就是最佳选择。

感谢前人的智慧，Aki终于可以按时下班啦！