C#布隆过滤器的实现

本文主要是介绍C#布隆过滤器的实现，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
原理

见：https://www.cnblogs.com/mushroom/p/4556801.html
布隆过滤器作用

解决缓存穿透问题
过滤重复数据
在C#中的实现方式之一（来自外网）

 /// <summary>
    /// 布隆过滤器
    /// </summary>
    /// <typeparam name="T">数据类型</typeparam>
    public class Filter<T>
    {
        /// <summary>
        /// 一种可用于散列输入的函数。 
        /// </summary>
        /// <param name="input">要计算Hash的值</param>
        /// <returns>生成的Hash值</returns>
        public delegate int HashFunction(T input);

        /// <summary>
        /// 根据所需的容量和错误率以及Hash函数的最佳数量，使用底层数据结构的最佳大小，创建一个误判率为 1/capacity的布隆过滤器。  
        /// 如果您的类型T是string或int，则将为您提供内置的Hash函数。否则将引发异常。如果您没有使用这些类型，请使用支持自定义Hash函数的重载。
        /// </summary>
        /// <param name="capacity">要添加到过滤器中的项目的预计数量。可以添加超过此数量的项目，但误判率将超过预期。</param>
        public Filter(int capacity) : this(capacity, null) { }

        /// <summary>
        /// 根据所需的容量和错误率以及Hash函数的最佳数量，使用底层数据结构的最佳大小，创建一个误判率为 1/capacity的布隆过滤器。  
        /// 如果您的类型T是string或int，则将为您提供内置的Hash函数。否则将引发异常。如果您没有使用这些类型，请使用支持自定义Hash函数的重载。
        /// </summary>
        /// <param name="capacity">要添加到过滤器中的项目的预计数量。可以添加超过此数量的项目，但误判率将超过预期。</param>
        /// <param name="errorRate">可接受的误判率(例如, 0.01F = 1%)</param>
        public Filter(int capacity, int errorRate) : this(capacity, errorRate, null) { }

        /// <summary>
        /// 根据所需的容量和错误率以及Hash函数的最佳数量，使用底层数据结构的最佳大小，创建一个误判率为 1/capacity的布隆过滤器。  
        /// 如果您的类型T是string或int，则将为您提供二级Hash函数。否则将引发异常。如果您没有使用这些类型，请使用支持自定义Hash函数的重载。
        /// </summary>
        /// <param name="capacity">要添加到过滤器中的项目的预计数量。可以添加超过此数量的项目，但误判率将超过预期。</param>
        /// <param name="hashFunction">对输入值进行哈希运算的函数。请勿使用GetHashCode()。如果此参数为null，且T为string或int，则将为您提供内置的Hash函数。</param>
        public Filter(int capacity, HashFunction hashFunction) : this(capacity, BestErrorRate(capacity), hashFunction) { }

        /// <summary>
        /// 根据所需的容量和错误率以及Hash函数的最佳数量，使用底层数据结构的最佳大小，创建一个误判率为 1/capacity的布隆过滤器。  
        /// 如果您的类型T是string或int，则将为您提供二级Hash函数。否则将引发异常。如果您没有使用这些类型，请使用支持自定义Hash函数的重载。
        /// </summary>
        /// <param name="capacity">要添加到过滤器中的项目的预计数量。可以添加超过此数量的项目，但误判率将超过预期。</param>
        /// <param name="hashFunction">对输入值进行哈希运算的函数。请勿使用GetHashCode()。如果此参数为null，且T为string或int，则将为您提供内置的Hash函数。</param>
        /// <param name="errorRate">可接受的误判率 (例如： 0.01F = 1%)</param>
        public Filter(int capacity, float errorRate, HashFunction hashFunction) : this(capacity, errorRate, hashFunction, BestM(capacity, errorRate), BestK(capacity, errorRate)) { }

        /// <summary>
        /// 创建一个新的布隆过滤器实例
        /// </summary>
        /// <param name="capacity">要添加到过滤器中的项目的预计数量。可以添加超过此数量的项目，但误判率将超过预期。</param>
        /// <param name="errorRate">可接受的误判率 (例如： 0.01F = 1%)</param>
        /// <param name="hashFunction">对输入值进行哈希运算的函数。请勿使用GetHashCode()。如果此参数为null，且T为string或int，则将为您提供内置的Hash函数。</param>
        /// <param name="m">BitArray的容量</param>
        /// <param name="k">使用的Hash函数数量</param>
        public Filter(int capacity, float errorRate, HashFunction hashFunction, int m, int k)
        {
            // 验证参数是否在范围内
            if (capacity < 1)
                throw new ArgumentOutOfRangeException(nameof(capacity), capacity, $@"{nameof(capacity)} 必须大于0");
            if (errorRate >= 1 || errorRate <= 0)
                throw new ArgumentOutOfRangeException(nameof(errorRate), errorRate,
                    $@"{nameof(errorRate)} 必须介于0和1之间");
            if (m < 1) // 说明 BestM 函数溢出了
                throw new ArgumentOutOfRangeException(
                    $"提供的{nameof(capacity)}和{nameof(errorRate)}导致了BitArray的长度超过了[{int.MaxValue}]。 请减少其中一个值。");

            // 设置次级Hash函数
            if (hashFunction == null)
            {
                if (typeof(T) == typeof(String))
                {
                    _getHashSecondary = HashString;
                }
                else if (typeof(T) == typeof(int))
                {
                    _getHashSecondary = HashInt32;
                }
                else
                {
                    throw new ArgumentNullException(nameof(HashFunction), @"当T不是字符串或int时，请为您的类型T提供散列函数。");
                }
            }
            else
                _getHashSecondary = hashFunction;

            _hashFunctionCount = k;
            _hashBits = new BitArray(m);
        }

        /// <summary>
        /// 添加新的项到过滤器。该项无法被移除。
        /// </summary>
        /// <param name="item"></param>
        public void Add(T item)
        {
            // 开始翻转项目的每个散列的位 
            int primaryHash = item.GetHashCode();
            int secondaryHash = _getHashSecondary(item);
            for (int i = 0; i < _hashFunctionCount; i++)
            {
                int hash = ComputeHash(primaryHash, secondaryHash, i);
                _hashBits[hash] = true;
            }
        }

        /// <summary>
        ///  检查给定概率的筛选器中项目是否存在。 
        /// </summary>
        /// <param name="item"></param>
        /// <returns></returns>
        public bool Contains(T item)
        {
            int primaryHash = item.GetHashCode();
            int secondaryHash = _getHashSecondary(item);
            for (int i = 0; i < _hashFunctionCount; i++)
            {
                int hash = ComputeHash(primaryHash, secondaryHash, i);
                if (_hashBits[hash] == false)
                    return false;
            }
            return true;
        }

        /// <summary>
        /// 过滤器中false位与true位的比率。例如，容量为10的过滤器中只有1位true，那么意味着真实度为0.1。
        /// </summary>
        public double Truthiness => (double)TrueBits() / _hashBits.Count;

        private int TrueBits()
        {
            int output = 0;
            foreach (bool bit in _hashBits)
            {
                if (bit == true)
                    output++;
            }
            return output;
        }

        /// <summary>
        /// 执行 Dillinger & Manolio 双散列（使用Dillinger 、 Manolio两位的研究结果）
        /// </summary>
        /// <param name="primaryHash">主Hash值</param>
        /// <param name="secondaryHash">次级Hash值</param>
        /// <param name="i">Hash函数个数索引</param>
        /// <returns></returns>
        private int ComputeHash(int primaryHash, int secondaryHash, int i)
        {
            int resultingHash = (primaryHash + (i * secondaryHash)) % _hashBits.Count;
            return Math.Abs((int)resultingHash);
        }

        private readonly int _hashFunctionCount;
        private readonly BitArray _hashBits;
        private readonly HashFunction _getHashSecondary;

        /// <summary>
        /// 计算最佳K值（代表使用的Hash函数数量）
        /// </summary>
        /// <param name="capacity">预计添加到过滤器中的项目数量</param>
        /// <param name="errorRate">错误率</param>
        /// <returns></returns>
        private static int BestK(int capacity, float errorRate)
        {
            return (int)Math.Round(Math.Log(2.0) * BestM(capacity, errorRate) / capacity);
        }

        /// <summary>
        /// 计算最佳M值（BitArray容量）
        /// </summary> 
        /// <param name="capacity">预计添加到过滤器中的项目数量</param>
        /// <param name="errorRate">错误率</param>
        /// <returns></returns>
        private static int BestM(int capacity, float errorRate)
        {
            return (int)Math.Ceiling(capacity * Math.Log(errorRate, (1.0 / Math.Pow(2, Math.Log(2.0)))));
        }

        /// <summary>
        /// 最佳误判率
        /// </summary>
        /// <param name="capacity"></param>
        /// <returns></returns>
        private static float BestErrorRate(int capacity)
        {
            float c = (float)(1.0 / capacity);
            if (c != 0)
                return c;
            else
                return (float)Math.Pow(0.6185, int.MaxValue / capacity); // 参考：http://www.cs.princeton.edu/courses/archive/spring02/cs493/lec7.pdf
        }

        /// <summary> 
        /// 使用Thomas Wang的方法v3.1对32位带符号int进行散列 (http://www.concentric.net/~Ttwang/tech/inthash.htm).
        /// 运行时建议11个周期
        /// </summary>
        /// <param name="input">将被散列的整数</param>
        /// <returns>散列结果</returns>
        private static int HashInt32(T input)
        {
            uint? x = input as uint?;
            unchecked
            {
                x = ~x + (x << 15); // x = (x << 15) - x- 1, as (~x) + y 相当于 y - x - 1 在二进制中的补码表示
                x = x ^ (x >> 12);
                x = x + (x << 2);
                x = x ^ (x >> 4);
                x = x * 2057; // x = (x + (x << 3)) + (x<< 11);
                x = x ^ (x >> 16);
                return (int)x;
            }
        }

        /// <summary>
        ///  使用来自Dobbs博士的Bob Jenkin's "One At A Time" 方法散列一个字符串成 (http://burtleburtle.net/bob/hash/doobs.html).
        /// （https://en.wikipedia.org/wiki/Jenkins_hash_function）
        ///  运行时建议为9x+9，其中x = input.Length。 
        /// </summary>
        /// <param name="input">要散列的字符串</param>
        /// <returns>散列结果</returns>
        private static int HashString(T input)
        {
            string s = input as string;
            int hash = 0;

            if (s != null)
            {
                foreach (var t in s)
                {
                    hash += t;
                    hash += (hash << 10);
                    hash ^= (hash >> 6);
                }
            }

            hash += (hash << 3);
            hash ^= (hash >> 11);
            hash += (hash << 15);
            return hash;
        }
    }
这篇关于C#布隆过滤器的实现的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
Net Core教程

C#布隆过滤器的实现

原理

布隆过滤器作用

在C#中的实现方式之一（来自外网）

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯
