最强的手机网站建设,原画培训机构排行榜,网红营销的优势,唐山网站建设多少钱文章目录一、布隆过滤器概念二、布隆过滤器应用三、布隆过滤器实现1.插入2.查找3.删除四、布隆过滤器优缺五、结语一、布隆过滤器概念 布隆过滤器是由布隆#xff08;Burton Howard Bloom#xff09;在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构#xff0c;特点是…
文章目录一、布隆过滤器概念二、布隆过滤器应用三、布隆过滤器实现1.插入2.查找3.删除四、布隆过滤器优缺五、结语一、布隆过滤器概念 布隆过滤器是由布隆Burton Howard Bloom在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构特点是高效地插入和查询可以用来告诉你 “某样东西一定不存在或者可能存在”它是用多个哈希函数将一个数据映射到位图结构中。此种方式不仅可以提升查询效率也可以节省大量的内存空间 . 位图的优点是节省空间快缺点是要求范围相对集中如果范围分散空间消耗上升同时只能针对整型字符串通过哈希转化成整型再去映射对于整型没有冲突因为整型是有限的映射唯一的位置但是对于字符串来说是无限的会发生冲突会发生误判此时的情况的是不在是正确的在是不正确的因为可能不来是不在的但是位置跟别人发生冲突发生误判
此时布隆过滤器就登场了可以降低误判率让一个值映射多个位置但是并不是消除误判 可能还是会出现误判 虽然布隆过滤器还是会出现误判因为这个数据的比特位被其他数据所占但是判断一个数据不存在是准确不存在就是0 布隆过滤器改进映射多个位置降低误判率位置越多消耗也越多
如果布隆过滤器长度比较小比特位很快会被占为1误判率自然会上升所以布隆过滤器的长度会影响误判率理论上来说如果一个值映射的位置越多则误判的概率越小但是并不是位置越多越好空间也会消耗大佬们自然也能够想得到所以有公式 我们可以来估算一下假设用 3 个哈希函数即K3ln2 的值我们取 0.7那么 m 和 n 的关系大概是 m n×k/ln24.2n 也就是过滤器长度应该是插入元素个数的 4 -5倍 二、布隆过滤器应用
不需要一定准确的场景。比如游戏注册时候的昵称的判重如果不在那就是不在没被使用在的话可能会被误判。
提高查找效率客户端中查找一个用户的ID与服务器中的是否相同在增加一层布隆过滤器提高查找效率 三、布隆过滤器实现
布隆过滤器的插入元素可能是字符串也可能是其他类型只要提供对应的哈希函数将该类型的数据转换成整型就可以了。
一般情况下布隆过滤器都是用来处理字符串的所以布隆过滤器可以实现为一个模板类将模板参数 T 的缺省类型设置为 string
template size_t N,size_t X 5,class Kstring,class HashFunc1 BKDRHash,class HashFunc2 APHash,class HashFunc3 DJBHash
class BloomFilter{public:private:bitsetN * X _bs;};这里布隆过滤器提供三个哈希函数由于布隆过滤器一般处理的是字符串类型的数据所以我们默认提供几个将字符串转换成整型的哈希函数选取综合评分最高的 BKDRHash、APHash 和 DJBHash这三种哈希算法 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){size_t 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){size_t hash 5318;for (auto ch : key){hash (hash 5) ch;}return hash;}};1.插入
布隆过滤器复用bitset的 set 接口用于插入元素插入元素时我们通过上面的三个哈希函数分别计算出该元素对应的三个比特位然后在位图中设置为1即可 void set(const K key){size_t hash1 HashFunc1()(key) % (N * X);size_t hash2 HashFunc2()(key) % (N * X);size_t hash3 HashFunc3()(key) % (N * X);_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);_bs.set(hash4);}2.查找
通过三个哈希函数分别算出对应元素的三个哈希地址得到对应的比特位然后去判断这三个比特位是否都被设置成了1
如果出现一个比特位未被设置成1说明该元素一定不存在也就是如果一个比特位为0就是false而如果三个比特位全部都被设置则return true表示该元素已经存在注可能会出现误判 bool test(const K key){size_t hash1 HashFunc1()(key) % (N * X);if (!_bs.test(hash1)){return false;}size_t hash2 HashFunc2()(key) % (N * X);if (!_bs.test(hash2)){return false;}size_t hash3 HashFunc3()(key) % (N * X);if (!_bs.test(hash3)){return false;}return true;}3.删除
布隆过滤器一般没有删除因为布隆过滤器判断一个元素是会存在误判此时无法保证要删除的元素在布隆过滤器中如果此时将位图中对应的比特位清0就会影响到其他元素了 这时候我们只需要在每个比特位加一个计数器当存在插入操作时在计数器里面进行 删除后对该位置进行 -- 即可
但是布隆过滤器的本来目的就是为了提高效率和节省空间在每个比特位增加额外的计数器空间消耗那就更多了 四、布隆过滤器优缺
优 \1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数一般比较小)与数据量大小无关 \2. 哈希函数相互之间没有关系方便硬件并行运算 \3. 布隆过滤器不需要存储元素本身在某些对保密要求比较严格的场合有很大优势 \4. 在能够承受一定的误判时布隆过滤器比其他数据结构有这很大的空间优势 \5. 数据量很大时布隆过滤器可以表示全集其他数据结构不能 \6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算 缺 \1. 有误判率不能准确判断元素是否在集合中(补救方法再建立一个白名单存储可能会误判的数据) \2. 不能获取元素本身 \3. 一般情况下不能从布隆过滤器中删除元素 五、结语
给两个文件分别有100亿个query我们只有1G内存如何找到两个文件交集分别给出精确算法和近似算法
近似算法利用布隆过滤器交集的就一定会进去但是可能会存在误判不同的也会进去这是近似
精准算法query一般是查询指令比如可能是网络请求或者是一个数据库sql语句
100亿个query,假设平均每个query是50byte则100亿个query那就是合计500GB
相同的query是一定进入相同编号的小文件再对这些文件放进内存的两个set中编号相同的Ai和Bi小文件找交集即可 本篇结束…
