回答
本质上布隆过滤器(Bloom Filter
)是一种数据结构,一种效率极高的概率型数据结构,用于判断一个元素是否存在于布隆过滤器中,但这个判断是一个概率事件,由于它是基于 hash 函数的,所以会存在一定的误判概率,它所反馈的情况是:某个元素一定不存在或者可能存在。
由于布隆过滤器是一个 bit 向量或者 bit 数组,它能够在占用很少空间和以极快的时间内进行元素的插入和查询操作。所以它非常适用于解决海量数据的存在性问题。
扩展
什么是布隆过滤器
布隆过滤器(Bloom Filter
)是一个叫做 Bloom 的老哥于 1970 年提出的。我们可以把它看作是由二进制向量(或者说位数组)和一系列哈希函数两部分组成的数据结构。
- 二进制向量:这是布隆过滤器的核心,一个非常大的二进制向量,初始时所有位都设为 0。
- 哈希函数:布隆过滤器使用多个哈希函数来处理每个插入或查询的元素。每个哈希函数将元素映射到位数组的一个位置上。所以,哈希函数的质量会影响布隆过滤器的效率和误判率。
布隆过滤器是使用一个较大的 bit 数组来保存所有的数据,数组中的每个元素都只占用 1 bit ,并且每个元素只能是 0 或者 1(代表 false 或者 true)。