布隆过滤器的原理、实现与应用场景

#include <functional>
#include <memory>
#include <random>
#include <string>
#include <vector>

using namespace cutl;

class BloomFilter
{
private:
    size_t size_;
    bitmap bitmap_;
    size_t hash_size_;

public:
    BloomFilter(size_t size, size_t hash_size)
      : size_(size)
      , hash_size_(hash_size)
      , bitmap_(size)
    {
    }

    // 双重哈希函数，生成k个哈希值
    std::pair<size_t, size_t> hash(const std::string& str) const
    {
        std::hash<std::string> hasher1;
        std::hash<std::string> hasher2;

        size_t h1 = hasher1(str);
        size_t h2 = hasher2(str + "salt"); // 加盐获得不同的哈希值

        return { h1, h2 };
    }

    /**
     * 添加元素
     */
    void add(const std::string& value)
    {
        auto pair = hash(value);
        auto h1 = pair.first;
        auto h2 = pair.second;
        // 确保h2是奇数，提高分布性
        if (h2 & 0x1 == 0) // 等同于 h2 % 2 == 0
        {
            h2 += 1;
        }

        for (size_t i = 0; i < hash_size_; ++i)
        {
            size_t index = (h1 + i * h2) % size_;
            bitmap_.set(index);
        }
    }

    /**
     * 判断元素是否存在（可能有误判）
     */
    bool contains(const std::string& value) const
    {
        auto pair = hash(value);
        auto h1 = pair.first;
        auto h2 = pair.second;
        if (h2 & 0x1 == 0) // 等同于 h2 % 2 == 0
        {
            h2 += 1;
        }

        for (size_t i = 0; i < hash_size_; ++i)
        {
            size_t index = (h1 + i * h2) % size_;
            if (!bitmap_.get(index))
            {
                return false;
            }
        }
        return true;
    }

    /**
     * 清空布隆过滤器
     */
    void clear() { bitmap_.reset(); }

    /**
     * 获取位图中设置位的数量
     */
    size_t getSetBitCount() { return bitmap_.count(); }
};

void TestBsetUsage()
{
    PrintSubTitle("TestBsetUsage");

    // 创建布隆过滤器：位数组大小1000，使用3个哈希函数
    BloomFilter bloom(1000, 3);

    // 添加一些元素
    bloom.add("apple");
    bloom.add("banana");
    bloom.add("orange");

    // 测试存在性
    std::cout << "Contains 'apple': " << bloom.contains("apple") << std::endl;   // 应该为true
    std::cout << "Contains 'banana': " << bloom.contains("banana") << std::endl; // 应该为true
    std::cout << "Contains 'grape': " << bloom.contains("grape")
              << std::endl; // 可能为false，或小概率为true（误判）
}