高级数据结构

优先级队列

原理

特性

应用场景

红黑树

原理

特性

应用场景

特性

java的hashmap

B+树

原理

特性

应用场景

前缀树 、 字典树

原理

特性

应用场景

跳表

原理

特性

应用场景

布隆过滤器 bloom filter

原理

构建一个大的数组向量，每个元素放入的时候计算一次hash，得到元素落入的位置。用于做元素是否存在的判别。

特性

节省空间，判别快

应用场景

web3加密货币钱包钱包dApp网站白名单过滤 实现方案：客户端判别+缓存 服务端构建+更新

缓存穿透判别

feed是否推荐过

参数

supported_domains_filter_ String representation of the domain bloom filter bit-vector

bloom_filter_array_size_ Size of the filter in terms of number of bits

number_of_hash_functions_ Number of hash funtions used for lookup in the domain filter

shift_base_  Randomization parameter used by the hashing functions

prime_bases_ Base primes used to generate hashes

误判概率计算

BF计算器

参数： k哈希次数 m数组大小 n元素数量

1. 一个bit位被置为1的概率
2. 一个bit位没有被置为1的概率
3. 一个元素k次哈希后都没有把一个bit位置为1的概率
4. n个元素都经过k次哈希后没把一个bit位置为1的概率
5. 如果一个元素存在误报，意即这个元素经过k次哈希后得到的k个索引全部都是1，概率是
6. 根据自然对数底数e的定义，可以近似表示为：

细节

我们的设计：误判率固定（0.01），数组大小随元素数量增长

ShiftBase和Primes在此处用于改变哈希函数，使得同一输入对应的输出更散列。哈希函数的目标是将输入尽可能均匀地映射到输出空间。如果所有输入都映射到同一索引，或者一些索引比其他索引更常见，那么布隆过滤器的效率就会降低，因为会增加假阳性的概率。

具体来看，这段代码中的CalculateHash方法是这样工作的：

• primeBaseIndex是shift除以Primes数组长度的余数。这样可以确保即使shift超出了Primes数组的长度，我们仍然能得到一个有效的索引。
• primeBase是Primes数组中primeBaseIndex位置的元素。Primes数组的具体内容没有给出，但根据名称可以推测它是一组质数。质数在哈希函数中常常被用作乘法因子，因为它们有一些有利的数学性质，可以帮助分散哈希值。
• 然后，对于域名中的每个字符，我们将primeBase左移shift位，然后加上primeBase和当前字符的ASCII值。这个操作可以理解为一种混合输入字符和当前哈希值的方式，同时引入了shift来增加混合的复杂性。

在GetIndexToBeSetFromDomain方法中，使用CalculateHash方法计算了给定域名的哈希值，并确保哈希值为正（通过取绝对值），然后对布隆过滤器数组的大小取模，以得到一个位于数组范围内的索引。

private const int ShiftBase = 2;
private static readonly int[] Primes = { 5381, 5393, 5821, 5869 }; // arbitrarily selected prime numbers
private BitArray ConstructBloomFilterArray()
        {
            // We don't need to validate SupportedDomains member since we guarantee that in constructor
            // Exceptions will be thrown if invalid data is read from CSV.

            // The # of supported domain is going to grow, hence I am not using any fixed size array.
            // Ref: http://en.wikipedia.org/wiki/Bloom_filter#Optimal_number_of_hash_functions
            // we will use the formulas for array size:
            // s = -(n * ln(p))/(ln(2)^2)
            // where:
            //  s - the size of the bit array
            //  n - number of input, in this case number of unique domains.
            //  p - desired false positive probability (where 0<p<1), we are keeping it to 0.01 to start with.
            // Formula for optimal number of hash functions:
            // k = (s * ln(2)) / n
            // where:
            //  k - the number of hash functions needed to get the desired false positive probability
            //  s - the size of a bit array
            //  n - number of elements to be inserted
            double ln2 = Math.Log(2);
            double ln2Sqr = ln2 * ln2;
            int arraySize = (int)-(SupportedDomains.Count * Math.Log(0.01) / ln2Sqr);
            int numberOfHashFunctions = GetNumberOfHashFunctions(arraySize, SupportedDomains.Count);

            BitArray bloomFilterArray = new BitArray(arraySize, defaultValue: false);
            foreach (string domain in SupportedDomains)
            {
                if (!string.IsNullOrEmpty(domain))
                {
                    string trimmedDomain = domain.Trim();

                    for (int i = ShiftBase; i < numberOfHashFunctions + ShiftBase; i++)
                    {
                        int index = GetIndexToBeSetFromDomain(trimmedDomain, i, arraySize);
                        bloomFilterArray[index] = true;
                    }

                    Logger.LogInformation($"Domain '{trimmedDomain}' added.");
                }
            }
            return bloomFilterArray;
        }
private static int GetIndexToBeSetFromDomain(string domain, int shift, int bloomFilterArraySize)
        {
            int hash = CalculateHash(domain, shift);
            hash = Math.Abs(hash);
            return hash % bloomFilterArraySize;
        }
private static int CalculateHash(string domain, int shift)
        {
            var primeBaseIndex = shift % Primes.Length;

            int primeBase = Primes[primeBaseIndex];

            foreach (char currentChar in domain)
            {
                primeBase = (primeBase << shift) + primeBase + currentChar;
            }

            return primeBase;
        }

https://hur.st/bloomfilter/?n=3018&p=0.01&m=&k=4

区块链

原理

特性

应用场景

最后更新于 2023年5月18日 by qlili