监控员工电脑上网场景下的布隆过滤器C#语言算法

using System;
using System.Security.Cryptography;
namespace EmployeeNetworkMonitoring
{
    /// <summary>
    /// 适配监控员工电脑上网场景的布隆过滤器
    /// </summary>
    public class BloomFilter
    {
        // 位数组，用于存储元素哈希标记
        private readonly BitArray _bitArray;
        // 哈希函数个数
        private readonly int _hashFunctionCount;
        // 预期存储元素总量
        private readonly int _expectedItemCount;
        // 位数组长度
        private readonly int _bitArrayLength;
        /// <summary>
        /// 构造函数，初始化布隆过滤器参数
        /// </summary>
        /// <param name="expectedItemCount">预期存储的网址总量</param>
        /// <param name="falsePositiveRate">可接受的误判率</param>
        public BloomFilter(int expectedItemCount, double falsePositiveRate)
        {
            if (expectedItemCount <= 0)
                throw new ArgumentOutOfRangeException(nameof(expectedItemCount), "预期元素数量必须大于0");
            if (falsePositiveRate <= 0 || falsePositiveRate > 1)
                throw new ArgumentOutOfRangeException(nameof(falsePositiveRate), "误判率必须在(0,1]区间内");
            _expectedItemCount = expectedItemCount;
            // 计算最优位数组长度
            _bitArrayLength = CalculateOptimalBitArrayLength(expectedItemCount, falsePositiveRate);
            // 计算最优哈希函数个数
            _hashFunctionCount = CalculateOptimalHashFunctionCount(_bitArrayLength, expectedItemCount);
            _bitArray = new BitArray(_bitArrayLength);
        }
        /// <summary>
        /// 计算最优位数组长度
        /// </summary>
        private int CalculateOptimalBitArrayLength(int n, double p)
        {
            return (int)Math.Ceiling((n * Math.Log(p)) / Math.Log(1 / Math.Pow(2, Math.Log(2))));
        }
        /// <summary>
        /// 计算最优哈希函数个数
        /// </summary>
        private int CalculateOptimalHashFunctionCount(int m, int n)
        {
            return (int)Math.Round((m / (double)n) * Math.Log(2));
        }
        /// <summary>
        /// 插入网址到布隆过滤器
        /// </summary>
        /// <param name="url">员工访问的网址</param>
        public void Add(string url)
        {
            if (string.IsNullOrEmpty(url))
                throw new ArgumentNullException(nameof(url));
            var hashes = ComputeHashes(url);
            foreach (var hash in hashes)
            {
                _bitArray.Set(hash, true);
            }
        }
        /// <summary>
        /// 判断网址是否可能已存在（监控场景中用于去重或黑名单校验）
        /// </summary>
        /// <param name="url">员工访问的网址</param>
        /// <returns>true：可能存在；false：一定不存在</returns>
        public bool Contains(string url)
        {
            if (string.IsNullOrEmpty(url))
                throw new ArgumentNullException(nameof(url));
            var hashes = ComputeHashes(url);
            foreach (var hash in hashes)
            {
                if (!_bitArray.Get(hash))
                    return false;
            }
            return true;
        }
        /// <summary>
        /// 计算网址的多个哈希值
        /// </summary>
        private int[] ComputeHashes(string url)
        {
            var hashes = new int[_hashFunctionCount];
            using var murmurHash = MurMurHash3.Create128();
            var urlBytes = System.Text.Encoding.UTF8.GetBytes(url);
            var hashBytes = murmurHash.ComputeHash(urlBytes);
            // 基于128位哈希值生成多个32位哈希下标
            for (int i = 0; i < _hashFunctionCount; i++)
            {
                var hash32 = BitConverter.ToInt32(hashBytes, (i % 2) * 4);
                hashes[i] = Math.Abs(hash32) % _bitArrayLength;
            }
            return hashes;
        }
    }
    // 监控场景调用示例
    public class MonitoringService
    {
        public static void Main(string[] args)
        {
            // 初始化布隆过滤器：预期存储100万条网址，误判率0.01%
            var bloomFilter = new BloomFilter(1_000_000, 0.0001);
            
            // 模拟员工访问的网址列表
            var visitedUrls = new[] 
            { 
                "https://www.example.com", 
                "https://www.enterprise-internal.com",
                "https://www.untrusted-site.com" 
            };
            // 插入已访问网址到过滤器（用于去重）
            foreach (var url in visitedUrls)
            {
                bloomFilter.Add(url);
                Console.WriteLine($"已将网址[{url}]加入监控过滤器");
            }
            // 模拟监控员工电脑上网时的网址校验
            var testUrls = new[] 
            { 
                "https://www.example.com",  // 已访问过
                "https://www.new-site.com", // 未访问过
                "https://www.untrusted-site.com" // 黑名单网址
            };
            foreach (var url in testUrls)
            {
                var exists = bloomFilter.Contains(url);
                if (exists)
                {
                    Console.WriteLine($"监控到员工访问网址[{url}]，该网址可能已被记录或在黑名单中");
                }
                else
                {
                    Console.WriteLine($"监控到员工访问新网址[{url}]，执行新增记录流程");
                    bloomFilter.Add(url);
                }
            }
        }
    }
}