# Go package implementing Bloom filters

## Bloom filters

A Bloom filter is a representation of a set of *n* items, where the main requirement is to make membership queries; *i.e.*, whether an item is a member of a set.

A Bloom filter has two parameters: *m*, a maximum size (typically a reasonably large multiple of the cardinality of the set to represent) and *k*, the number of hashing functions on elements of the set. (The actual hashing functions are important, too, but this is not a parameter for this implementation). A Bloom filter is backed by a BitSet; a key is represented in the filter by setting the bits at each value of the hashing functions (modulo *m*). Set membership is done by *testing* whether the bits at each value of the hashing functions (again, modulo *m*) are set. If so, the item is in the set. If the item is actually in the set, a Bloom filter will never fail (the true positive rate is 1.0); but it is susceptible to false positives. The art is to choose *k* and *m* correctly.

In this implementation, the hashing functions used is murmurhash, a non-cryptographic hashing function.

This implementation accepts keys for setting and testing as `[]byte`

. Thus, to

add a string item, `"Love"`

:

```
n := uint(1000)
filter := bloom.New(20*n, 5) // load of 20, 5 keys
filter.Add([]byte("Love"))
```

Similarly, to test if `"Love"`

is in bloom:

```
if filter.Test([]byte("Love"))
```

For numeric data, I recommend that you look into the encoding/binary library. But, for example, to add a `uint32`

to the filter:

```
i := uint32(100)
n1 := make([]byte, 4)
binary.BigEndian.PutUint32(n1, i)
filter.Add(n1)
```

Finally, there is a method to estimate the false positive rate of a particular

bloom filter for a set of size *n*:

```
if filter.EstimateFalsePositiveRate(1000) > 0.001
```

Given the particular hashing scheme, it's best to be empirical about this. Note

that estimating the FP rate will clear the Bloom filter.

Discussion here: Bloom filter

Godoc documentation: https://godoc.org/github.com/willf/bloom

## Installation

```
go get -u github.com/willf/bloom
```

## Contributing

If you wish to contribute to this project, please branch and issue a pull request against master ("GitHub Flow")

This project include a Makefile that allows you to test and build the project with simple commands.

To see all available options:

```
make help
```

## Running all tests

Before committing the code, please check if it passes all tests using (note: this will install some dependencies):

```
make deps
make qa
```