泉州建站模板源码,网站的页面风格有哪些,站长平台官网,医疗器械注册证文章目录 布隆过滤器提出布隆过滤器概念布隆过滤器应用场景设计思路:布隆过滤器的插入布隆过滤器的查找布隆过滤器删除BloomFilter.h布隆过滤器优点布隆过滤器缺陷 布隆过滤器提出
我们在使用新闻客户端看新闻时,它会给我们不停地推荐新的内容,它每次推荐时要去重,去掉那些已经… 文章目录 布隆过滤器提出布隆过滤器概念布隆过滤器应用场景设计思路:布隆过滤器的插入布隆过滤器的查找布隆过滤器删除BloomFilter.h布隆过滤器优点布隆过滤器缺陷 布隆过滤器提出
我们在使用新闻客户端看新闻时,它会给我们不停地推荐新的内容,它每次推荐时要去重,去掉那些已经看过的内容 问题来了,新闻客户端推荐系统如何实现推送去重的 答:用服务器记录了用户看过的所有历史记录,当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选,过滤掉那些已经存在的记录 那问题又来了,如何快速查找呢 用哈希表存储用户记录,缺点浪费空间用位图存储用户记录,缺点不能处理哈希冲突将哈希与位图结合,即布隆过滤器 布隆过滤器概念
位图:节省空间,效率高 ,但是有局限性:只能处理整数 但是布隆过滤器可以处理字符串,自定义类型 布隆过滤器是由布隆Burton Howard Bloom在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构,特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”,它是用多个哈希函数,将一个数据映射到位图结构中,此种方式不仅可以提升查询效率,也可以节省大量的内存空间 例子: 布隆过滤器中一个值通过多个哈希函数,在位图中有多个映射位置,即使一个位置发生冲突了,还有另外的映射的值,降低了冲突的概率,由于映射多个位置,因此可能不同的值,处于同一个位置,虽然不能保证这个值一定存在,但是可以保证一个值一定不存在,因为只要有一个映射的位置为0,就说明该值不存在 问题:布隆过滤器会误判存在还是会误判不存在? 存在可能会误判 因为会产生哈希冲突,不同的字符串可能会映射在同一个位置, 一个字符串不存在但是可能会被误判成存在为了减少减少误判,通常采用多个哈希函数来映射多个位置 即一个值映射多个位置
是一定会有哈希冲突的因为整数是有限的,字符串是无限的 布隆过滤器应用场景
布隆过滤器会存在误判,所以通常应用在允许误判的场景之中
一般应用场景:数据量大,节省空间,允许误判 黑名单校验 发现存在黑名单中的,就执行特定操作,比如识别垃圾邮件,只要是邮箱在黑名单中的邮件,就识别为垃圾邮件,假设黑名单的数量是数以亿计的,存放起来就是非常耗费存储空间的,布隆过滤器则是一个较好的解决方案,把所有黑名单都放在布隆过滤器中,再收到邮件时,判断邮件地址是否在布隆过滤器中即可, 身份验证 大门口的身份验证,如果不是小区里面的人,直接就拒绝进入(不在是确定的),如果通过了布隆过滤器的判断,再去数据库中对比一次,这样通过一层布隆过滤器可以提高这个查找系统的效率 检测手机号是否注册过 系统所有用户的电话号码都存储再数据库的用户表 . 如果这个手机号不在布隆过滤器就肯定没有注册过, 如果在布隆过滤器,那么这里可能存在误判,再查一次数据库复核一下 设计思路:
首先我们需要确定位图开辟多大的空间 假设k为3, 则-位图的大小大致应该为: m 4.2*n 先准备几个哈希函数用于将字符串转为整形
//BKDR算法
struct BKDRHash
{size_t operator()(const string s){// BKDRsize_t value 0;for (auto ch : s){value * 31;value ch;}return value;}
};struct APHash
{size_t operator()(const string s){size_t hash 0;for (long i 0; i s.size(); i){if ((i 1) 0){hash ^ ((hash 7) ^ s[i] ^ (hash 3));}else{hash ^ (~((hash 11) ^ s[i] ^ (hash 5)));}}return hash;}
};struct DJBHash
{size_t operator()(const string s){size_t hash 5381;for (auto ch : s){hash (hash 5) ch;}return hash;}
};templatesize_t N 非类型模板参数,共插入多少个值
size_t X 4, //X值越大,产生冲突的概率越低, N*X表示位图开辟多少个比特位空间,利用公式计算X
class K string,
class HashFunc1 BKDRHash,//一个字符串想映射几个比特位就给几个HashFunc仿函数计算哈希地址
class HashFunc2 APHash,
class HashFunc3 DJBHashclass BloomFilter
{
public:
private:bitsetX*N _bs;
};布隆过滤器的插入
将值对应的每个哈希函数计算出的位置都置为1
//将key所映射的位置设为1
void Set(const K key)
{size_t len N * X;//总长度 //计算映射的哈希地址 HashFunc()是匿名对象size_t index1 HashFunc1()(key) % len;size_t index2 HashFunc2()(key) % len;size_t index3 HashFunc3()(key) % len;//将对应的映射位置标志为1_bs.set(index1);_bs.set(index2);_bs.set(index3);
}布隆过滤器的查找
布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中 因此被映射到的位置的比特位一定为1,所以可以按照以下方式进行查找
分别计算每个哈希值对应的比特位置存储的是否为0, 只要有一个映射位置为0代表该元素一定不在哈希表中否则可能在哈希表中(因为存在误判)
//判断key是否在布隆过滤器中
bool Test(const K key)
{//三个映射为都是1才在(可能存在误判),其中一个不是1就不在size_t len N * X;size_t index1 HashFunc1()(key) % len;size_t index2 HashFunc2()(key) % len;size_t index3 HashFunc3()(key) % len;if ( (!_bs.test(index1)) || (!_bs.test(index2)) || (!_bs.test(index3))){return false;}return true;//可能存在误判
}注意布隆过滤器如果说某个元素不存在时,该元素一定不存在, 如果**该元素存在时,该元素可能存在也可能不存在.**因为有些哈希函数存在一定的误判 布隆过滤器删除
布隆过滤器不能直接支持删除工作, 因为在删除一个元素时可能会影响其他元素,因为不确定当前位置,是自己的,还是发生了哈希冲突其它的值映射过来的 如何支持修改呢? -存储引用计数(有几个值映射在当前位置) 将布隆过滤器中的每个比特位扩展成一个小的计数器,插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一, 删除元素时给k个计数器减一,通过多占用几倍存储空间的代价来增加删除操作
但是这种方法不太好, 因为计数器的大小不易确定,如果给小了,发生冲突会导致溢出(计数回绕:即最大值溢出变为 最小值) 如果给大了浪费空间,脱离了布隆过滤器的本质思想,
缺陷
无法确认元素是否真正在布隆过滤器中存在计数回绕
BloomFilter.h
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once//BKDR算法
struct BKDRHash
{size_t operator()(const string s){// BKDRsize_t value 0;for (auto ch : s){value * 31;value ch;}return value;}
};struct APHash
{size_t operator()(const string s){size_t hash 0;for (long i 0; i s.size(); i){if ((i 1) 0){hash ^ ((hash 7) ^ s[i] ^ (hash 3));}else{hash ^ (~((hash 11) ^ s[i] ^ (hash 5)));}}return hash;}
};struct DJBHash
{size_t operator()(const string s){size_t hash 5381;for (auto ch : s){hash (hash 5) ch;}return hash;}
};templatesize_t N, 非类型模板参数,共插入多少个值
size_t X 4, //X值越大,产生冲突的概率越低, N*X表示位图开辟多少个比特位空间
class K string,// 假设布隆过滤器中元素类型为K,默认为string类型
//每个元素对应3个哈希函数
class HashFunc1 BKDRHash,//一个字符串想映射几个比特位就给几个HashFunc仿函数计算哈希地址
class HashFunc2 APHash,
class HashFunc3 DJBHash
class BloomFilter
{
public://将key所在的三个映射位设为1void Set(const K key){size_t len N * X;//总长度 //计算映射的哈希地址 HashFunc()是匿名对象size_t index1 HashFunc1()(key) % len;size_t index2 HashFunc2()(key) % len;size_t index3 HashFunc3()(key) % len;//将对应的映射位置标志为1_bs.set(index1);_bs.set(index2);_bs.set(index3);}//判断key是否在布隆过滤器中bool Test(const K key){//三个映射为都是1才在(可能存在误判),其中一个不是1就不在size_t len N * X;size_t index1 HashFunc1()(key) % len;size_t index2 HashFunc2()(key) % len;size_t index3 HashFunc3()(key) % len;if ( (!_bs.test(index1)) || (!_bs.test(index2)) || (!_bs.test(index3))){return false;}return true;//可能存在误判 }
// 不支持删除,删除可能会影响其他值,
// 一般情况不支持删除,why?-多个值可能会标记一个位,删除可能会影响其他key
// 如果非要支持删除的话,标记不再使用一个比特位,可以使用多个比特位,进行计数多少个值映射的这个比特位
// 但是这种方法是杀敌一千,自损八百的做法,因为消耗的更多的空间void Reset(const K key);
private://此时k为3 则此时位图的大小大致应该为: m 4.2*n 即X 4bitsetN*X _bs;
};
void TestBloomFilter()
{BloomFilter100 bf;//最多存100个值 -》开辟100*4个比特位srand(time(0));size_t N 100;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(6789 i);v2.push_back(url);}size_t n2 0;for (auto str : v2){if (bf.Test(str)){n2;}}cout 相似字符串误判率: (double)n2 / (double)N endl;
}布隆过滤器优点 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数,一般比较小),与数据量大小无关 哈希函数相互之间没有关系,方便硬件并行运算 布隆过滤器不需要存储元素本身,在某些对保密要求比较严格的场合有很大优势 在能够承受一定的误判时,布隆过滤器比其他数据结构有这很大的空间优势 数据量很大时,布隆过滤器可以表示全集,其他数据结构不能 使用同一组散列函数的布隆过滤器可以进行交、并、差运算 布隆过滤器缺陷
有误判率,即存在假阳性(False Position),即不能准确判断元素是否在集合中(补救方法再建立一个白名单,存储可能会误判的数据)不能获取元素本身一般情况下不能从布隆过滤器中删除元素如果采用计数方式删除,可能会存在计数回绕问题
