网站建设总结与心得体会,电子商务经营范围有哪些?,网站更换域名备案吗,app开发成本预算表布隆过滤器的提出
在注册账号设置昵称的时候#xff0c;为了保证每个用户昵称的唯一性#xff0c;系统必须检测你输入的昵称是否被使用过#xff0c;这本质就是一个key的模型#xff0c;我们只需要判断这个昵称被用过#xff0c;还是没被用过。
方法一#xff1a;用红黑…布隆过滤器的提出
在注册账号设置昵称的时候为了保证每个用户昵称的唯一性系统必须检测你输入的昵称是否被使用过这本质就是一个key的模型我们只需要判断这个昵称被用过还是没被用过。
方法一用红黑树或哈希表将所有使用过的昵称存储起来当需要判断一个昵称是否被用过时直接判断该昵称是否在红黑树或哈希表中即可。但红黑树和哈希表最大的问题就是浪费空间当昵称数量非常多的时候内存当中根本无法存储这些昵称方法二用位图将所有使用过的昵称存储起来虽然位图只能存储整型数据但我们可以通过一些哈希算法将字符串转换成整型比如BKDR哈希算法。当需要判断一个昵称是否被用过时直接判断位图中该昵称对应的比特位是否被设置即可。
位图虽然能够大大节省内存空间但由于字符串的组合形式太多了一个字符的取值有256种而一个数字的取值只有10种因此无论通过何种哈希算法将字符串转换成整型都不可避免会存在哈希冲突。
这里的哈希冲突就是不同的昵称最终被转换成了相同的整型此时就可能会引发误判即某个昵称明明没有被使用过却被系统判定为已经使用过了于是就出现了布隆过滤器。
布隆过滤器的概念
布隆过滤器是由布隆Burton Howard Bloom在1970年提出的一种紧凑型的、比较巧妙的概率型数据结构特点是高效地插入和查询。 布隆过滤器其实就是位图的一个变形和延申虽然无法避免存在哈希冲突但我们可以想办法降低误判的概率。 当一个数据映射到位图中时布隆过滤器会用多个哈希函数将其映射到多个比特位当判断一个数据是否在位图当中时需要分别根据这些哈希函数计算出对应的比特位如果这些比特位都被设置为1则判定为该数据存在否则则判定为该数据不存在。 布隆过滤器使用多个哈希函数进行映射目的就在于降低哈希冲突的概率一个哈希函数产生冲突的概率可能比较大但多个哈希函数同时产生冲突的概率可就没那么大了。
假设布隆过滤器使用三个哈希函数进行映射那么“张三”这个昵称被使用后位图中会有三个比特位会被置1当有人要使用“李四”这个昵称时就算前两个哈希函数计算出来的位置都产生了冲突但由于第三个哈希函数计算出的比特位的值为0此时系统就会判定“李四”这个昵称没有被使用过。 但随着位图中添加的数据不断增多位图中1的个数也在不断增多此时就会导致误判的概率增加。
比如“张三”和“李四”都添加到位图中后当有人要使用“王五”这个昵称时虽然“王五”计算出来的三个位置既不和“张三”完全一样也不和“李四”完全一样但“王五”计算出来的三个位置分别被“张三”和“李四”占用了此时系统也会误判为“王五”这个昵称已经被使用过了。 布隆过滤器的特点 布隆过滤器判断一个数据存在可能是不准确的因为这个数据对应的比特位可能被其他一个数据或多个数据占用了。 布隆过滤器判断一个数据不存在是准确的因为如果该数据存在那么该数据对应的比特位都应该已经被设置为1了。
如何控制误判率 很显然过小的布隆过滤器很快所有的比特位都会被设置为1此时布隆过滤器的误判率就会变得很高因此布隆过滤器的长度会直接影响误判率布隆过滤器的长度越长其误判率越小。 此外哈希函数的个数也需要权衡哈希函数的个数越多布隆过滤器中比特位被设置为1的速度越快并且布隆过滤器的效率越低但如果哈希函数的个数太少也会导致误判率变高。
那应该如何选择哈希函数的个数和布隆过滤器的长度呢有人通过计算后得出了以下关系式 其中k为哈希函数个数m为布隆过滤器长度n为插入的元素个数p为误判率。
我们这里可以大概估算一下如果使用3个哈希函数即k的值为3 ln2的值我们取0.7那么m和n的关系大概是m 4 * n也就是布隆过滤器的长度应该是插入元素个数的4倍。
布隆过滤器的实现
首先布隆过滤器可以实现为一个模板类因为插入布隆过滤器的元素不仅仅是字符串也可以是其他类型的数据只有调用者能够提供对应的哈希函数将该类型的数据转换成整型即可但一般情况下布隆过滤器都是用来处理字符串的所以这里可以将模板参数K的缺省类型设置为string。
布隆过滤器中的成员一般也就是一个位图我们可以在布隆过滤器这里设置一个非类型模板参数N用于让调用者指定位图的长度。
//布隆过滤器
templatesize_t N, class K string, class Hash1 BKDRHash, class Hash2 APHash, class Hash3 DJBHash
class BloomFilter {
public://...
private:bitsetN _bs;
};实例化布隆过滤器时需要调用者提供三个哈希函数由于布隆过滤器一般处理的是字符串类型的数据因此这里我们可以默认提供几个将字符串转换成整型的哈希函数。
这里选取将字符串转换成整型的哈希函数是经过测试后综合评分最高的BKDRHash、APHash和DJBHash这三种哈希算法在多种场景下产生哈希冲突的概率是最小的。此时本来这三种哈希函数单独使用时产生冲突的概率就比较小现在要让它们同时产生冲突概率就更小了。
代码如下
struct BKDRHash {size_t operator()(const string s) {size_t value 0;for (auto ch: s) {value value * 131 ch;}return value;}
};struct APHash {size_t operator()(const string s) {size_t value 0;for (size_t i 0; i s.size(); i) {if ((i 1) 0) {value ^ ((value 7) ^ s[i] ^ (value 3));} else {value ^ (~((value 11) ^ s[i] ^ (value 5)));}}return value;}
};struct DJBHash {size_t operator()(const string s) {if (s.empty())return 0;size_t value 5381;for (auto ch: s) {value (value 5) ch;}return value;}
};布隆过滤器的插入
布隆过滤器当中需要提供一个Set接口用于插入元素到布隆过滤器当中。插入元素时需要通过三个哈希函数分别计算出该元素对应的三个比特位然后将位图中的这三个比特位设置为1即可。
代码如下
void Set(const K key) {//计算出key对应的三个位size_t i1 Hash1()(key) % N;size_t i2 Hash2()(key) % N;size_t i3 Hash3()(key) % N;//设置位图中的这三个位_bs.set(i1);_bs.set(i2);_bs.set(i3);
}布隆过滤器的查找
布隆过滤器当中还需要提供一个Test接口用于检测某个元素是否在布隆过滤器当中。检测时需要通过三个哈希函数分别计算出该元素对应的三个比特位然后判断位图中的这三个比特位是否被设置为1。
只要这三个比特位当中有一个比特位未被设置则说明该元素一定不存在。如果这三个比特位全部被设置则返回true表示该元素存在可能存在误判。
代码如下
bool Test(const K key) {//依次判断key对应的三个位是否被设置size_t i1 Hash1()(key) % N;if (_bs.test(i1) false) {return false;//key一定不存在}size_t i2 Hash2()(key) % N;if (_bs.test(i2) false) {return false;//key一定不存在}size_t i3 Hash3()(key) % N;if (_bs.test(i3) false) {return false;//key一定不存在}return true;//key对应的三个位都被设置key存在可能误判
}布隆过滤器的删除
布隆过滤器一般不支持删除操作原因如下
因为布隆过滤器判断一个元素存在时可能存在误判因此无法保证要删除的元素确实在布隆过滤器当中此时将位图中对应的比特位清0会影响其他元素。此外就算要删除的元素确实在布隆过滤器当中也可能该元素映射的多个比特位当中有些比特位是与其他元素共用的此时将这些比特位清0也会影响其他元素。
如何让布隆过滤器支持删除
要让布隆过滤器支持删除必须要做到以下两点
保证要删除的元素在布隆过滤器当中。比如刚才的呢称例子当中如果通过调用Test函数得知要删除的昵称可能存在布隆过滤器当中后可以进一步遍历存储昵称的文件确认该昵称是否真正存在。保证删除后不会影响到其他元素。可以为位图中的每一个比特位设置一个对应的计数值当插入元素映射到该比特位时将该比特位的计数值当删除元素时将该元素对应比特位的计数值–即可。
可是布隆过滤器最终还是没有提供删除的接口因为使用布隆过滤器本来就是要节省空间和提高效率的。在删除时需要遍历文件或磁盘中确认待删除元素确实存在而文件IO和磁盘IO的速度相对内存来说是很慢的并且为位图中的每个比特位额外设置一个计数器就需要多用原位图几倍的存储空间这个代价也是不小的。
布隆过滤器的优点 增加和查询元素的时间复杂度为O(K)K为哈希函数的个数一般比较小与数据量大小无关。 哈希函数相互之间没有关系方便硬件并行运算。 布隆过滤器不需要存储元素本身在某些对保密要求比较严格的场合有很大优势。 在能够承受一定的误判时布隆过滤器比其他数据结构有着很大的空间优势。 数据量很大时布隆过滤器可以表示全集其他数据结构不能。 使用同一组哈希函数的布隆过滤器可以进行交、并、差运算。
布隆过滤器的缺陷
有误判率即存在假阳性False Position即不能准确判断元素是否在集合中补救方法再自建一个白名单存储可能会误判的数据不能获取元素本身。一般情况下不能从布隆过滤器中删除元素。
布隆过滤器使用场景
使用布隆过滤器的前提是布隆过滤器的误判不会对业务逻辑造成影响。
比如当我们首次访问某个网站时需要用手机号注册账号而用户的各种数据实际都是存储在数据库当中的也就是磁盘上面。
当我们用手机号注册账号时系统就需要判断你填入的手机号是否已经注册过如果注册过则会提示用户注册失败。但这种情况下系统不可能直接去遍历磁盘当中的用户数据判断该手机号是否被注册过因为磁盘IO是很慢的这会降低用户的体验。这种情况下就可以使用布隆过滤器将所有注册过的手机号全部添加到布隆过滤器当中当我们需要用手机号注册账号时就可以直接去布隆过滤器当中进行查找。如果在布隆过滤器中查找后发现该手机号不存在则说明该手机号没有被注册过此时就可以让用户进行注册并且避免了磁盘IO。如果在布隆过滤器中查找后发现该手机号存在此时还需要进一步访问磁盘进行复核确认该手机号是否真的被注册过因为布隆过滤器在判断元素存在时可能会误判。
由于大部分情况下用户用一个手机号注册账号时都是知道自己没有用该手机号注册过账号的因此在布隆过滤器中查找后都是找不到的此时就避免了进行磁盘IO。而只有布隆过滤器误判或用户忘记自己用该手机号注册过账号的情况下才需要访问磁盘进行复核。 以让用户进行注册并且避免了磁盘IO。
如果在布隆过滤器中查找后发现该手机号存在此时还需要进一步访问磁盘进行复核确认该手机号是否真的被注册过因为布隆过滤器在判断元素存在时可能会误判。
由于大部分情况下用户用一个手机号注册账号时都是知道自己没有用该手机号注册过账号的因此在布隆过滤器中查找后都是找不到的此时就避免了进行磁盘IO。而只有布隆过滤器误判或用户忘记自己用该手机号注册过账号的情况下才需要访问磁盘进行复核。
