A Bloom Filter Written in PHP

bloomfilter.php

<?php

/**
 * This class relies on the GMP extension to be loaded in PHP
 *
 */

class Bloomfilter
{

    protected $maxElements, $probability, $space, $hashes, $filter;

    public function __construct($numElements, $probability = 0.01)
    {
        $this->maxElements = $numElements;
        $this->probability = $probability;
    }
    
    protected function calculateSpace($numElements, $probability)
    {
        return (int) ceil(($numElements * (log($probability)) / (log(2) ** 2)) * -1);
    }
    
    protected function calculateHashFunctions($numElements, $space)
    {
        return (int) ceil($this->space / $this->maxElements * log(2));
    }
    
    protected function numHashFunctionsAvailable()
    {
        $num = 0;
        foreach(hash_algos() as $algo) {
            $num += count(unpack('J*', hash($algo, 'bloom', true)));
        }
        return $num;
    }
        
    protected function hash($element)
    {
        $hashes = [];
        foreach(hash_algos() as $algo) {
            foreach(unpack('P*', hash($algo, $element, true)) as $hash) {
                $hash = gmp_init(sprintf("%u", $hash));
                $hashes[] = ($hash % $this->space);
                if (count($hashes) >= $this->hashes) {
                    break 2;
                }
            }
        }
        return $hashes;
    }
    
    protected function isInit()
    {
        if (!strlen($this->filter)) {
            throw new Exception("Filter has not been initialized!");
        }
    }
    
    public function initialize()
    {
        $this->space  = $this->calculateSpace($this->maxElements, $this->probability);
        $this->hashes = $this->calculateHashFunctions($this->maxElements, $this->space);
        if ($this->hashes > $this->numHashFunctionsAvailable()) {
            throw new Exception("Cannot initialize filter with available system hash functions!");
        }
        $this->filter = str_repeat("\0", ceil($this->space / 8));
    }
    
    public function set($element)
    {
        $this->isInit();
        if (!is_scalar($element)) {
            $element = serialize($element);
        }
        $hashes = $this->hash($element);
        foreach($hashes as $hash) {
            $offset = (int) floor($hash / 8);
            $bit    = (int) ($hash % 8);
            $this->filter[$offset] = chr(ord($this->filter[$offset]) | (2 ** $bit));
        }
    }
    
    public function check($element)
    {
        $this->isInit();
        if (!is_scalar($element)) {
            $element = serialize($element);
        }
        $hashes = $this->hash($element);
        foreach($hashes as $hash) {
            $offset = (int) floor($hash / 8);
            $bit    = (int) ($hash % 8);
            if (!(ord($this->filter[$offset]) & (2 ** $bit))) {
                return false;
            }
        }
        return true;
    }
    
    public function getFilter()
    {
        return $this->filter;
    }
    
}

example.php

<?php

try {
  $bloomfilter = new BloomFilter(100);
  $bloomfilter->initialize();
  $bloomfilter->set("Hello PHP!");
  var_dump($bloomfilter->check("Hello PHP!"));
} catch(Exception $e) {
  var_dump($e);
}