Bloom Filters in Go

Introduction

A Bloom filter is a space-efficient probabilistic data structure used to test whether an element is a member of a set. Unlike traditional data structures, Bloom filters can return false positives (indicating that an element is in the set when it is not), but never false negatives (indicating that an element is not in the set when it is). This makes them useful in scenarios where the cost of false positives is low, and memory efficiency is crucial.

Key Concepts

• Probabilistic Nature: Bloom filters use multiple hash functions to map elements to a bit array. The presence of an element is determined by checking if all corresponding bits are set. The more hash functions and the larger the bit array, the lower the probability of false positives.
• False Positive Rate: The likelihood that a Bloom filter incorrectly reports the presence of an element. This rate can be controlled by adjusting the size of the bit array and the number of hash functions.

Implementation in Go

To implement a Bloom filter in Go, follow these steps:

1. Define the structure of the Bloom filter.
2. Initialize the bit array and hash functions.
3. Implement methods to add elements and check membership.

Bloom Filter Structure

go
package main

import (
	"crypto/sha256"
	"encoding/binary"
	"hash"
	"hash/fnv"
	"math"
)

type BloomFilter struct {
	bitArray  []bool
	numHashes int
}

// NewBloomFilter initializes a new Bloom filter with the given size and number of hash functions.
func NewBloomFilter(size int, numHashes int) *BloomFilter {
	return &BloomFilter{
		bitArray:  make([]bool, size),
		numHashes: numHashes,
	}
}

// hashFunctions generates a list of hash functions.
func hashFunctions() []hash.Hash {
	return []hash.Hash{fnv.New64(), sha256.New()}
}

// Add inserts an element into the Bloom filter.
func (bf *BloomFilter) Add(item []byte) {
	hashes := hashFunctions()
	for i := 0; i < bf.numHashes; i++ {
		hash := hashElement(hashes, item, i)
		index := hash % uint64(len(bf.bitArray))
		bf.bitArray[index] = true
	}
}

// Check tests if an element is in the Bloom filter.
func (bf *BloomFilter) Check(item []byte) bool {
	hashes := hashFunctions()
	for i := 0; i < bf.numHashes; i++ {
		hash := hashElement(hashes, item, i)
		index := hash % uint64(len(bf.bitArray))
		if !bf.bitArray[index] {
			return false
		}
	}
	return true
}

// hashElement combines multiple hash functions to create a unique hash.
func hashElement(hashes []hash.Hash, item []byte, i int) uint64 {
	hash := hashes[i%len(hashes)]
	hash.Reset()
	hash.Write(item)
	return binary.BigEndian.Uint64(hash.Sum(nil))
}

func main() {
	// Create a Bloom filter with a size of 1000 bits and 3 hash functions
	bf := NewBloomFilter(1000, 3)

	// Add elements to the Bloom filter
	bf.Add([]byte("Hello"))
	bf.Add([]byte("World"))

	// Check for membership
	println(bf.Check([]byte("Hello"))) // Output: true
	println(bf.Check([]byte("Go")))    // Output: false (likely)
}

Explanation

1. BloomFilter Structure:

   • bitArray is a slice of booleans representing the bit array.
   • numHashes is the number of hash functions used.

2. NewBloomFilter:

   • Initializes the bit array and sets the number of hash functions.

3. hashFunctions:

   • Returns a slice of hash functions (FNV-1a and SHA-256 in this example).

4. Add:

   • Inserts an element into the Bloom filter by hashing it with each hash function and setting the corresponding bits.

5. Check:

   • Checks for the presence of an element by verifying that all corresponding bits for each hash function are set.

6. hashElement:

   • Combines multiple hash functions to create a unique hash for each element.

Calculating False Positive Rates

The false positive rate (FPR) of a Bloom filter can be approximated using the formula:

$\text{FPR} = \left(1 - e^{-\frac{k \cdot n}{m}}\right)^k$

Where:

• $k$ is the number of hash functions.
• $n$ is the number of inserted elements.
• $m$ is the size of the bit array.

By adjusting $k$ and $m$, you can control the trade-off between space efficiency and the likelihood of false positives.

Practical Applications

• Caching: Quickly check if an item might be in the cache.
• Databases: Filter out non-existent rows before performing more expensive queries.
• Networking: Preventing malicious activity by quickly checking blacklists.

Conclusion

Bloom filters provide a highly efficient means of membership testing with a controllable false positive rate. By understanding their probabilistic nature and implementation, you can effectively utilize Bloom filters in scenarios where memory efficiency and speed are critical. This example in Go demonstrates the fundamental concepts and implementation steps, providing a foundation for further optimization and application-specific adjustments.