先定義一個hash函數集合類,這些hash函數不一定都用到,實際上32位hash值的用3個就可以了,具體的數量可以根據你的位序列總量和你需要存入的量決定,上面已經給出最佳值。
class BloomFilterHash { /** * 由Justin Sobel编写的按位散列函数 */ public function JSHash($string, $len = null) { $hash = 1315423911; $len || $len = strlen($string); for ($i=0; $i<$len; $i++) { $hash ^= (($hash << 5) + ord($string[$i]) + ($hash >> 2)); } return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF; } /** * 该哈希算法基于AT&T贝尔实验室的Peter J. Weinberger的工作。 * Aho Sethi和Ulman编写的“编译器(原理,技术和工具)”一书建议使用采用此特定算法中的散列方法的散列函数。 */ public function PJWHash($string, $len = null) { $bitsInUnsignedInt = 4 * 8; //(unsigned int)(sizeof(unsigned int)* 8); $threeQuarters = ($bitsInUnsignedInt * 3) / 4; $oneEighth = $bitsInUnsignedInt / 8; $highBits = 0xFFFFFFFF << (int) ($bitsInUnsignedInt - $oneEighth); $hash = 0; $test = 0; $len || $len = strlen($string); for($i=0; $i<$len; $i++) { $hash = ($hash << (int) ($oneEighth)) + ord($string[$i]); } $test = $hash & $highBits; if ($test != 0) { $hash = (($hash ^ ($test >> (int)($threeQuarters))) & (~$highBits)); } return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF; } /** * 类似于PJW Hash功能,但针对32位处理器进行了调整。它是基于UNIX的系统上的widley使用哈希函数。 */ public function ELFHash($string, $len = null) { $hash = 0; $len || $len = strlen($string); for ($i=0; $i<$len; $i++) { $hash = ($hash << 4) + ord($string[$i]); $x = $hash & 0xF0000000; if ($x != 0) { $hash ^= ($x >> 24); } $hash &= ~$x; } return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF; } /** * 这个哈希函数来自Brian Kernighan和Dennis Ritchie的书“The C Programming Language”。 * 它是一个简单的哈希函数,使用一组奇怪的可能种子,它们都构成了31 .... 31 ... 31等模式,它似乎与DJB哈希函数非常相似。 */ public function BKDRHash($string, $len = null) { $seed = 131; # 31 131 1313 13131 131313 etc.. $hash = 0; $len || $len = strlen($string); for ($i=0; $i<$len; $i++) { $hash = (int) (($hash * $seed) + ord($string[$i])); } return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF; } /** * 这是在开源SDBM项目中使用的首选算法。 * 哈希函数似乎对许多不同的数据集具有良好的总体分布。它似乎适用于数据集中元素的MSB存在高差异的情况。 */ public function SDBMHash($string, $len = null) { $hash = 0; $len || $len = strlen($string); for ($i=0; $i<$len; $i++) { $hash = (int) (ord($string[$i]) + ($hash << 6) + ($hash << 16) - $hash); } return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF; } /** * 由Daniel J. Bernstein教授制作的算法,首先在usenet新闻组comp.lang.c上向世界展示。 * 它是有史以来发布的最有效的哈希函数之一。 */ public function DJBHash($string, $len = null) { $hash = 5381; $len || $len = strlen($string); for ($i=0; $i<$len; $i++) { $hash = (int) (($hash << 5) + $hash) + ord($string[$i]); } return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF; } /** * Donald E. Knuth在“计算机编程艺术第3卷”中提出的算法,主题是排序和搜索第6.4章。 */ public function DEKHash($string, $len = null) { $len || $len = strlen($string); $hash = $len; for ($i=0; $i<$len; $i++) { $hash = (($hash << 5) ^ ($hash >> 27)) ^ ord($string[$i]); } return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF; } /** * 参考 http://www.isthe.com/chongo/tech/comp/fnv/ */ public function FNVHash($string, $len = null) { $prime = 16777619; //32位的prime 2^24 + 2^8 + 0x93 = 16777619 $hash = 2166136261; //32位的offset $len || $len = strlen($string); for ($i=0; $i<$len; $i++) { $hash = (int) ($hash * $prime) % 0xFFFFFFFF; $hash ^= ord($string[$i]); } return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF; } }
接著就是連接redis來進行操作
/** * 使用redis实现的布隆过滤器 */ abstract class BloomFilterRedis { /** * 需要使用一个方法来定义bucket的名字 */ protected $bucket; protected $hashFunction; public function __construct($config, $id) { if (!$this->bucket || !$this->hashFunction) { throw new Exception("需要定义bucket和hashFunction", 1); } $this->Hash = new BloomFilterHash; $this->Redis = new YourRedis; //假设这里你已经连接好了 } /** * 添加到集合中 */ public function add($string) { $pipe = $this->Redis->multi(); foreach ($this->hashFunction as $function) { $hash = $this->Hash->$function($string); $pipe->setBit($this->bucket, $hash, 1); } return $pipe->exec(); } /** * 查询是否存在, 如果曾经写入过,必定回true,如果没写入过,有一定几率会误判为存在 */ public function exists($string) { $pipe = $this->Redis->multi(); $len = strlen($string); foreach ($this->hashFunction as $function) { $hash = $this->Hash->$function($string, $len); $pipe = $pipe->getBit($this->bucket, $hash); } $res = $pipe->exec(); foreach ($res as $bit) { if ($bit == 0) { return false; } } return true; } }
上面定義的是一個抽象類,如果要使用,可以根據具體的業務來使用。例如下面是一個過濾重複內容的過濾器。
/** * 重复内容过滤器 * 该布隆过滤器总位数为2^32位, 判断条数为2^30条. hash函数最优为3个.(能够容忍最多的hash函数个数) * 使用的三个hash函数为 * BKDR, SDBM, JSHash * * 注意, 在存储的数据量到2^30条时候, 误判率会急剧增加, 因此需要定时判断过滤器中的位为1的的数量是否超过50%, 超过则需要清空. */ class FilteRepeatedComments extends BloomFilterRedis { /** * 表示判断重复内容的过滤器 * @var string */ protected $bucket = 'rptc'; protected $hashFunction = array('BKDRHash', 'SDBMHash', 'JSHash'); }
以上是如何使用php+redis實作布隆過濾器的詳細內容。更多資訊請關注PHP中文網其他相關文章!