手机主题如何自己制作网站,慈溪建设银行支行网站,福州自助建站,免费企业网站建设技术一、问题概述 布隆过滤器是由布隆提出来的#xff0c;是由一个很长的二进制序列和一系列的映射函数组成。主要用于检测一个元素是否在一个集合中。当然在设计计算机软件时#xff0c;我们也经常会判断一个元素是否在一个集合中。比如#xff1a;在字处理软件中#xff0c;…一、问题概述 布隆过滤器是由布隆提出来的是由一个很长的二进制序列和一系列的映射函数组成。主要用于检测一个元素是否在一个集合中。当然在设计计算机软件时我们也经常会判断一个元素是否在一个集合中。比如在字处理软件中需要检查一个英语单词是否拼写正确即是否在字典中在网络爬虫里这个网站是否被访问过。最直接的方法就是将元素都存入计算机中遇到一个新元素时将它和元素进行比较即可。一般是用哈希表存储的因为它的查询速度快就是比较浪费空间。集合小的时候存储效率还好当集合大的时候存储效率低的问题就显现出来了。再比如对于一个像 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件提供商总是需要过滤来自发送垃圾邮件的人的垃圾邮件。这时我们就得记录那些发垃圾邮件的Email地址由于那些发送者不停地在注册新的地址全世界少说也有几十亿个发垃圾邮件的地址将他们都存起来则需要大量的网络服务器。如果用哈希表每存储一亿个email地址就需要1.6GB 的内存因此存贮几十亿个邮件地址可能需要上百GB的内存。除非是超级计算机一般服务器是无法存储的。所以在这里我们就引入了布隆过滤器来处理这些问题。
二、布隆过滤器的基本思想 如果想判断一个元素是不是在一个集合里一般想到的是将所有元素保存起来然后通过比较确定。链表树等等数据结构都是这种思路. 但是随着集合中元素的增加我们需要的存储空间越来越大检索速度也越来越慢。不过世界上还有一种叫作散列表又叫哈希表Hash table的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列Bit Array中的一个点。这样一来我们只要看看这个点是不是1就知道可以集合中有没有它了。这就是布隆过滤器的基本思想。 布隆过滤器是一种空间效率很高的数据结构。也可以看做是位图BitMap的扩展位图链接
当一个元素加入集合中时通过k个不同的哈希函数将这个元素映射成一个位数组的k个点把它们置为1。当我们检测看一个元素存不存在时只需要看那k个位是否为1就可以了。主要分为两点
1、如果这k个位中只要有一个位为0就说明此元素不在集合中
2、如果k个位都为1的话表明此元素可能存在集合中。
第二点又体现了布隆过滤器的一个缺点存在一定的误判率。但是为了尽可能的降低这种误判率我们采用上述多个哈希函数检测的方式。经研究表明可将误判率降低到万分之一以下。
同时布隆过滤器的优点也是非常显著的。它的空间效率和查询时间都远远超过一般的算法。存储空间和插入/查询时间都是常数O(k)。
还有重要的一点是一般情况下布隆过滤器不支持删除操作起初有人会想到使用计数方式将位或--来删除元素。但是由于布隆过滤器的误判你可能会把错误的元素删除。下节我们会分析到这类问题哦
三、实现代码vs2013
//HashFunc.h #pragma once
#includestring
#includeiostream
using namespace std;/// brief BKDR Hash Function /// detail 本 算法由于在Brian Kernighan与Dennis Ritchie的《The C Programming Language》一书被展示而得 名是一种简单快捷的hash算法也是Java目前采用的字符串的Hash算法累乘因子为31。 templateclass T size_t BKDRHash(const T *str) { register size_t hash 0; while (size_t ch (size_t)*str) { hash hash * 131 ch; // 也可以乘以31、131、1313、13131、131313.. // 有人说将乘法分解为位运算及加减法可以提高效率如将上式表达为hash hash 7 hash 1 hash ch; // 但其实在Intel平台上CPU内部对二者的处理效率都是差不多的 // 我分别进行了100亿次的上述两种运算发现二者时间差距基本为0如果是Debug版分解成位运算后的耗时还要高1/3 // 在ARM这类RISC系统上没有测试过由于ARM内部使用Booths Algorithm来模拟32位整数乘法运算它的效率与乘数有关 // 当乘数8-31位都为1或0时需要1个时钟周期 // 当乘数16-31位都为1或0时需要2个时钟周期 // 当乘数24-31位都为1或0时需要3个时钟周期 // 否则需要4个时钟周期 // 因此虽然我没有实际测试但是我依然认为二者效率上差别不大 } return hash; } /// brief SDBM Hash Function /// detail 本算法是由于在开源项目SDBM一种简单的数据库引擎中被应用而得名它与BKDRHash思想一致只是种子不同而已。 templateclass T size_t SDBMHash(const T *str) { register size_t hash 0; while (size_t ch (size_t)*str) { hash 65599 * hash ch; //hash (size_t)ch (hash 6) (hash 16) - hash; } return hash; } /// brief RS Hash Function /// detail 因Robert Sedgwicks在其《Algorithms in C》一书中展示而得名。 templateclass T size_t RSHash(const T *str) { register size_t hash 0; size_t magic 63689; while (size_t ch (size_t)*str) { hash hash * magic ch; magic * 378551; } return hash; } /// brief AP Hash Function /// detail 由Arash Partow发明的一种hash算法。 templateclass T size_t APHash(const T *str) { register size_t hash 0; size_t ch; for (long i 0; ch (size_t)*str; i) { if ((i 1) 0) { hash ^ ((hash 7) ^ ch ^ (hash 3)); } else { hash ^ (~((hash 11) ^ ch ^ (hash 5))); } } return hash; } /// brief JS Hash Function /// 由Justin Sobel发明的一种hash算法。 templateclass T size_t JSHash(const T *str) { if(!*str) // 这是由本人添加以保证空字符串返回哈希值0 return 0; register size_t hash 1315423911; while (size_t ch (size_t)*str) { hash ^ ((hash 5) ch (hash 2)); } return hash; } /// brief DEK Function /// detail 本算法是由于Donald E. Knuth在《Art Of Computer Programming Volume 3》中展示而得名。 templateclass T size_t DEKHash(const T* str) { if(!*str) // 这是由本人添加以保证空字符串返回哈希值0 return 0; register size_t hash 1315423911; while (size_t ch (size_t)*str) { hash ((hash 5) ^ (hash 27)) ^ ch; } return hash; } /// brief FNV Hash Function /// detail Unix system系统中使用的一种著名hash算法后来微软也在其hash_map中实现。 templateclass T size_t FNVHash(const T* str) { if(!*str) // 这是由本人添加以保证空字符串返回哈希值0 return 0; register size_t hash 2166136261; while (size_t ch (size_t)*str) { hash * 16777619; hash ^ ch; } return hash; } /// brief DJB Hash Function /// detail 由Daniel J. Bernstein教授发明的一种hash算法。 templateclass T size_t DJBHash(const T *str) { if(!*str) // 这是由本人添加以保证空字符串返回哈希值0 return 0; register size_t hash 5381; while (size_t ch (size_t)*str) { hash (hash 5) ch; } return hash; } /// brief DJB Hash Function 2 /// detail 由Daniel J. Bernstein 发明的另一种hash算法。 templateclass T size_t DJB2Hash(const T *str) { if(!*str) // 这是由本人添加以保证空字符串返回哈希值0 return 0; register size_t hash 5381; while (size_t ch (size_t)*str) { hash hash * 33 ^ ch; } return hash; } /// brief PJW Hash Function /// detail 本算法是基于ATT贝尔实验室的Peter J. Weinberger的论文而发明的一种hash算法。 templateclass T size_t PJWHash(const T *str) {static const size_t TotalBits sizeof(size_t) * 8; static const size_t ThreeQuarters (TotalBits * 3) / 4; static const size_t OneEighth TotalBits / 8; static const size_t HighBits ((size_t)-1) (TotalBits - OneEighth); register size_t hash 0; size_t magic 0; while (size_t ch (size_t)*str) { hash (hash OneEighth) ch; if ((magic hash HighBits) ! 0) { hash ((hash ^ (magic ThreeQuarters)) (~HighBits)); } } return hash; } /// brief ELF Hash Function /// detail 由于在Unix的Extended Library Function被附带而得名的一种hash算法它其实就是PJW Hash的变形。 templateclass T size_t ELFHash(const T *str) { static const size_t TotalBits sizeof(size_t) * 8; static const size_t ThreeQuarters (TotalBits * 3) / 4; static const size_t OneEighth TotalBits / 8; static const size_t HighBits ((size_t)-1) (TotalBits - OneEighth); register size_t hash 0; size_t magic 0; while (size_t ch (size_t)*str) { hash (hash OneEighth) ch; if ((magic hash HighBits) ! 0) { hash ^ (magic ThreeQuarters); hash ~magic; } } return hash; } //BloomFilter.h #pragma once
#includestring
#includeiostream
using namespace std;
#includeBitMap.h
#includeHashFunc.h
struct _HashFunc1
{size_t operator()(const string s){return BKDRHash(s.c_str());}
};struct _HashFunc2
{size_t operator()(const string s){return SDBMHash(s.c_str());}
};struct _HashFunc3
{size_t operator()(const string s){return RSHash(s.c_str());}
};struct _HashFunc4
{size_t operator()(const string s){return APHash(s.c_str());}
};struct _HashFunc5
{size_t operator()(const string s){return JSHash(s.c_str());}
};templateclass K string,
class HashFunc1 _HashFunc1,
class HashFunc2 _HashFunc2,
class HashFunc3 _HashFunc3,
class HashFunc4 _HashFunc4,
class HashFunc5 _HashFunc5class BloomFilter
{
public:BloomFilter(size_t Num):_bm(Num*5*2),_size(Num*5*2){}void BloomSet(const K key){size_t Hash1 HashFunc1()(key)%_size;size_t Hash2 HashFunc2()(key)%_size;size_t Hash3 HashFunc3()(key)%_size;size_t Hash4 HashFunc4()(key)%_size;size_t Hash5 HashFunc5()(key)%_size;_bm.Set(Hash1);_bm.Set(Hash2);_bm.Set(Hash3);_bm.Set(Hash4);_bm.Set(Hash5);}bool Test(const K key){size_t Hash1 HashFunc1()(key)%_size;if(_bm.Test(Hash1) false){return false;}size_t Hash2 HashFunc2()(key)%_size;if(_bm.Test(Hash2) false){return false;}size_t Hash3 HashFunc3()(key)%_size;if(_bm.Test(Hash3) false){return false;}size_t Hash4 HashFunc4()(key)%_size;if(_bm.Test(Hash4) false){return false;}size_t Hash5 HashFunc5()(key)%_size;if(_bm.Test(Hash5) false){return false;}return true;}
private:BitMap _bm;size_t _size;
};void BloomFilterTest()
{BloomFilter bm(1024);bm.BloomSet(11111);bm.BloomSet(11110);bm.BloomSet(11112);bm.BloomSet(11113);coutbm.Test(11111)endl;coutbm.Test(11101)endl;coutbm.Test(11102)endl;coutbm.Test(11113)endl;}四、运行结果
