DataStructures/Probabilistic/BloomFilter.cs

using System;
using System.Collections.Generic;

namespace DataStructures.Probabilistic;

public class BloomFilter<T> where T : notnull
{
    private const uint FnvPrime = 16777619;
    private const uint FnvOffsetBasis = 2166136261;
    private readonly byte[] filter;
    private readonly int numHashes;
    private readonly int sizeBits;

    //github.com/ <summary>
    //github.com/ Initializes a new instance of the <see cref="BloomFilter{T}"/> class. This constructor will create a Bloom Filter
    //github.com/ of an optimal size with the optimal number of hashes to minimize the error rate.
    //github.com/ </summary>
    //github.com/ <param name="expectedNumElements">Expected number of unique elements that could be added to the filter.</param>
    public BloomFilter(int expectedNumElements)
    {
        numHashes = (int)Math.Ceiling(.693 * 8 * expectedNumElements / expectedNumElements); // compute optimal number of hashes
        filter = new byte[expectedNumElements]; // set up filter with 8 times as many bits as elements
        sizeBits = expectedNumElements * 8; // number of bit slots in the filter
    }

    //github.com/ <summary>
    //github.com/ Initializes a new instance of the <see cref="BloomFilter{T}"/> class.
    //github.com/ This constructor let's you decide how large you want the filter to be as well as allowing you to specify
    //github.com/ how many hashes it will use. Only use if you don't care to optimize false positivity.
    //github.com/ </summary>
    //github.com/ <param name="sizeBits">size in bits you want the filter to be.</param>
    //github.com/ <param name="numHashes">number of hash functions to be used.</param>
    public BloomFilter(int sizeBits, int numHashes)
    {
        filter = new byte[sizeBits / 8 + 1];
        this.numHashes = numHashes;
        this.sizeBits = sizeBits;
    }

    //github.com/ <summary>
    //github.com/ Inserts an item into the bloom filter.
    //github.com/ </summary>
    //github.com/ <param name="item">The item being inserted into the Bloom Filter.</param>
    public void Insert(T item)
    {
        foreach (var slot in GetSlots(item))
        {
            filter[slot / 8] |= (byte)(1 << (slot % 8)); // set the filter at the decided slot to 1.
        }
    }

    //github.com/ <summary>
    //github.com/ Searches the Bloom Filter to determine if the item exists in the Bloom Filter.
    //github.com/ </summary>
    //github.com/ <param name="item">The item being searched for in the Bloom Filter.</param>
    //github.com/ <returns>true if the item has been added to the Bloom Filter, false otherwise.</returns>
    public bool Search(T item)
    {
        foreach (var slot in GetSlots(item))
        {
            var @byte = filter[slot / 8]; // Extract the byte in the filter.
            var mask = 1 << (slot % 8); // Build the mask for the slot number.
            if ((@byte & mask) != mask)
            {
                return false;
            }
        }

        return true;
    }

    //github.com/ <summary>
    //github.com/ Yields the appropriate slots for the given item.
    //github.com/ </summary>
    //github.com/ <param name="item">The item to determine the slots for.</param>
    //github.com/ <returns>The slots of the filter to flip or check.</returns>
    private IEnumerable<int> GetSlots(T item)
    {
        var hash = item.GetHashCode();
        for (var i = 0; i < numHashes; i++)
        {
            yield return Math.Abs((i + 1) * hash) % sizeBits;
        }
    }
}