位图数组 布隆过滤器

位图数组

一个int类型的整数用4字节,也就是32个bit位来表示，将整数类型的数组转换成位图数组，那么存储长度将变为原来的32倍

arr[0] 表示0-31
arr[1] 表示32-63
//...

获取索引

假设当前数为178，那么178在位图数组中的位置为：

// 数组索引，要存放的index
index=Math.floor(178/32)
// 位图索引，对应32位要存放的索引
bitIndex=178%32

获取索引状态

// 拿到index，再右移bitIndex位，那此时状态就变到了最后一位，再& 1
// ... 0000000s
// ... 00000001
int s=(arr[index]>>bitIndex)& 1

设置索引状态

将对应位置设置为1

// ...s...
// ...1...
// 注意是或操作，1其他位为0，最后只会将s位变为1，其他位不会影响
arr[index] | (1 << bitIndex)

将对应位置设为0

// 1 << bitIndex 后取反将变为, ... 1110111 ...
// 注意 & 1 不会影响其他位
arr[index] & (~ (1 << bitIndex))

布隆过滤器

特点

• 存在一定失误率，但很小
• 不能删除已设置的元素
• 假设要查询当前url是否在黑名单
  • 只会存在将非黑名单判定成黑名单这种失误，而不会出现将黑名单判定成白名单的情况
• 通过位图数组，大幅度减少存储空间

大致原理

场景：要存储100亿个黑名单url，并且给定一个url要判断是否在黑名单内

• 假设数组长度为m
• 对100亿个黑名单url，对每个url用k个hash函数求得k个转换出来的整型数n，对n%m获取到不超过m的映射值n2,对n2进行上面位图的操作，放入bit中
  • 这里要求k个hash，拿到k个n2，k个bit是因为对样本提取多个指纹，最后结果更精确
• 为什么只会出现将非黑名单判定成黑名单这种这种情况
  • 假设黑名单url1对应的k个指纹bit位置为32,11,22,黑名单url2对应的k个指纹bit位置为9,11,10
  • 如果要判定的url在黑名单内，那么通过hash得出指纹bit一定被设置了，因为hash函数的特效会得到相同的输出，所以如果是黑名单的url不可能被判定成白名单
  • 如果要判定的url不在黑名单内，那么因为hash冲突可能bit位置为22，10，因为被其他黑名单url设置了，所以白名单的url会被判定成黑名单
• 为什么要求元素设置后不能被删除
  • 因为黑名单url2删除bit位11时，会将黑名单url1的bit位11也影响，那么再进行判定时，黑名单url1会因为bit位11没有设置，被判定为白名单url
• 对于数组长度m、失误率p和哈希函数的个数k，都存在数学公式去计算