布隆过滤器学习

背景¶

平时查询一个value是否存在，通常会创建一个hashmap进行存储所有元素。它的好处是快速准确，缺点是浪费空间。因此，引入布隆过滤器。

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

原理¶

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

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

参考文献¶

1. 飞书，