内网监管软件中的布隆过滤器算法及C#实现例程

using System;
using System.Security.Cryptography;
namespace IntranetMonitoringSoftware
{
    /// <summary>
    /// 适配内网监管软件的布隆过滤器实现
    /// 用于高效过滤违规IP、敏感关键词等数据
    /// </summary>
    public class BloomFilter
    {
        // 位数组长度（单位：比特）
        private readonly int _bitLength;
        // 位数组（用ulong数组存储，节省内存）
        private readonly ulong[] _bitArray;
        // 哈希函数个数
        private readonly int _hashCount;
        /// <summary>
        /// 构造函数，初始化布隆过滤器
        /// </summary>
        /// <param name="expectedCount">预期存储的元素个数</param>
        /// <param name="falsePositiveRate">允许的误判率</param>
        public BloomFilter(int expectedCount, double falsePositiveRate)
        {
            // 计算最优位数组长度m
            _bitLength = (int)Math.Ceiling(expectedCount * Math.Log(falsePositiveRate, Math.E) / Math.Log(2));
            // 计算最优哈希函数个数k
            _hashCount = (int)Math.Round(Math.Log(2) * _bitLength / expectedCount);
            // 初始化位数组，ulong为64位，计算所需数组长度
            _bitArray = new ulong[(int)Math.Ceiling((double)_bitLength / 64)];
        }
        /// <summary>
        /// 插入元素到布隆过滤器
        /// </summary>
        /// <param name="element">待插入元素（如违规IP、敏感关键词）</param>
        public void Insert(string element)
        {
            if (string.IsNullOrEmpty(element))
                throw new ArgumentNullException(nameof(element));
            // 获取元素的多个哈希值，更新位数组
            foreach (var hash in GetHashes(element))
            {
                // 计算哈希值对应的位数组索引和比特位
                int arrayIndex = hash / 64;
                int bitIndex = hash % 64;
                // 将对应比特位设为1
                _bitArray[arrayIndex] |= 1UL << bitIndex;
            }
        }
        /// <summary>
        /// 查询元素是否可能存在于布隆过滤器中
        /// </summary>
        /// <param name="element">待查询元素</param>
        /// <returns>true：可能存在；false：一定不存在</returns>
        public bool Contains(string element)
        {
            if (string.IsNullOrEmpty(element))
                return false;
            // 检查所有哈希值对应的比特位是否均为1
            foreach (var hash in GetHashes(element))
            {
                int arrayIndex = hash / 64;
                int bitIndex = hash % 64;
                // 若任意一个比特位为0，说明元素一定不存在
                if ((_bitArray[arrayIndex] & (1UL << bitIndex)) == 0)
                    return false;
            }
            return true;
        }
        /// <summary>
        /// 生成元素的多个哈希值（基于SHA256实现）
        /// </summary>
        /// <param name="element">待哈希元素</param>
        /// <returns>哈希值数组</returns>
        private int[] GetHashes(string element)
        {
            int[] hashes = new int[_hashCount];
            using (SHA256 sha256 = SHA256.Create())
            {
                // 将元素转换为字节数组
                byte[] elementBytes = System.Text.Encoding.UTF8.GetBytes(element);
                // 计算SHA256哈希值（32字节）
                byte[] hashBytes = sha256.ComputeHash(elementBytes);
                // 从哈希字节数组中提取多个int类型的哈希值
                for (int i = 0; i < _hashCount; i++)
                {
                    // 每4个字节组成一个int哈希值，循环提取
                    hashes[i] = BitConverter.ToInt32(hashBytes, (i % 8) * 4);
                    // 确保哈希值为非负数，避免索引异常
                    if (hashes[i] < 0)
                        hashes[i] = -hashes[i];
                    // 取模，确保哈希值在位数组范围内
                    hashes[i] %= _bitLength;
                }
            }
            return hashes;
        }
    }
    /// <summary>
    /// 测试类，模拟内网监管软件中的布隆过滤器使用场景
    /// </summary>
    public class BloomFilterTest
    {
        public static void Main(string[] args)
        {
            // 模拟内网监管软件的违规IP名单（预期存储1000条，误判率0.01）
            BloomFilter forbiddenIpFilter = new BloomFilter(1000, 0.01);
            // 插入1000条模拟违规IP
            for (int i = 0; i < 1000; i++)
            {
                string forbiddenIp = $"192.168.1.{i}";
                forbiddenIpFilter.Insert(forbiddenIp);
            }
            // 测试查询（存在的IP）
            string existIp = "192.168.1.100";
            Console.WriteLine($"IP {existIp} 是否为违规IP：{forbiddenIpFilter.Contains(existIp)}"); // 输出：True
            // 测试查询（不存在的IP）
            string nonExistIp = "192.168.1.1001";
            Console.WriteLine($"IP {nonExistIp} 是否为违规IP：{forbiddenIpFilter.Contains(nonExistIp)}"); // 输出：False
            // 模拟敏感关键词过滤场景
            BloomFilter sensitiveKeywordFilter = new BloomFilter(500, 0.005);
            string[] sensitiveKeywords = { "涉密", "违规", "外泄", "机密", "未授权" };
            foreach (var keyword in sensitiveKeywords)
            {
                sensitiveKeywordFilter.Insert(keyword);
            }
            // 测试敏感关键词查询
            string testContent = "该文件包含涉密信息";
            bool hasSensitive = sensitiveKeywordFilter.Contains("涉密");
            Console.WriteLine($"内容是否包含敏感关键词：{hasSensitive}"); // 输出：True
        }
    }
}