php+Redis实现由于Redis实现了setbit和getbit操作，自然适合实现Bloomfilters，redis也有Bloomfilter插件。这里使用php+redis来实现Bloomfilter。首先定义一个散列函数集合类。不得使用这些散列函数。其实三个32位的哈希值就够了。具体数量可以根据你的比特序列的总量和你需要存储的数量来决定。,上面已经给出了最佳值。classBloomFilterHash{/***JustinSobel编写的按位哈希函数*/publicfunctionJSHash($string,$len=null){$hash=1315423911;$len||$len=strlen($字符串);对于($i=0;$i<$len;$i++){$hash^=(($hash<<5)+ord($string[$i])+($hash>>2));}返回（$hash%0xFFFFFFFF）&0xFFFFFFFF；}/***该散列算法基于AT&T贝尔实验室的PeterJ.Weinberger的工作。*AhoSethi和Ulman合着的《Compilers(Principles,Techniques,andTools)》一书推荐使用散列函数，在这个特定的算法中采用散列方法。*/publicfunctionPJWHash($string,$len=null){$bitsInUnsignedInt=4*8;//(无符号整数)(sizeof(无符号整数)*8);$threeQuarters=($bitsInUnsignedInt*3)/4;$oneEighth=$bitsInUnsignedInt/8;$highBits=0xFFFFFFFF<<(int)($bitsInUnsignedInt-$oneEighth);$散列=0;$测试=0；$len||$len=strlen($字符串);for($i=0;$i<$len;$i++){$hash=($hash<<(int)($oneEighth))+ord($string[$i]);$test=$hash&$highBits;如果（$test!=0）{$hash=(($hash^($test>>(int)($threeQuarters)))&(~$highBits));}返回（$hash%0xFFFFFFFF）&0xFFFFFFFF；}/***类似于PJW哈希函数，但针对32位处理器进行了调整。它广泛用于基于UNIX的系统以使用哈希函数。*/publicfunctionELFHash($string,$len=null){$hash=0;$len||$len=strlen($字符串);对于($i=0;$i<$len;$i++){$hash=($hash<<4)+ord($string[$i]);$x=$hash&0xF0000000;如果($x!=0){$hash^=($x>>24);}$hash&=~$x;}返回（$hash%0xFFFFFFFF）&0xFFFFFFFF；}/***此散列函数来自BrianKernighan和DennisRitchie合着的《TheCProgrammingLanguage》一书。*这是一个简单的哈希函数，使用一组奇怪的可能种子，这些种子全部形成模式31....31...31等。它似乎与DJB哈希函数非常相似。*/publicfunctionBKDRHash($string,$len=null){$seed=131;#31131131313131131313等等。$hash=0;$len||$len=strlen($字符串);对于($i=0;$i<$len;$i++){$hash=(int)(($hash*$seed)+ord($string[$i]));}返回($hash%0xFFFFFFFF)&0xFFFFFFFF;}/***这是开源SDBM项目中使用的首选算法。*哈希函数似乎对许多不同的数据集具有良好的整体分布。它似乎适用于数据集中元素的MSB存在高方差的情况。*/publicfunctionSDBMHash($string,$len=null){$hash=0;$len||$len=strlen($字符串);对于($i=0;$i<$len;$i++){$hash=(int)(ord($string[$i])+($hash<<6)+($hash<<16)-$哈希）；}返回（$hash%0xFFFFFFFF）&0xFFFFFFFF；}/***由DanielJ.Bernstein教授制作的算法，首次在usenet新闻组comp.lang.c上向全世界展示。*它是有史以来最高效的哈希函数之一。*/publicfunctionDJBHash($string,$len=null){$hash=5381;$len||$len=strlen($字符串);对于($i=0;$i<$len;$i++){$hash=(int)(($hash<<5)+$hash)+ord($string[$i]);}返回（$hash%0xFFFFFFFF）&0xFFFFFFFF；/***DonaldE.Knuth在“计算机编程艺术第3卷”主题排序和搜索第6.4章中介绍了算法。*/publicfunctionDEKHash($string,$len=null){$len||$len=strlen($字符串);$散列=$len;对于($i=0;$i<$len;$i++){$hash=(($hash<<5)^($hash>>27))^ord($string[$i]);}返回（$hash%0xFFFFFFFF）&0xFFFFFFFF；}/***参考http://www.isthe.com/chongo/tech/comp/fnv/*/publicfunctionFNVHash($string,$len=null){$prime=16777619;//32位素数2^24+2^8+0x93=16777619$hash=2166136261;//32位偏移$len||$len=strlen($字符串);对于($i=0;$i<$len;$i++){$hash=(int)($hash*$prime)%0xFFFFFFFF;$hash^=ord($string[$i]);}返回（$hash%0xFFFFFFFF）&0xFFFFFFFF；}}然后连接redis进行操作/***使用redis实现的Bloomfilter*/abstractclassBloomFilterRedis{/***需要使用方法定义bucket的名字*/protected$bucket;受保护的$hashFunction；公共职能__construct($config,$id){if(!$this->bucket||!$this->hashFunction){thrownewException("需要定义bucket和hashFunction",1);}$this->Hash=newBloomFilterHash;$this->Redis=newYourRedis;//假设你已经在这里连接}/***添加到集合*/publicfunctionadd($string){$pipe=$this->Redis->multi();foreach($this->hashFunctionas$function){$hash=$this->Hash->$function($string);}$pipe->setBit($this->bucket,$hash,1);}返回$pipe->exec();}/***查询是否存在，如果已经写入，则必须返回true，如果没有写入，有一定几率会误判为存在*/publicfunctionexists($string){$pipe=$this->Redis->multi();$len=strlen($字符串);foreach($this->hashFunctionas$function){$hash=$this->Hash->$function($string,$len);}$pipe=$pipe->getBit($this->bucket,$hash);}$res=$pipe->exec();foreach($resas$bit){if($bit==0){返回假；}}返回真；}}上面定义的是一个抽象类，如果要使用，可以根据具体业务来使用。例如，下面是一个过滤重复内容的过滤器。/***Duplicatecontentfilter*布隆过滤器的总位数为2^32位，判断项数为2^30。最佳哈希函数数为3。（最大可容忍的哈希函数数）*使用的三个哈希函数是*BKDR,SDBM,JSHash**注意当存储数据量达到2^30时，误判率会急剧上升，所以需要定时判断filter中的bit是否为1的个数是否超过50%，超过则需要清零。*/classFilteRepeatedCommentsextendsBloomFilterRedis{/***表示判断重复内容的过滤器*@varstring*/protected$bucket='rptc';protected$hashFunction=array('BKDRHash','SDBMHash','JSHash');}
