BloomFilter.h

Go to the documentation of this file.

// Honeycomb, Copyright (C) 2015 NewGamePlus Inc.  Distributed under the Boost Software License v1.0.
#pragma once

#include "Honey/Misc/BitSet.h"
#include "Honey/String/Id.h"
#include "Honey/Math/Alge/Alge.h"

namespace honey
{

namespace bloom_filter
{
    namespace priv
    {
        extern const szt seedCount;
        extern const szt seeds[];
    }
    template<class T>
    struct hash
    {
        szt operator()(const T& val, szt hashIndex) const       { return honey::hash::fast(ByteBufConst(reinterpret_cast<const byte*>(&val), sizeof(T)), priv::seeds[hashIndex]); }
    };

    inline tuple<szt,szt> calcParams(szt elemCount, Double errorProb)
    {
        // Optimal hash count (k) formula that minimizes error (p):
        // m = -n*ln(p) / ln(2)^2
        szt bitCount = Alge_d::ceil(-Double(elemCount) * Alge_d::log(errorProb) / Alge_d::sqr(Alge_d::log(2)));
        // k = ln(2) * m / n
        szt hashCount = Alge_d::ceil(Alge_d::log(2) * bitCount / elemCount);
        return make_tuple(bitCount, hashCount);
    }
    
    template<class T, class Alloc = std::allocator<szt>>
    struct Key
    {
        Key() {}
        Key(szt elemCount, Double errorProb = 0.01, const Alloc& a = Alloc()) :
            hashes(get<1>(calcParams(elemCount, errorProb)), 0, a) {}

        bool operator==(const Key& rhs) const                   { return hashes == rhs.hashes; }
        
        void hash(const T& obj)                                 { for (szt i = 0; i < hashes.size(); ++i) hashes[i] = hasher(obj,i); }

        vector<szt,Alloc> hashes;
        bloom_filter::hash<T> hasher;
    };

    template<class T, class Alloc>
    struct hash<Key<T,Alloc>>
    {
        szt operator()(const Key<T,Alloc>& val, szt hashIndex) const
        { assert(hashIndex < val.hashes.size(), "Key does not have enough hashes for bloom filter"); return val.hashes[hashIndex]; }
    };
}


template<class T, class Block = uint64, class Alloc = std::allocator<Block>>
class BloomFilter
{
public:
    typedef BitSet_<Block, Alloc> BitSet;

    BloomFilter(szt elemCount, Double errorProb = 0.01, const Alloc& a = Alloc()) :
        _errorProb(errorProb),
        _bits(0, false, a)
    {
        szt bitCount;
        tie(bitCount, _hashCount) = bloom_filter::calcParams(elemCount, errorProb);
        assert(_hashCount <= bloom_filter::priv::seedCount, "Not enough seeds, either try a higher error prob or add more seeds");
        // Round up to nearest power of two so that hash can be converted to index without a modulo
        _bits.resize(BitOp::pow2Ceil(bitCount));
        _bitIndexMask = _bits.size()-1;
    }

    void insert(const T& obj)
    {
        for (szt i = 0; i < _hashCount; ++i)
            _bits.set(bitIndex(_hasher(obj, i)));
    }

    bool contains(const T& obj) const
    {
        for (szt i = 0; i < _hashCount; ++i)
            if (!_bits.test(bitIndex(_hasher(obj, i)))) return false;
        return true;
    }

    void clear()                                { _bits.reset(); }

    Double errorProb() const                    { return _errorProb; }
    const BitSet& bits() const                  { return _bits; }

private:
    szt bitIndex(szt hash) const                { return hash & _bitIndexMask; }

    Double _errorProb;
    BitSet _bits;
    szt _bitIndexMask;
    szt _hashCount;
    bloom_filter::hash<T> _hasher;
};

}

namespace std
{
    template<class T, class Alloc>
    struct hash<honey::bloom_filter::Key<T,Alloc>>
    {
        size_t operator()(const honey::bloom_filter::Key<T,Alloc>& val) const
        {
            using namespace honey;
            assert(val.hashes.size());
            return val.hashes[0];
        }
    };
}