布隆过滤器原理是什么？如何实现实战应用？

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

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

布隆过滤器

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

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

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

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

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

哈希函数

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

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

哈希算法有以下特点：

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

位数组

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

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