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實現的布隆過濾器
 */
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();
 }

 /**
 * 查詢是否存在, 存在的一定會存在, 不存在有一定幾率會誤判
 */
 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');
}