Bloom Filter in C#

Here’s a simple implementation of a Bloom Filter.

    public class BloomFilter
    {
        HashAlgorithm hash;
        int m, n, k;
        BitArray table;

        public BloomFilter(HashAlgorithm h, int size, float falsePositiveRate)
        {
            hash = h;
            double bits = -(size * Math.Log(falsePositiveRate)) / Math.Pow(Math.Log(2), 2);
            double hashes = -Math.Log(0.7) * bits / size;
            n = size;
            k = (int)hashes;
            m = (int)bits;
            table = new BitArray(m);
        }

        IEnumerable<int> Probe(byte[] input)
        {
            int chunks = hash.HashSize / 32;
            for (int i = 0; i < k; i++)
            {
                byte[] val = hash.ComputeHash(input);
                for (int j = 0; j < chunks && i < k; j++, i++)
                    yield return Math.Abs(BitConverter.ToInt32(val, j)) % m;
            }
        }

        public void PutValue(byte[] input)
        {
            foreach (int index in Probe(input))
                table.Set(index,true);
        }

        public bool Exists(byte[] input)
        {
            foreach (int index in Probe(input))
            {
                if (!table.Get(index)) return false;
            }
            return true;
        }

    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s