Redis之布隆过滤器

由一个初值都为零的bit数组和多个哈希函数构成用来快速判断集合中是否存在某个元素

1. 特性

1. 减少内存占用
2. 不保存数据信息，只是在内存中做一个是否存在的标记flag

2.

它实际上是一个很长的二进制数组(00000000)+一系列随机hash算法映射函数，主要用于判断一个元素是否在集合中。 通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景，一般想到的是将集合中所有元素保存起来，然后通过比较确定。
链表、树、哈希表等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间也会呈现线性增长，最终达到瓶颈。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为O(n),O(logn),O(1)。这个时候，布隆过滤器（Bloom Filter）就应运而生

3.

一个元素如果判断结果:存在时，元素不一定存在。但是判断结果为不存在时，则一定不存在
布隆过滤器可以添加元素，但是不能删除元素由于涉及hashcode判断依据，删掉元素会导致误判率增加。

4. 使用

redis的setbit/getbit

5.

为了解决布隆过滤器不能删除元素的问题，布谷鸟过滤器横空出世。