布隆过滤器的工作原理及其实际应用案例有哪些？

本文共计1652个文字，预计阅读时间需要7分钟。

布隆过滤器+一句话说明，布隆过滤器是为了解决查询一个元素是否存在于某个集合中而设计的一种高效数据结构。例如：50亿个用户ID，查询某ID是否存在于这50亿集合中。50亿*8字节，约为50GB，内存占用极大。

布隆过滤器

用一句话来说，布隆过滤器是为了解决查询一个元素是否存在于某个集合之中。

例如：50亿个用户ID，查询某ID是否在这50亿集合之中。

50亿*8字节大约为50GB，内存占用极大。

所以一般采用 位数组，以及位数组的延伸设计：布隆过滤器。

在学习布隆过滤器之前，我们需要有些基础性概念：

哈希函数

哈希函数，即散列函数。它可以任意长度的输入通过算法转换成一个定长的输出，这个输出就是散列值，或者叫哈希值。

因为是无穷对应有限，则必有多个输入对应相同的输出，即散列冲突，或叫哈希冲突。

哈希算法有以下特点：

• 从输出无法推导出输入。
• 散列冲突的概率要尽可能小。
• 数据敏感，对输入的简单修改会导致输出的巨大差异。

位数组

位数组本质上是一个超长的bit数组，数组元素只能为0或1。

根据上文，如果50亿个用户ID是有序的，使用bit数组实际上很好判断。

将每个ID映射到数组下标之中，用1代表存在，0代表不存在，如果有一段数学意义上连续的ID，还可以用一位数组下标映射一段ID，内存占用将更小。

但如果用户ID不是自增的，如果50亿用户ID，按照ID为10位来计算，将有超过90亿种可能排列，使用位数组要占用超过100GB内存。

这几乎是无法接受的。