bloom_filter.hpp

浏览该文件的文档.

#ifndef NEFORCE_CORE_CONTAINER_BLOOM_FILTER_HPP__
#define NEFORCE_CORE_CONTAINER_BLOOM_FILTER_HPP__

 
#include "NeForce/core/container/bitmap.hpp"
#include "NeForce/core/container/vector.hpp"
#include "NeForce/core/memory/bit.hpp"
#include "NeForce/core/numeric/math.hpp"
NEFORCE_BEGIN_NAMESPACE__


template <typename T, typename Hash = hash<T>>
class bloom_filter {
private:
    size_t m_;    
    size_t k_;    
    bitmap bits_; 
    Hash hasher_; 

    static size_t compute_m(const size_t n, const double p) noexcept {
        const double ln2 = logarithm_e(2.);
        const double m = -static_cast<double>(n) * logarithm_e(p) / (ln2 * ln2);
        return static_cast<size_t>(ceil(m));
    }

    static size_t compute_k(const size_t n, const size_t m) noexcept {
        const double k = (static_cast<double>(m) / n) * logarithm_e(2.);
        return static_cast<size_t>(max(static_cast<decimal_t>(1), round(k)));
    }

    pair<size_t, size_t> hash_values(const T& key) const noexcept {
        size_t h1 = hasher_(key);
        size_t h2 = rotate_l(h1, 17);
        if (h2 == 0) {
            h2 = 1;
        }
        return {h1, h2};
    }

    size_t nth_hash(const size_t i, const size_t h1, const size_t h2) const noexcept { return (h1 + i * h2) % m_; }
 
public:
    bloom_filter(const bloom_filter&) noexcept = default;
    bloom_filter(bloom_filter&&) noexcept = default;
    bloom_filter& operator=(const bloom_filter&) = default;
    bloom_filter& operator=(bloom_filter&&) = default;

    ~bloom_filter() = default;

    bloom_filter(const size_t expected_insertions, const double false_positive_prob) :
    m_(compute_m(expected_insertions, false_positive_prob)),
    k_(compute_k(expected_insertions, m_)),
    bits_(m_, false),
    hasher_(Hash()) {
        if (expected_insertions == 0 || false_positive_prob <= 0.0 || false_positive_prob >= 1.0) {
            NEFORCE_THROW_EXCEPTION(
                    value_exception("expected_insertions must be positive and false_positive_prob in (0,1)"));
        }
    }

    bloom_filter(const size_t m, const size_t k) :
    m_(m),
    k_(k),
    bits_(m_, false),
    hasher_(Hash()) {
        if (m == 0 || k == 0) {
            NEFORCE_THROW_EXCEPTION(value_exception("m and k must be positive"));
        }
    }

    NEFORCE_NODISCARD size_t capacity() const noexcept {
        return static_cast<size_t>(static_cast<double>(m_) * logarithm_e(2.) / k_);
    }

    NEFORCE_NODISCARD bool empty() const noexcept {
        for (size_t i = 0; i < m_; ++i) {
            if (bits_[i]) {
                return false;
            }
        }
        return true;
    }

    NEFORCE_NODISCARD size_t bit_size() const noexcept { return m_; }

    NEFORCE_NODISCARD size_t hash_count() const noexcept { return k_; }

    NEFORCE_NODISCARD size_t approximate_count() const noexcept {
        size_t bits_set = 0;
        for (size_t i = 0; i < m_; ++i) {
            if (bits_[i]) {
                ++bits_set;
            }
        }
        const double x = static_cast<double>(bits_set) / m_;
        return static_cast<size_t>(-(static_cast<double>(m_) / k_) * logarithm_e(1 - x));
    }

    NEFORCE_NODISCARD double false_positive_rate() const noexcept {
        size_t bits_set = 0;
        for (size_t i = 0; i < m_; ++i) {
            if (bits_[i]) {
                ++bits_set;
            }
        }
        const double x = static_cast<double>(bits_set) / m_;
        return power(x, k_);
    }

    NEFORCE_NODISCARD bool contains(const T& key) const noexcept {
        auto h = this->hash_values(key);
        for (size_t i = 0; i < k_; ++i) {
            const size_t index = this->nth_hash(i, h.first, h.second);
            if (!bits_[index]) {
                return false;
            }
        }
        return true;
    }

    void insert(const T& key) noexcept {
        auto h = this->hash_values(key);
        for (size_t i = 0; i < k_; ++i) {
            const size_t index = this->nth_hash(i, h.first, h.second);
            bits_[index] = true;
        }
    }

    void clear() noexcept { fill(bits_.begin(), bits_.end(), false); }

    bloom_filter& merge(const bloom_filter& other) {
        if (m_ != other.m_ || k_ != other.k_) {
            NEFORCE_THROW_EXCEPTION(value_exception("Filters must have same parameters to merge"));
        }
 
        for (size_t i = 0; i < m_; ++i) {
            if (other.bits_[i]) {
                bits_[i] = true;
            }
        }
        return *this;
    }

    bloom_filter intersect(const bloom_filter& other) const {
        if (m_ != other.m_ || k_ != other.k_) {
            NEFORCE_THROW_EXCEPTION(value_exception("Filters must have same parameters for intersection"));
        }
 
        bloom_filter result(m_, k_);
        for (size_t i = 0; i < m_; ++i) {
            result.bits_[i] = bits_[i] && other.bits_[i];
        }
        return result;
    }

    bloom_filter unite(const bloom_filter& other) const {
        bloom_filter result(*this);
        return result.merge(other);
    }

    byte_vector to_bytes() const {
        byte_vector bytes((m_ + 7) / 8);
        for (size_t i = 0; i < m_; ++i) {
            if (bits_[i]) {
                bytes[i / 8] |= (1 << (i % 8));
            }
        }
        return bytes;
    }

    void from_bytes(const byte_vector& bytes) {
        if (bytes.size() * 8 < m_) {
            NEFORCE_THROW_EXCEPTION(value_exception("Insufficient byte data"));
        }
        for (size_t i = 0; i < m_; ++i) {
            bits_[i] = (bytes[i / 8] >> (i % 8)) & 1;
        }
    }
};
 // BloomFilter
 
NEFORCE_END_NAMESPACE__
#endif // NEFORCE_CORE_CONTAINER_BLOOM_FILTER_HPP__