> ## Content Index
> Fetch the complete content index at: https://savasayik.com/llms.txt
> Use this file to discover other available public pages before exploring further.

# What is a Bloom Filter?
- URL: https://savasayik.com/what-is-a-bloom-filter/
- Published: 2025-04-13T15:14:45.000Z
- Updated: 2025-04-20T18:02:04.000Z
- Description: Think of a database cop... It can’t always confirm who’s in, but if it says someone’s not there — trust it. That’s Bloom Filter for you!
- Author: Savas AYIK
- Tags: Development, #Import 2025-10-26 11:39

A **Bloom filter** is a **lightweight**, **probabilistic** data structure used to **quickly check** whether an element is a member of a set. Its key characteristic is that it can **definitively say if an item is *not* in the set**, but it can only say an item is *probably* in the set — meaning it may sometimes produce **false positives** (reporting something exists when it actually doesn't).

A Bloom filter does **not store the actual data** itself. Instead, it keeps track of membership information by marking bits in a fixed-size bit array. This makes it extremely **space-efficient**, allowing it to represent millions of entries with just a few megabytes of memory. Operations are also performed in **constant time** (O(1)), making it very fast.

However, there are trade-offs. Traditional Bloom filters do not support removing or updating elements, and the possibility of false positives must be considered. This makes them most suitable for cases where **perfect accuracy is not required**, and the goal is to avoid unnecessary database queries or reduce memory usage.

In summary, Bloom filters are ideal for **membership checks** in large datasets where speed and memory efficiency matter more than perfect accuracy. They're commonly used in web caching, malicious URL detection, spam filters, NoSQL database indexing, and big data processing.

## How Does a Bloom Filter Work?

1. A Bloom filter starts with a fixed-size **bit array** (e.g., 10,000 bits), all set to `0`.
2. To add an item, multiple **hash functions** are applied to the item to determine positions in the bit array.
3. The bits at those positions are set to `1`.
4. To check for membership:
  - The same hash functions are used on the query item.
  - If *all* corresponding bits are `1`, the item is *probably present*.
  - If *any* bit is `0`, the item is *definitely not present*.

## Simple Example

Imagine the bit array looks like this:

```pgsql

Bit Set: [0, 1, 0, 1, 0, 0, 1, 0, 0, 0]

```

- `"savasayik"` → hash1 = 1, hash2 = 3, hash3 = 6 → all are `1` → **Probably present**
- `"mehmet"` → hash1 = 2, hash2 = 4, hash3 = 7 → bit 2 = `0` → **Definitely not present**

![](https://savasayik.com/content/images/2025/04/bloom_filter_hash_v3-1.jpg)

## Real-World Use Cases

| Use Case          | Description                                                       |
| ----------------- | ----------------------------------------------------------------- |
| **Web Caching**   | Quickly check if a URL has already been accessed                  |
| **Email Systems** | Is the sender in the spam list?                                   |
| **Web Browsers**  | Chrome and Firefox use them to detect malicious URLs              |
| **Databases**     | ClickHouse, Cassandra, HBase use Bloom filters for fast filtering |
| **Blockchain**    | Used in Ethereum light clients for fast membership checking       |
| **Big Data**      | Employed in Hadoop, Spark, and Flink for efficient filtering      |

## Comparison to Classic Data Structures

| Feature           | Bloom Filter         | Hash Set / Map      |
| ----------------- | -------------------- | ------------------- |
| Memory Usage      | Very Low             | High                |
| False Positives   | Yes (rare)           | No                  |
| Lookup Speed      | Constant (very fast) | Fast (but costlier) |
| Stores Data       | No                   | Yes                 |
| Supports Deletion | No (in basic form)   | Yes                 |

## Simple Bloom Filter Example in Go

```go
package main

import (
	"fmt"
	"hash/fnv"
)

const size = 1000 // Size of the bit array

type BloomFilter struct {
	bitset []bool
}

func NewBloomFilter() *BloomFilter {
	return &BloomFilter{
		bitset: make([]bool, size),
	}
}

// Two simple hash functions using FNV
func hash1(s string) int {
	h := fnv.New32()
	h.Write([]byte(s))
	return int(h.Sum32()) % size
}

func hash2(s string) int {
	h := fnv.New64()
	h.Write([]byte(s))
	return int(h.Sum64()) % size
}

func (bf *BloomFilter) Add(item string) {
	bf.bitset[hash1(item)] = true
	bf.bitset[hash2(item)] = true
}

func (bf *BloomFilter) PossiblyContains(item string) bool {
	return bf.bitset[hash1(item)] && bf.bitset[hash2(item)]
}

func main() {
	bf := NewBloomFilter()

	// Adding values
	bf.Add("savasayik")
	bf.Add("mustafasandal")

	// Checking membership
	fmt.Println("savasayik:", bf.PossiblyContains("savasayik"))       // true
	fmt.Println("mustafasandal:", bf.PossiblyContains("mustafasandal")) // true
	fmt.Println("mehmet:", bf.PossiblyContains("mehmet"))             // false (or rarely true)
}

```

Notes

- We use two FNV hash functions (`fnv.New32` and `fnv.New64`) for simplicity.
- This Bloom filter only supports `Add` and `PossiblyContains` operations.
- False positives are possible, but false negatives are not.

Use a real package like `github.com/willf/bloom` for production use.