So schreiben Sie einen Bloom-Filteralgorithmus mit C#

So schreiben Sie mit C# einen Bloom-Filteralgorithmus

Ein Bloom-Filter ist eine sehr platzsparende Datenstruktur, mit der ermittelt werden kann, ob ein Element zu einer Menge gehört. Seine Grundidee besteht darin, Elemente über mehrere unabhängige Hash-Funktionen in ein Bit-Array abzubilden und die Bits des entsprechenden Bit-Arrays als 1 zu markieren. Bei der Beurteilung, ob ein Element zur Menge gehört, müssen Sie nur beurteilen, ob die Bits des entsprechenden Bitarrays alle 1 sind. Wenn ein Bit 0 ist, kann festgestellt werden, dass sich das Element nicht in der Menge befindet. Bloom-Filter zeichnen sich durch schnelle Abfragen und geringen Platzbedarf aus und werden in vielen Szenarien häufig verwendet.

In diesem Artikel wird das Schreiben des Bloom-Filteralgorithmus mit C# vorgestellt und spezifische Codebeispiele bereitgestellt.

Zuerst müssen wir eine Bloom-Filterklasse definieren und einige notwendige Variablen und Methoden deklarieren. Das Folgende ist die Definition einer einfachen Bloom-Filterklasse:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Security.Cryptography;

public class BloomFilter
{
    private BitArray _bits;
    private int _hashFunctionsCount;

    public BloomFilter(int capacity, double falsePositiveRate)
    {
        int bitsCount = GetBitsCount(capacity, falsePositiveRate);
        _bits = new BitArray(bitsCount);
        _hashFunctionsCount = GetHashFunctionsCount(bitsCount, capacity);
    }

    public void Add(string item)
    {
        foreach (int hash in GetHashes(item))
        {
            _bits.Set(Math.Abs(hash % _bits.Length), true);
        }
    }

    public bool Contains(string item)
    {
        foreach (int hash in GetHashes(item))
        {
            if (!_bits[Math.Abs(hash % _bits.Length)])
            {
                return false;
            }
        }
        return true;
    }

    private IEnumerable<int> GetHashes(string item)
    {
        using (SHA256 sha256 = SHA256.Create())
        {
            byte[] hashBytes = sha256.ComputeHash(System.Text.Encoding.UTF8.GetBytes(item));
            for (int i = 0; i < _hashFunctionsCount; i++)
            {
                yield return BitConverter.ToInt32(hashBytes, i * 4);
            }
        }
    }

    private int GetBitsCount(int capacity, double falsePositiveRate)
    {
        return (int)Math.Ceiling(capacity * Math.Log(falsePositiveRate) / Math.Log(1 / Math.Pow(2, Math.Log(2))));
    }

    private int GetHashFunctionsCount(int bitsCount, int capacity)
    {
        return (int)Math.Round((double)(bitsCount / capacity) * Math.Log(2));
    }
}

Der obige Code definiert eine BloomFilter-Klasse, die den Konstruktor, die Add-Methode und Contains< enthält /code>Methode. Der Konstruktor erhält zwei Parameter: Kapazität und Falsch-Positiv-Rate. Basierend auf diesen beiden Parametern werden die erforderliche Bit-Array-Größe und die Anzahl der Hash-Funktionen berechnet. Die Methode <code>Add wird verwendet, um Elemente zum Bloom-Filter hinzuzufügen, die Elemente über mehrere Hash-Funktionen in Bit-Arrays abzubilden und die Bits der entsprechenden Bit-Arrays als 1 zu markieren. Die Methode Contains wird verwendet, um zu bestimmen, ob ein Element im Bloom-Filter vorhanden ist, das Element über mehrere Hash-Funktionen einem Bit-Array zuzuordnen und zu bestimmen, ob die Bits des entsprechenden Bit-Arrays alle 1 sind. BloomFilter类，其中包含了构造函数、Add方法和Contains方法。构造函数接收两个参数：容量和误判率，根据这两个参数计算出需要的位数组大小和哈希函数个数。Add方法用于向布隆过滤器中添加元素，将元素通过多个哈希函数映射到位数组中，并将对应位数组的位标记为1。Contains方法用于判断一个元素是否存在于布隆过滤器中，通过多个哈希函数将元素映射到位数组中，并判断对应位数组的位是否都为1。

接下来，我们可以使用布隆过滤器类进行测试。以下是一个简单的示例：

using System;

public class Program
{
    public static void Main(string[] args)
    {
        BloomFilter bloomFilter = new BloomFilter(100000, 0.01);

        bloomFilter.Add("apple");
        bloomFilter.Add("banana");
        bloomFilter.Add("orange");

        Console.WriteLine(bloomFilter.Contains("apple")); // 输出：True
        Console.WriteLine(bloomFilter.Contains("banana")); // 输出：True
        Console.WriteLine(bloomFilter.Contains("orange")); // 输出：True
        Console.WriteLine(bloomFilter.Contains("watermelon")); // 输出：False
    }
}

以上示例代码创建了一个布隆过滤器对象，并向其中添加了三个元素("apple", "banana", "orange")。然后，通过Contains

Als nächstes können wir die Bloom-Filterklasse zum Testen verwenden. Hier ist ein einfaches Beispiel:

rrreee

Der obige Beispielcode erstellt ein Bloom-Filterobjekt und fügt ihm drei Elemente („Apfel“, „Banane“, „Orange“) hinzu. Verwenden Sie dann die Methode Contains, um zu ermitteln, ob ein Element im Bloom-Filter vorhanden ist.

Es ist zu beachten, dass es bei der Beurteilung, ob sich ein Element im Bloom-Filter befindet, zu Fehleinschätzungen kommen kann, da der Bloom-Filter eine gewisse Fehleinschätzungsrate aufweist. Daher eignen sich Bloom-Filter vor allem für Szenarien, die eine gewisse Fehleinschätzungsrate tolerieren können, beispielsweise die Feststellung, ob eine URL besucht wurde. 🎜🎜Zusammenfassend stellt dieser Artikel vor, wie man den Bloom-Filteralgorithmus mit C# schreibt, und stellt relevante Codebeispiele bereit. Als effiziente Datenstruktur hat der Bloom-Filter in einigen spezifischen Szenarien einen wichtigen Anwendungswert. Ich hoffe, dass dieser Artikel zum Verständnis und zur Anwendung des Bloom-Filteralgorithmus beitragen kann. 🎜

Das obige ist der detaillierte Inhalt vonSo schreiben Sie einen Bloom-Filteralgorithmus mit C#. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!