景德镇建站公司,电影网站模板源代码,建行官方网站多少,用了wordpress的网站文章目录 一、布隆过滤器提出二、布隆过滤器概念三、布隆过滤器哈希函数个数的选择四、布隆过滤器的实现1.布隆过滤器的插入2.布隆过滤器的查找3.布隆过滤器删除4.完整代码实现 五、布隆过滤器总结1.布隆过滤器优点2.布隆过滤器缺陷3.布隆过滤器的应用4.布隆过滤器相关面试题 一… 文章目录 一、布隆过滤器提出二、布隆过滤器概念三、布隆过滤器哈希函数个数的选择四、布隆过滤器的实现1.布隆过滤器的插入2.布隆过滤器的查找3.布隆过滤器删除4.完整代码实现 五、布隆过滤器总结1.布隆过滤器优点2.布隆过滤器缺陷3.布隆过滤器的应用4.布隆过滤器相关面试题 一、布隆过滤器提出
我们知道位图可以快速的判断某个数据是否在一个集合中但是位图有如下缺点
1.位图只适用于数据范围集中的场景当数据过于分散的时候就会存在空间的浪费
2.位图只能针对整形对于非整形的数据无法进行处理
其中位图只能针对整形的缺点我们可以使用仿函数来解决即针对某一种特定类型定义一个HashFunc函数将其转换为整形比如当数据类型为字符串的时候我们可以使用字符串哈希算法将字符串转换为整形然后再将这个整形映射到位图中
但是这种方法存在一个很大的缺陷–不同的字符串通过同一个HashFunc函数转换出来的值可能是一样的也就是说我们判断一个数在不在的时候就存在误判在这种情况下
1.位图中该字符串存在是不准确的因为该字符串的比特位可能原本是0但是和其他字符串冲突了发生了误判导致该比特位变为了1
2.位图中字符串不在是准确的因为比特位为0说明该字符串以及可能与该字符串发生冲突的其他字符串都不存在所以不在是准确的
此外我们通常会对字符串哈希函数转换出来的值进行取模以此来节省空间因为转换出来结果的范围是不确定的但是取模之后又会增加哈希冲突的概率。
那么我们该如何降低误判率呢答案是布隆过滤器
二、布隆过滤器概念
布隆过滤器是由布隆Burton Howard Bloom在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构特点是高效地插入和查询可以用来告诉你“某样东西一定不存在或者可能存在”它是用多个哈希函数将一个数据映射到位图结构中。此种方式不仅可以提升查询效率也可以节省大量的内存空间。
我们可以看到布隆过滤器是通过使用多个哈希函数的方式来降低误判率即让同一个元素映射多个下标位置在查询时只能这些位置都为1的时候才表示该值存在而同一个元素通过不同哈希函数映射出来的不同下标同时被误判的概率肯定是比一个下标位置被误判的概率要低很多的。 需要注意的是布隆过滤器只能降低误判率不能彻底消除误判
三、布隆过滤器哈希函数个数的选择
那么是不是映射下标位置的个数越多越好呢当然不是的因为一个元素映射的下标位置越多那么浪费的空间越多此时我们可以选择哈希表或者红黑树这样查询的结果还是准确的对于如何选择哈希函数个数和布隆过滤器长度这里有一篇大佬写的博客大家可以参考详解布隆过滤器的原理使用场景和注意事项
我们通过这篇博客可以知道哈希长度布隆过滤器长度 插入元素个数与误判率如下图 以及他们之间的关系 对于上面的K取值带入可得
1.当k取3的时候m大约为4.3n即一个插入元素要消耗4个左右的比特位
1.当k取5的时候m大约为7.2n即一个插入元素要消耗7个左右的比特位
1.当k取8的时候m大约为11.6n即一个插入元素要消耗12个左右的比特位
结合关系图和关系表达式可以得出哈希函数取3-5个比较合适。
四、布隆过滤器的实现
布隆过滤器的实现很简单位图使用库中的bitset 即可字符串哈希算法可以从下面这篇博客中介绍的算法里面挑选几个评分比较高的算法各种字符串Hash函数
1.布隆过滤器的插入
对个数据的插入我们只需要让每一个位图都调用set即可就可以实现比如下面的例子 向布隆过滤器中插入“baidu” 向布隆过滤器中插入“tencent” 代码实现
void set(const T key)
{size_t hashi1 HashFunc1()(key) % (N * X);size_t hashi2 HashFunc2()(key) % (N * X);size_t hashi3 HashFunc3()(key) % (N * X);size_t hashi4 HashFunc4()(key) % (N * X);_bs.set(hashi1);_bs.set(hashi2);_bs.set(hashi3);_bs.set(hashi4);
}2.布隆过滤器的查找
布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找分别计算每个哈希值对应的比特位置存储的是否为零只要有一个为零代表该元素一定不在哈希表中否则可能在哈希表中。
注意布隆过滤器如果说某个元素不存在时该元素一定不存在如果该元素存在时该元素可能存在因为有些哈希函数存在一定的误判。
比如在布隆过滤器中查找alibaba时假设3个哈希函数计算的哈希值为1、3、7刚好和其他元素的比特位重叠此时布隆过滤器告诉该元素存在但实该元素是不存在的。
代码实现如下
bool test(const T key)
{size_t hashi1 HashFunc1()(key) % (N * X);if (!_bs.test(hashi1)){return false;}size_t hashi2 HashFunc2()(key) % (N * X);if (!_bs.test(hashi2)){return false;}size_t hashi3 HashFunc3()(key) % (N * X);if (!_bs.test(hashi3)){return false;}size_t hashi4 HashFunc4()(key) % (N * X);if (!_bs.test(hashi4)){return false;}// 前面判断不在都是准确不存在误判return true; // 可能存在误判映射几个位置都冲突就会误判
}3.布隆过滤器删除
布隆过滤器不能直接支持删除工作因为在删除一个元素时可能会影响其他元素。
比如删除上图中tencent元素如果直接将该元素所对应的二进制比特位置0“baidu”元素也被删除了因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。
一种支持删除的方法将布隆过滤器中的每个比特位扩展成一个小的计数器插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一删除元素时给k个计数器减一通过多占用几倍存储空间的代价来增加删除操作。
缺陷
1.无法确认元素是否真正在布隆过滤器中
2.存在计数回绕
4.完整代码实现
#pragma oncenamespace hdp
{struct BKDRHash{size_t operator()(const string key){size_t hash 0;for (auto ch : key){hash * 131;hash ch;}return hash;}};struct APHash{size_t operator()(const string key){unsigned int hash 0;int i 0;for (auto ch : key){if ((i 1) 0){hash ^ ((hash 7) ^ (ch) ^ (hash 3));}else{hash ^ (~((hash 11) ^ (ch) ^ (hash 5)));}i;}return hash;}};struct DJBHash{size_t operator()(const string key){unsigned int hash 5381;for (auto ch : key){hash (hash 5) ch;}return hash;}};struct JSHash{size_t operator()(const string s){size_t hash 1315423911;for (auto ch : s){hash ^ ((hash 5) ch (hash 2));}return hash;}};templatesize_t N,size_t X 6,class Tstring,class HashFunc1 BKDRHash,class HashFunc2 APHash,class HashFunc3 DJBHash,class HashFunc4 JSHashclass BloomFilter{public:void set(const T key){size_t hashi1 HashFunc1()(key) % (N * X);size_t hashi2 HashFunc2()(key) % (N * X);size_t hashi3 HashFunc3()(key) % (N * X);size_t hashi4 HashFunc4()(key) % (N * X);_bs.set(hashi1);_bs.set(hashi2);_bs.set(hashi3);_bs.set(hashi4);}bool test(const T key){size_t hashi1 HashFunc1()(key) % (N * X);if (!_bs.test(hashi1)){return false;}size_t hashi2 HashFunc2()(key) % (N * X);if (!_bs.test(hashi2)){return false;}size_t hashi3 HashFunc3()(key) % (N * X);if (!_bs.test(hashi3)){return false;}size_t hashi4 HashFunc4()(key) % (N * X);if (!_bs.test(hashi4)){return false;}// 前面判断不在都是准确不存在误判return true; // 可能存在误判映射几个位置都冲突就会误判}private:std::bitsetN * X _bs;};void test_bloomfilter1(){// 10:46继续string str[] { 猪八戒, 孙悟空, 沙悟净, 唐三藏, 白龙马1,1白龙马,白1龙马,白11龙马,1白龙马1 };BloomFilter10 bf;for (auto str : str){bf.set(str);}for (auto s : str){cout bf.test(s) endl;}cout endl;srand(time(0));for (const auto s : str){cout bf.test(s to_string(rand())) endl;}}void test_bloomfilter2(){srand(time(0));const size_t N 100000;BloomFilterN bf;std::vectorstd::string v1;std::string url https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html;for (size_t i 0; i N; i){v1.push_back(url std::to_string(i));}for (auto str : v1){bf.set(str);}// v2跟v1是相似字符串集但是不一样std::vectorstd::string v2;for (size_t i 0; i N; i){std::string url https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html;url std::to_string(999999 i);v2.push_back(url);}size_t n2 0;for (auto str : v2){if (bf.test(str)){n2;}}cout 相似字符串误判率: (double)n2 / (double)N endl;// 不相似字符串集std::vectorstd::string v3;for (size_t i 0; i N; i){string url zhihu.com;url std::to_string(i rand());v3.push_back(url);}size_t n3 0;for (auto str : v3){if (bf.test(str)){n3;}}cout 不相似字符串误判率: (double)n3 / (double)N endl;}
}我们可以使用上面两个函数对布隆过滤器进行测试我们最终会发现误判率是可控的我们可以根据具体的应用场景来测试调整哈希函数的个数以及布隆过滤器的长度最终实现出最符合当前应用场景的布隆过滤器
五、布隆过滤器总结
1.布隆过滤器优点
1.增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数一般比较小)与数据量大小无关
2.哈希函数相互之间没有关系方便硬件并行运算
3.布隆过滤器不需要存储元素本身在某些对保密要求比较严格的场合有很大优势
4.在能够承受一定的误判时布隆过滤器比其他数据结构有这很大的空间优势
5.数据量很大时布隆过滤器可以表示全集其他数据结构不能
6.使用同一组散列函数的布隆过滤器可以进行交、并、差运算
2.布隆过滤器缺陷
1.有误判率即存在假阳性(False Position)即不能准确判断元素是否在集合中(补救方法再建立一个白名单存储可能会误判的数据)
2.不能获取元素本身
3.一般情况下不能从布隆过滤器中删除元素
4.如果采用计数方式删除可能会存在计数回绕问题
3.布隆过滤器的应用
布隆过滤器是解决位图只能处理整形和数据范围集中的缺陷而提出的但是哈希函数和取模会导致哈希冲突从而发生误判为了降低误判率我们需要合理的选择哈希函数的个树以及布隆过滤器的长度
布隆过滤器适用于不需要完全准确允许出现一定误判的场景例如如下场景
1.用户注册时的昵称判重某些网站在注册时不允许出现重复昵称而已注册的昵称都保存在服务器的数据库中因为数据库存在磁盘是上访问速度非常慢所以如果用户没选择一个昵称都去数据库中查找是否存在的话效率是很低的。此时我们就可以在服务器前面加一个布隆过滤器进行过滤–将已注册的昵称都映射到布隆过滤器中而不在一定是准确的此时运行用户可以使用该昵称可以直接返回不再需要到数据库中进行查找。如果昵称在布隆过滤器中则提示用户重新输入但是这个并不影响用户的使用我们也可以去数据库中进行查找返回准确的结果。
2.查询个人的数据比如我们要在公司的客户的数据中以身份证号为key值查找某一个用户的具体信息。由于直接访问数据的效率非常低此时我们即可以在服务器前面加一个布隆过滤器。查找方式和第一点一样不在就直接返回如果存在则再到数据库中进行查找再返回查找的结果
在于其他的领域比如判断一个网站是否是危险网站我们在点进该网站时就应该显示出信息此时我们就可以使用布隆过滤器快速的进行显示。 4.布隆过滤器相关面试题
给两个文件分别有100亿个query我们只有1G内存如何找到两个文件交集分别给出精确算法和近似算法
我们需要使用哈希切割的思想–使用相同的哈希函数分别对这两个文件进行切割切割结果为A0–Ai,B0-Bi;因为哈希函数相同所以Ai和Bi中的query及发生冲突的query都在同一个小文件中此时我们只需要分别求出Ai和Bi相同下标小文件中的交集即可。需要注意的是如果小文件很大说明某一个或几个query有大量的重复此时换一个哈希函数再分别对Ai和Bi小文件递归子文件进行哈希切割即可。
对于精确算法来说我们需要先将Ai号小文件中的元素全部存入set/map中再依次取Bi号小文件中的数据到set/map中查询即可得到交集但是最后的结果需要进行去重处理。
