政务公开和网站建设自查报告,自动采集更新的网站wordpress,电源网站模版,免费商城小程序源码文章目录位图数组获取索引获取索引状态设置索引状态布隆过滤器特点大致原理位图数组
一个int类型的整数用4字节,也就是32个bit位来表示#xff0c;将整数类型的数组转换成位图数组#xff0c;那么存储长度将变为原来的32倍
arr[0] 表示0-31
arr[1] 表示32-63
//...获取索引…
文章目录位图数组获取索引获取索引状态设置索引状态布隆过滤器特点大致原理位图数组
一个int类型的整数用4字节,也就是32个bit位来表示将整数类型的数组转换成位图数组那么存储长度将变为原来的32倍
arr[0] 表示0-31
arr[1] 表示32-63
//...获取索引
假设当前数为178那么178在位图数组中的位置为
// 数组索引要存放的index
indexMath.floor(178/32)
// 位图索引对应32位要存放的索引
bitIndex178%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个n2k个bit是因为对样本提取多个指纹最后结果更精确 为什么只会出现将非黑名单判定成黑名单这种这种情况 假设黑名单url1对应的k个指纹bit位置为32,11,22,黑名单url2对应的k个指纹bit位置为9,11,10如果要判定的url在黑名单内那么通过hash得出指纹bit一定被设置了因为hash函数的特效会得到相同的输出所以如果是黑名单的url不可能被判定成白名单如果要判定的url不在黑名单内那么因为hash冲突可能bit位置为2210因为被其他黑名单url设置了所以白名单的url会被判定成黑名单 为什么要求元素设置后不能被删除 因为黑名单url2删除bit位11时会将黑名单url1的bit位11也影响那么再进行判定时黑名单url1会因为bit位11没有设置被判定为白名单url 对于数组长度m、失误率p和哈希函数的个数k都存在数学公式去计算
