Bloom Filter C#

Question

Here is a bloom filter I made in C#:

public class BloomFilter
{
    private BitArray PosValues = new BitArray(int.MaxValue);
    private BitArray NegValues = new BitArray(int.MaxValue);

    public void AddValue(int HashCode)
    {
        if (HashCode > 0)
        {
            PosValues[HashCode - 1] = true;
        }
        else if (HashCode < 0)
        {
            NegValues[-HashCode - 1] = true;
        }
    }

    public bool ValueUsed(int HashCode)
    {
        if (HashCode > 0)
        {
            return PosValues[HashCode - 1];
        }
        else if (HashCode < 0)
        {
            return NegValues[-HashCode - 1];
        }
        return true;
    }
}

And here is an example of how I use it:

public void Test()
{
    BloomFilter bloomFilter = new BloomFilter();

    MessageBox.Show(bloomFilter.ValueUsed("Test".GetHashCode()).ToString()); //Return false.
    bloomFilter.AddValue("Test".GetHashCode()); //Add the string to the bloom filter.
    MessageBox.Show(bloomFilter.ValueUsed("Test".GetHashCode()).ToString()); //Returns true.
}

Is this a good implementation of a bloom filter?

Answer 1

Naming

• Please try to follow the C# standard naming, like
  • private members should use camel casing
  • method parameters should use camel casing (except positional records)
  • etc.
• Please try to avoid short names / abbreviation when possible
  • PosValues >> positiveValues

BitArray

• I haven't used this structure before so I had to read about it :D
• You can also mark them as readonly

AddValue

• Based on the provided example it might make sense to expect a string as a parameter and call the GetHashCode inside this method
• [-HashCode - 1]: It is pretty easy to miss the - operator at the beginning
  • I would suggest to use HashCode * -1 instead to make your intent more visible
• I would also suggest a bit of restructuring to avoid using guard expressions

if (HashCode = 0) return;
var isHashCodePositive = HashCode > 0;
BitArray toBeUpdatedArray = isHashCodePositive ? PosValues : NegValues;
int index = isHashCodePositive ? HashCode : HashCode * -1;

toBeUpdatedArray[index - 1] = true;

ValueUsed

• In case of C# we usually have the following naming convention for bool returning members:
  • If it is a property then prefix it with is >> IsValueUsed
  • If it is a method then prefix it with has >> HasValueUsed
  • I've worked at a company where only is prefix was used everywhere
• I have the same advices here as I've listed at AddValue

---

For the sake of completeness here is the revised version of your BloomFilter class

public class BloomFilter
{
    private readonly BitArray positiveValues = new BitArray(int.MaxValue);
    private readonly BitArray negativeValues = new BitArray(int.MaxValue);

    public void AddValue(string value)
    {
        int hashCode = value?.GetHashCode() ?? 0;
        if (hashCode == 0) return;

        var isHashCodePositive = hashCode > 0;
        BitArray toBeUpdatedArray = isHashCodePositive ? positiveValues : negativeValues;
        int index = isHashCodePositive ? hashCode : hashCode * -1;

        toBeUpdatedArray[index - 1] = true;
    }

    public bool HasValueUsed(string value)
    {
        int hashCode = value?.GetHashCode() ?? 0;
        if (hashCode == 0) return true;

        var isHashCodePositive = hashCode > 0;
        BitArray toBeLookedUpArray = isHashCodePositive ? positiveValues : negativeValues;
        int index = isHashCodePositive ? hashCode : hashCode * -1;

        return toBeLookedUpArray[index - 1];
    }
}

Of course the common part could be extracted to reduce redundancy

public class BloomFilter
{
    private readonly BitArray positiveValues = new (int.MaxValue);
    private readonly BitArray negativeValues = new (int.MaxValue);

    public void AddValue(string value)
    {
        var (hashCode, isPositive) = GetHashCode(value);
        if (hashCode == 0) return;

        var (array, index) = GetArrayAndIndex(hashCode, isPositive);
        array[index] = true;
    }

    public bool HasValueUsed(string value)
    {
        var (hashCode, isPositive) = GetHashCode(value);
        if (hashCode == 0) return true;

        var (array, index) = GetArrayAndIndex(hashCode, isPositive);
        return array[index];
    }

    private static (int HashCode, bool IsPositive) GetHashCode(string value)
    {
        int hashCode = value?.GetHashCode() ?? 0;
        bool isPositive = hashCode > 0;
        return (hashCode, isPositive);
    }

    private (BitArray Array, Index) GetArrayAndIndex(int hashCode, bool isPositive)
    {
        BitArray array = isPositive ? positiveValues : negativeValues;
        int index = isPositive ? hashCode : hashCode * -1;
        return (array, index - 1);
    }
}

Answer 2

Is this a Bloom filter?

A Bloom filter is, IMO, a data structure that uses a bit array smaller than the domain of values that it's storing the presence of, and uses several hashes to optimize the false positive rate.

What we have here, is (mostly) a bit array. You could argue that it is a Bloom filter with extreme parameters: only one hash, but (almost) the maximum number of entries. But I don't really see that as Bloom filter, it doesn't have the space vs false-positives trade off that Bloom filters have.

A Bloom filter with approximately 2³² entries (very extreme, but that's what we have here so let's compare it to that) could have a lower false-positive rate, for example if we expect to insert a billion elements then the number of hash functions should be 3 and the probability of a false-positive would be approximately 12.7%, while with 1 hash function (which is what is implemented here) it would be approximately 20%.

In such an extreme case (with this many entries), it does not help to implement the extra hashes by re-hashing the hash, the extra hashes would have to be truly independent hashes (which also means that the interface cannot simply take one hash, that is not enough information). Otherwise, if multiple values all hash to some integer h, the hashes of that hash would also all be the same anyway, so the extra hashes would not help to disambiguate the value. With fewer entries you can sometimes reuse the same hash, for example with 2¹⁰ entries you can extract three 10-bit hashes from a 32-bit hash, and still have a couple of bits left over.

Bug

int.MinValue is a perfectly fine hash, but -HashCode - 1 would evaluate to int.MaxValue, which is just out of bounds (the underlying BitArray hash a length of int.MaxValue, so this is out of bounds by just 1).

Both bit arrays have length int.MaxValue, so we're "missing" two entries compared to the full domain of int. Zero is explicitly ignored, but another value has to be sacrificed as well to make things fit. The natural choice is int.MinValue. Of course another option is implementing your own bit array (which is very easy actually), then it can simply have 2³² entries and no quirks.

A Bloom filter with 2³² entries is extreme anyway. If you use fewer than 2³¹ entries, it would fit in a single BitArray without any trouble.