Redis相关文章
前言
布隆过滤器是 Redis 4.0版本提供的新功能，作为插件加载到Redis服务器中，提供强大的去重功能。
相比于 Set 集合的去重功能而言，布隆过滤器在空间上能节省 90% 以上，但是它的不足之处是去重率大约在 99% 左右，也就是说有 1% 左右的误判率，这种误差是由布隆过滤器的自身结构决定的。俗话说“鱼与熊掌不可兼得”，如果想要节省空间，就需要牺牲 1% 的误判率，而且这种误判率，在处理海量数据时，几乎可以忽略。
BitMap
要说布隆过滤器就要先提一下位图(bitMap)这个数据结构，bitmap基于bit存储，本质上为二进制数组，利用下标对应的bit值为0或1进行逻辑判断。
redis中bit映射基于字符串进行位移运算，所以长度最大限制在512MB之内，所以最大是2^32位。建议每个key的位数都控制下，因为读取时候时间复杂度O(n)，越大的串读的时间花销越大。
- Redis BitMap命令
SETBIT：为位数组指定偏移量上的二进制位设置值，偏移量从0开始计数，二进制位的值只能为0或1。返回原位置值。GETBIT：获取指定偏移量上二进制位的值。BITCOUNT：统计位数组中值为1的二进制位数量。BITOP：对多个位数组进行按位与、或、异或运算
127.0.0.1:6379> SETBIT first 01(integer)0127.0.0.1:6379> SETBIT first 31(integer)0127.0.0.1:6379> SETBIT first 00(integer)1127.0.0.1:6379> GETBIT first 0(integer)0127.0.0.1:6379> GETBIT first 3(integer)1
- 应用场景
计算网站大数据量用户签到信息，假如网站有1000w日活用户，需要判断每个用户的签到情况，正适用bitMap统计，通过字符串的位移量代表用户id，对应的bit值为0则未签到，为1则已签到。
BloomFilter
理解了bitmap再回来看布隆过滤器就非常明朗了，布隆过滤器本质上为bitmap + 多个hash算法组成的数据结构。
当有key存储的时候通过多个hash算法得出对应下标集合，将下标列表对应的bit值置为1，则代表该key已存入过滤器中。
检索时，只要看看这些点是不是都是1就知道元素是否在集合中；如果这些点有任何一个 0，则被检元素一定不在；如果都是1，则被检元素很可能在（之所以说“可能”是误差的存在）。
但既然是要基于Hash函数就会有Hash冲突的问题，所以bloomFilter不能保证100%的数据准确，只能保证如果bloomFilter的值为1不一定存在，bloomFilter的值为0一定不存在。
