员工上网行为管控中的布隆过滤器C++语言算法

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
// 引入工业级哈希函数库（实际项目需自行配置）
#include "MurmurHash3.h"
#include "city.h"
class BloomFilter {
private:
    std::vector<bool> bit_array_;  // 核心位数组
    size_t bit_size_;              // 位数组长度
    size_t hash_count_;            // 哈希函数数量
    size_t element_count_;         // 已插入元素数量
    // 哈希函数1：MurmurHash3
    size_t hash1(const std::string& key) const {
        uint32_t hash_val;
        MurmurHash3_x86_32(key.c_str(), key.size(), 0x12345678, &hash_val);
        return hash_val % bit_size_;
    }
    // 哈希函数2：CityHash
    size_t hash2(const std::string& key) const {
        return CityHash32(key.c_str(), key.size()) % bit_size_;
    }
    // 哈希函数3：自定义混合哈希
    size_t hash3(const std::string& key) const {
        size_t hash = 0;
        for (char c : key) {
            hash = hash * 31 + c;
        }
        return hash % bit_size_;
    }
public:
    // 构造函数：根据预期元素数、误判率计算参数
    BloomFilter(size_t expected_elements, double false_positive_rate) {
        element_count_ = 0;
        // 计算位数组长度m = -n * ln(p) / (ln2)^2
        bit_size_ = static_cast<size_t>(-expected_elements * log(false_positive_rate) / (log(2) * log(2)));
        // 计算哈希函数数量k = m/n * ln2
        hash_count_ = static_cast<size_t>(bit_size_ / expected_elements * log(2));
        bit_array_.resize(bit_size_, false);
    }
    // 插入元素（如违规URL）
    void insert(const std::string& key) {
        size_t h1 = hash1(key);
        size_t h2 = hash2(key);
        size_t h3 = hash3(key);
        bit_array_[h1] = true;
        bit_array_[h2] = true;
        if (hash_count_ > 2) bit_array_[h3] = true;
        element_count_++;
    }
    // 查询元素（如员工当前访问的URL）
    bool query(const std::string& key) const {
        size_t h1 = hash1(key);
        size_t h2 = hash2(key);
        if (!bit_array_[h1] || !bit_array_[h2]) return false;
        if (hash_count_ > 2) {
            size_t h3 = hash3(key);
            if (!bit_array_[h3]) return false;
        }
        return true;
    }
    // 计算当前误判率
    double getFalsePositiveRate() const {
        if (element_count_ == 0) return 0.0;
        double p = pow(1 - exp(-hash_count_ * element_count_ / (double)bit_size_), hash_count_);
        return p;
    }
};
// 测试例程：模拟员工上网行为URL拦截
int main() {
    // 初始化：预期10万条违规URL，误判率0.01%
    BloomFilter filter(100000, 0.0001);
    // 1. 插入违规URL（模拟企业更新违规库）
    std::vector<std::string> illegal_urls = {
        "https://example-illegal-1.com",
        "https://example-illegal-2.com",
        // 实际场景中可从配置文件批量读取
    };
    for (const auto& url : illegal_urls) {
        filter.insert(url);
    }
    // 2. 模拟员工上网行为：查询URL是否违规
    std::vector<std::string> employee_urls = {
        "https://example-illegal-1.com",  // 违规URL
        "https://work.weixin.qq.com",     // 合法URL
        "https://example-illegal-3.com"  // 新增违规URL（未插入）
    };
    for (const auto& url : employee_urls) {
        if (filter.query(url)) {
            std::cout << "员工访问URL：" << url << " - 疑似违规，已拦截\\n";
        } else {
            std::cout << "员工访问URL：" << url << " - 合规，允许访问\\n";
        }
    }
    // 输出当前误判率
    std::cout << "当前布隆过滤器误判率：" << filter.getFalsePositiveRate() << std::endl;
    return 0;
}