布隆过滤器与Redis

布隆过滤器是一种用来判定某个对象是否存在是否已经添加过的数据结构，一般来说，布隆过滤器要有初始化，加入对象，判定对象是否存在三个功能，本质上来说，与hashmap，hashset的思路是一样的，但是因为面对的场景不一样，在数据结构的设计思路上也有一些变化，一般来说，布隆过滤器面对的是海量数据，而且并不过于严格的要求准确性，针对这些特性，在设计布隆过滤器的时候，要从对象中提前某一个唯一值，但是该值可以对应多个对象（即可能由a对象的值或者a，b的值获得c的值，这是可以接受的），因此一般选用bitmap结构作为布隆过滤器的主体，bitmap本质上是一个bool类型的数组，以位移代替数组的下标，每一个bit就是数组的一项，以位移位置上bit的0,1指示true，false，这样就可以在尽可能少的空间上储存更多的数据。

有了储存值的数据结构bitmap，类比hashset，布隆过滤器还需要一个hash方法来得到值，为了减少hash冲突，布隆过滤器常常同时使用多个hash函数得到多个值，共同作为该对象的hash结果。

综上，布隆过滤器有一个hash函数组，有固定容量的bitmap，添加对象时，用hash函数组求出一组数据，映射成bitmap的一组位移，然后将bitmap对应位置bit设为1。

查询对象是否已经添加时，同样用hash函数组得到一组数据，得到对应的映射位移组，查看bitmap上的对应位置是否全部为1，如果全部为1，就认为可能已经添加过（有已经添加过的其他一个对象或多个对象的映射完全覆盖位移组的可能性），如果有0，那么就一定不存在。

这样只要有了固定的hash函数组，固定的size，布隆过滤本身也可以进行与并非。

那么在开发时如何真正的使用布隆过滤器呢，一般来说，需要使用布隆过滤器的往往是海量数据场景（不然为什么不直接使用hashset，hashmap之类的，反而会更准确），因此往往会是分布式服务器，所以要在第三方组件里实现布隆过滤器（谷歌guava有本地实现的库），reids就这样进入了我们的视野。

高性能，海量，缓存中间件，提到这些词，第一想法就是redis，而且redis里string类型底层的sds（简单动态字符串）本身就可以用来实现bitmap，sds数据结构有以下特性，本身有一个容量（最大512MB，这是因为长度是用一个32位无符号数储存的，大概实际是42亿个bit）和实际使用容量，使用时空间不够的话自动扩容（扩容后实际小于1M，就给实际大小2倍的容量，否则给实际长度+1M的空间），不自动销毁空间。也就是说sds是可以直接判定位移n个bit后是0还是1的。

基于这些特性，Redis的java客户端redisson已经实现了布隆过滤器函数，下面简单说一下Redisson是怎么实现的。

Redisson会在使用布隆过滤器开始要求使用者提供一个可能的数据插入量（n）以及允许的错误概览（p），比如我们初始化一个布隆过滤器filterA，假设要插入100万次，错误概览0.03125（1/32），那么客户端会先去redis中看有没有这个过滤器（可能已经被其他客户端实现了），假设没有的话，可以算出一个size（需要的bit数，最大不可以超过2的32次方，42亿左右，-log2 p* n/(  * log 10 2),比如filterA的size就大概是5*100 0000*3.32 ，一千五百万bit左右，不到2MB）以及hashIterations(散列函数迭代次数，-log2 p，filterA就是5)，然后就可以使用lua脚本在redis中申请空间进行初始化了。

在添加对象时，先使用两个固定的hash函数得到hash值hash1，hash2，然后根据hashIterations不断累加再对size取余，假设hashIterations是5，hash1是7，hash2是13，size是50，那么就会得到long[]{20,27,40,47,10}作为得到位移值，把这些位置上的位移置1就可以了。

查询时，方法与添加一致，先得到位移数组，再判定是否全部为1，最后根据判定结果确认是否可能已经添加过。