企业建站设计,杭州互联网公司排名,学校网站建设培训心得,wordpress没有文章导航每一个不曾起舞的日子都是对生命的辜负 布隆过滤器前言一.布隆过滤器提出二.布隆过滤器概念三. 布隆过滤器的操作3.1 布隆过滤器的插入3.2 布隆过滤器的查找3.3 布隆过滤器的删除四.布隆过滤器的代码4.1 HashFunc的仿函数参考4.2 BloomFilter.h五.布隆过滤器的优缺点六.布隆过滤… 每一个不曾起舞的日子都是对生命的辜负 布隆过滤器前言一.布隆过滤器提出二.布隆过滤器概念三. 布隆过滤器的操作3.1 布隆过滤器的插入3.2 布隆过滤器的查找3.3 布隆过滤器的删除四.布隆过滤器的代码4.1 HashFunc的仿函数参考4.2 BloomFilter.h五.布隆过滤器的优缺点六.布隆过滤器的应用场景前言 上一节中我们学到了位图可以看出位图有如下优点1.节省空间。2.快。 但相对的位图同样有缺点存在1. 一般要求范围相对集中如果范围特别分散空间消耗就会上升。2. 只能针对整形 那如果此时是字符串类型能不能通过位图的思想来确定字符串在不在呢 一.布隆过滤器提出
我们在使用新闻客户端看新闻时它会给我们不停地推荐新的内容它每次推荐时要去重去掉那些已经看过的内容。问题来了新闻客户端推荐系统如何实现推送去重的 用服务器记录了用户看过的所有历史记录当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选过滤掉那些已经存在的记录。 如何快速查找呢
用哈希表存储用户记录缺点浪费空间用位图存储用户记录缺点位图一般只能处理整形如果内容编号是字符串就无法处理了。将哈希与位图结合即布隆过滤器 即通过位图的方式确定字符串在还是不在我们可以采用HashFunc将字符串转换成整形映射到位图中这就是布隆过滤器。 二.布隆过滤器概念
布隆过滤器是由布隆Burton Howard Bloom在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构特点是高效地插入和查询可以用来告诉你 “某样东西一定不存在或者可能存在”它是用多个哈希函数将一个数据映射到位图结构中。此种方式不仅可以提升查询效率也可以节省大量的内存空间。
但实际上这种布隆过滤器的方式可能会产生误判
在是不一定准确的。hashFunc映射冲突不在一定是准确的。 可能存在是因为映射可能出现重复即产生冲突这是布隆过滤器无法避免的但是可以通过增加HashFunc的映射次数从而降低冲突引起的误判率。 如图映射之后当查找时如果三个映射值都不为0那么可以大概认为这个变量是存在的。映射越多越准确当然映射越多的话同样会浪费空间因此需要根据需求设计HashFunc的个数。
如何选择哈希函数个数和布隆过滤器长度
很显然过小的布隆过滤器很快所有的 bit 位均为 1那么查询任何值都会返回“可能存在”起不到过滤的目的了。布隆过滤器的长度会直接影响误报率布隆过滤器越长其误报率越小。
另外哈希函数的个数也需要权衡个数越多则布隆过滤器 bit 位置位 1 的速度越快且布隆过滤器的效率越低但是如果太少的话那我们的误报率会变高。
k 为哈希函数个数m 为布隆过滤器长度n 为插入的元素个数p 为误报率 如何选择适合业务的 k 和 m 值呢这里直接贴一个公式km∗ln2/nk m*ln2 / nkm∗ln2/n
可以看出当k3时m≈4.2*n。因此下面代码中我们采用5*N大小的布隆过滤器长度无疑是非常合适的。
三. 布隆过滤器的操作
上述虽然将大致的思路提到但还是需要具体描述一下步骤
3.1 布隆过滤器的插入 向布隆过滤器中插入“baidu” 此过程就需要用到指定的HashFunc了。
3.2 布隆过滤器的查找
布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找分别计算每个哈希值对应的比特位置存储的是否为零只要有一个为零代表该元素一定不在哈希表中否则可能在哈希表中。 注意布隆过滤器如果说某个元素不存在时该元素一定不存在如果该元素存在时该元素可能存在因为有些哈希函数存在一定的误判。 比如在布隆过滤器中查找alibaba时假设3个哈希函数计算的哈希值为1、3、7刚好和其他元素的比特位重叠此时布隆过滤器告诉该元素存在但实该元素是不存在的。
3.3 布隆过滤器的删除
布隆过滤器不能直接支持删除工作因为在删除一个元素时可能会影响其他元素。
比如删除上图中tencent元素如果直接将该元素所对应的二进制比特位置0“baidu”元素也被删除了因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。
一种支持删除的方法将布隆过滤器中的每个比特位扩展成一个小的计数器插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一删除元素时给k个计数器减一通过多占用几倍存储空间的代价来增加删除操作。
缺陷
无法确认元素是否真正在布隆过滤器中存在计数回绕
四.布隆过滤器的代码
4.1 HashFunc的仿函数参考
各种字符串Hash函数 - clq - 博客园 (cnblogs.com)
我们没必要重复造轮子因此直接采用上面链接的仿函数即可有评分高的选高的有需要就稍微改一下参数类型即可。
4.2 BloomFilter.h
#pragma once
#includebitset//设置的仿函数
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;}
};templatesize_t N,size_t X 5,class K string,class HashFunc1 BKDRHash,class HashFunc2 APHash,class HashFunc3 DJBHashclass BloomFilter
{
public:void set(const K key){size_t hash1 HashFunc1()(key) % (X * N);size_t hash2 HashFunc2()(key) % (X * N);size_t hash3 HashFunc3()(key) % (X * N);_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);}bool test(const K key){size_t hash1 HashFunc1()(key) % (X * N);if (!_bs.test(hash1))//如果不在没必要往后走了{return false;//不存在误判}size_t hash2 HashFunc2()(key) % (X * N);if (!_bs.test(hash2))//如果不在没必要往后走了{return false;//不存在误判}size_t hash3 HashFunc3()(key) % (X * N);if (!_bs.test(hash3))//如果不在没必要往后走了{return false;//不存在误判}return true;//可能存在误判}
private:std::bitsetN * X _bs;};通过大量的数据可以判断冲突率
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;
}通过控制X,X越大空间就越大越不易产生冲突误判率越低。当然增加HashFunc也可以降低误判率。
五.布隆过滤器的优缺点
优点 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数一般比较小)与数据量大小无关 哈希函数相互之间没有关系方便硬件并行运算 布隆过滤器不需要存储元素本身在某些对保密要求比较严格的场合有很大优势 在能够承受一定的误判时布隆过滤器比其他数据结构有这很大的空间优势 数据量很大时布隆过滤器可以表示全集其他数据结构不能 使用同一组散列函数的布隆过滤器可以进行交、并、差运算
缺点
有误判率即存在假阳性(False Position)即不能准确判断元素是否在集合中(补救方法再 建立一个白名单存储可能会误判的数据)不能获取元素本身一般情况下不能从布隆过滤器中删除元素如果采用计数方式删除可能会存在计数回绕问题
六.布隆过滤器的应用场景
不需要一定准确的场景。注册时候的昵称判重。提高效率 在客户端和数据库之间建立一个布隆过滤器如果通过布隆的结果发现没有找到那么一定不在也就不用继续向数据库中查找了。如果在那么就需要进数据库中一一查找因为布隆对于找到的值是不一定存在的。所以通过布隆可以提高数据不在时查找的效率。
