内网行为管理中的布隆过滤器C++语言算法

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
// MurmurHash3哈希函数实现（32位版本）
uint32_t MurmurHash3(const std::string& key, uint32_t seed) {
    const uint8_t* data = reinterpret_cast<const uint8_t*>(key.c_str());
    size_t len = key.size();
    const uint32_t c1 = 0xcc9e2d51;
    const uint32_t c2 = 0x1b873593;
    const uint32_t r1 = 15;
    const uint32_t r2 = 13;
    const uint32_t m = 5;
    const uint32_t n = 0xe6546b64;
    uint32_t hash = seed;
    const size_t block_size = len & ~0x3;
    const uint32_t* blocks = reinterpret_cast<const uint32_t*>(data);
    // 处理4字节块
    for (size_t i = 0; i < block_size / 4; ++i) {
        uint32_t k = blocks[i];
        k *= c1;
        k = (k << r1) | (k >> (32 - r1));
        k *= c2;
        hash ^= k;
        hash = ((hash << r2) | (hash >> (32 - r2))) * m + n;
    }
    // 处理剩余字节
    const uint8_t* tail = data + block_size;
    uint32_t k1 = 0;
    switch (len & 0x3) {
        case 3: k1 ^= tail[2] << 16;
        case 2: k1 ^= tail[1] << 8;
        case 1: k1 ^= tail[0];
                k1 *= c1;
                k1 = (k1 << r1) | (k1 >> (32 - r1));
                k1 *= c2;
                hash ^= k1;
    }
    hash ^= len;
    hash ^= (hash >> 16);
    hash *= 0x85ebca6b;
    hash ^= (hash >> 13);
    hash *= 0xc2b2ae35;
    hash ^= (hash >> 16);
    return hash;
}
class BloomFilter {
private:
    std::vector<bool> bitset;  // 二进制位数组
    size_t bit_size;            // 位数组长度
    size_t hash_count;          // 哈希函数个数
    std::vector<uint32_t> seeds;// 哈希函数种子
    // 计算元素在位数组中的映射位置
    std::vector<size_t> getPositions(const std::string& key) const {
        std::vector<size_t> positions(hash_count);
        for (size_t i = 0; i < hash_count; ++i) {
            uint32_t hash_val = MurmurHash3(key, seeds[i]);
            positions[i] = hash_val % bit_size;
        }
        return positions;
    }
public:
    // 构造函数：根据预期元素数量和误判率初始化
    BloomFilter(size_t expected_n, double false_positive_rate) {
        // 计算最优位数组长度
        bit_size = static_cast<size_t>(-expected_n * log(false_positive_rate) / (log(2) * log(2)));
        // 计算最优哈希函数个数
        hash_count = static_cast<size_t>(bit_size * log(2) / expected_n);
        bitset.resize(bit_size, false);
        // 初始化哈希函数种子（避免哈希函数相关性）
        seeds = {11, 23, 37, 41, 53, 67, 79, 83};
        // 若最优哈希数超过种子数，扩展种子
        while (seeds.size() < hash_count) {
            seeds.push_back(seeds.back() + 29);
        }
    }
    // 插入元素
    void insert(const std::string& key) {
        auto positions = getPositions(key);
        for (size_t pos : positions) {
            bitset[pos] = true;
        }
    }
    // 查询元素：true表示可能存在，false表示一定不存在
    bool contains(const std::string& key) const {
        auto positions = getPositions(key);
        for (size_t pos : positions) {
            if (!bitset[pos]) {
                return false;
            }
        }
        return true;
    }
};
// 内网行为管理场景测试示例
int main() {
    // 初始化布隆过滤器：预期存储10000个设备MAC，误判率0.01
    BloomFilter bf(10000, 0.01);
    // 插入黑名单设备MAC
    std::vector<std::string> blacklist_mac = {
        "00:1A:2B:3C:4D:5E", "00:1A:2B:3C:4D:5F", "00:1A:2B:3C:4D:60"
    };
    for (const auto& mac : blacklist_mac) {
        bf.insert(mac);
    }
    // 模拟内网设备接入检测
    std::string test_mac1 = "00:1A:2B:3C:4D:5E"; // 黑名单设备
    std::string test_mac2 = "00:1A:2B:3C:4D:61"; // 合法设备
    if (bf.contains(test_mac1)) {
        std::cout << "设备" << test_mac1 << "可能在黑名单中，启动精确校验流程" << std::endl;
    } else {
        std::cout << "设备" << test_mac1 << "不在黑名单，允许接入" << std::endl;
    }
    if (bf.contains(test_mac2)) {
        std::cout << "设备" << test_mac2 << "可能在黑名单中，启动精确校验流程" << std::endl;
    } else {
        std::cout << "设备" << test_mac2 << "不在黑名单，允许接入" << std::endl;
    }
    return 0;
}