Bloom Filter

bloom_filter.cpp

#include <iostream>
#include <vector>
#include <string>
#include <type_traits>

using hash_t = std::size_t;

inline auto HashBytes(const char *bytes, size_t length, hash_t seed = 0) -> hash_t {
    hash_t hash = length + seed;
    for (size_t i = 0; i < length; ++i) {
        hash = ((hash << 5) ^ (hash >> 27)) ^ static_cast<int8_t>(bytes[i]);
    }
    return hash;
}

template <typename T>
struct HashAdapter {
    void operator()(const T& value, hash_t& h1, hash_t& h2) const {
        static_assert(std::is_trivially_copyable<T>::value, "Type must be trivially copyable to use default byte hashing.");

        const char* bytes = reinterpret_cast<const char*>(&value);
        size_t length = sizeof(T);

        h1 = HashBytes(bytes, length, 0);
        h2 = HashBytes(bytes, length, 0x9e3779b9);
    }
};

template <>
struct HashAdapter<std::string> {
    void operator()(const std::string& value, hash_t& h1, hash_t& h2) const {
        h1 = HashBytes(value.data(), value.size(), 0);
        h2 = HashBytes(value.data(), value.size(), 0x9e3779b9);
    }
};

template <typename T>
size_t double_hash(const T &value, size_t i, size_t m) {
    hash_t h1, h2;
    HashAdapter<T>{}(value, h1, h2);
    return (h1 + i * h2) % m;
}

template <typename T>
class BloomFilter {
public:
    BloomFilter(const int filter_size, const int hash_count)
        : filter_size_(filter_size), hash_count_(hash_count), inserted_count(0) {
        bits_.assign(filter_size_, false);
    }

    void Insert(const T &value) {
        for (int i = 0; i < hash_count_; i++) {
            const auto idx = double_hash<T>(value, i, filter_size_);
            bits_[idx] = true;
        }
        inserted_count++;
    }

    auto Lookup(const T &value) -> bool {
        for (int i = 0; i < hash_count_; i++) {
            const auto idx = double_hash<T>(value, i, filter_size_);
            if (!bits_[idx]) {
                return false;
            }
        }
        return true;
    }

    auto GetCapacity() const -> int {
        return static_cast<int>(filter_size_ * 0.693 / hash_count_);
    }

    auto GetFilterSize() const -> int {
        return filter_size_;
    }

    auto GetHashCount() const -> int {
        return hash_count_;
    }

    auto GetInsertedCount() const -> int {
        return inserted_count;
    }

private:
    int filter_size_;
    int hash_count_;
    int inserted_count;
    std::vector<bool> bits_;
};

template <typename T>
class ScalableBloomFilter {
public:
    ScalableBloomFilter(const double capacity_threshold = 0.8) : capacity_threshold_(capacity_threshold) {
        filters_.emplace_back(base_filter_size_, base_hash_count_);
    }

    void Insert(const T &value) {
        const int capacity = filters_.back().GetCapacity();
        const int items_in_current_filter_ = filters_.back().GetInsertedCount();
        const int current_filter_size_ = filters_.back().GetFilterSize();
        const int current_hash_count_ = filters_.back().GetHashCount();

        if (items_in_current_filter_ >= capacity * capacity_threshold_) {
            filters_.emplace_back(current_filter_size_ * 2, current_hash_count_ + 1);
        }

        filters_.back().Insert(value);
    }

    auto Lookup(const T &value) -> bool {
        for (auto &filter: filters_) {
            if (filter.Lookup(value)) {
                return true;
            }
        }
        return false;
    }

    auto GetFilterCount() const -> int {
        return filters_.size();
    }

private:
    std::vector<BloomFilter<T>> filters_;
    int base_filter_size_{1024};
    int base_hash_count_{8};
    double capacity_threshold_;
};

std::vector<std::string> generate(const int count, const std::string &prefix = "item") {
    std::vector<std::string> res;
    res.reserve(count);
    for (int i = 0; i < count; ++i) {
        res.push_back(prefix + std::to_string(i));
    }
    return res;
}

int main() {
    ScalableBloomFilter<std::string>sbf;

    const int N = 2000;
    auto inserted = generate(N, "key");

    for (const auto &s: inserted) {
        sbf.Insert(s);
    }

    int missed = 0;
    for (const auto &s: inserted) {
        if (!sbf.Lookup(s)) {
            ++missed;
        }
    }
    std::cout << "插入 " << N << " 个，假阴性: " << missed << std::endl;

    const int test_cnt = 5000;
    auto not_inserted = generate(test_cnt, "other");
    int false_pos = 0;
    for (const auto &s: not_inserted) {
        if (sbf.Lookup(s)) {
            ++false_pos;
        }
    }

    double fp_rate = 100.0 * false_pos / test_cnt;
    std::cout << "未插入字符串假阳性: " << false_pos << " / " << test_cnt
            << " (" << fp_rate << "%)" << std::endl;
    std::cout << "过滤器数量: " << sbf.GetFilterCount() << std::endl;

    return 0;
}