# Bloom Filters

Several common data structures exploit randomness to achieve efficiency and
good average-case performance. We'll learn about two of them, Bloom Filters and
Skip Lists.

A Bloom filter is a **space-efficient probabilistic data structure** used to
quickly test whether an element is a member of a large set without accessing a
hard drive or network. A Bloom filter can be kept in RAM, when a full Set
cannot. The properties of a Bloom filter are:

- It does not store the items themselves, but instead stores a bit array which
  is altered in ways reminiscent of hash tables.
- It can definitively say, "this item is **definitely not** in the set."
- It can only say "this item is **probably** in the set." It occasionally
  returns false positives.

## How Bloom Filters Work

### 1\. Initialization

A Bloom filter is initialized by first allocating an array of $m$ bits, with all bits set to 0. Next, $k$ different, independent hash functions are selected. Each of these functions must map any input item to an index within the array's range, $[0, m-1]$.

### 2\. Insertion

To add an item to the set, the item is hashed by all $k$ hash functions to generate $k$ different indices. The bits at all $k$ of these positions in the array are then set to 1.

### 3\. Membership Query

To check if an item is in the set, the same process is followed: the item is
hashed with the same $k$ functions to get $k$ indices. The filter then checks
the bits at all $k$ positions. If *any* of those bits is 0, the item is
*definitely not* in the set, because all corresponding bits would have been set to 1 during insertion. If *all* the bits are 1, the item is *probably* in the set. This check is probabilistic because the bits may have been set to 1 by the insertion of *other* items, resulting in a false positive.

### 4\. Deletion

Standard Bloom filters do not support deletion. This is because clearing a bit from 1 to 0 could inadvertently affect the membership status of another item that hashes to the same bit. A variant called a **Counting Bloom Filter** can support deletion by replacing each bit with a small counter, but this solution comes at the cost of significantly more space.

### False Positive Rate

The probability that a specific bit is *not* set to 1 by a single hash function during one insertion is:

$$p = 1 - \frac{1}{m}$$

The probability it is *not* set by *any* of the $k$ hash functions during one insertion is:

$$p^k = \left(1 - \frac{1}{m}\right)^k$$

After $n$ elements have been inserted, the probability that a specific bit is still 0 is:

$$\left(p^k\right)^n = \left(1 - \frac{1}{m}\right)^{kn}$$

Therefore, the probability that the bit is 1 (has been set by at least one insertion) is:

$$q = 1 - \left(1 - \frac{1}{m}\right)^{kn}$$

A false positive occurs when checking for a *new* item, and all $k$ bits it hashes to *happen* to be 1 from previous insertions. The probability of this event is:

$$\text{False Positive Rate} \approx q^k = \left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k$$

### Trade-offs

The design of a Bloom filter involves balancing space, time, and accuracy.
Increasing $m$ (the size of the array) reduces the likelihood of hash
collisions, thereby decreasing the false positive rate at the cost of more
space.

Increasing $k$ (the number of hash functions) initially decreases the
false positive rate as more bits must be incidentally set to 1 in order to
trigger a false positive. After reaching an optimal point, however, it starts
to increase the false positive rate, as each insertion sets so many bits to 1
that false positive rates increase. An increase in $k$ also increases the
computational cost for insertions and queries.

Typically, a designer will estimate the expected number of items ($n$), decide
on an acceptable false positive rate, and then calculate the optimal values
for $m$ and $k$ to meet those requirements.

### Implementation

Here's an example implementation of a bloom filter.

```python
from bitarray import bitarray
import hashlib

class BloomFilter:
  # Sets a bit_array at the given bit capacity (default 1000 bits)
  def __init__(self, capacity=1000):
    self.capacity = capacity
    self.bit_array = bitarray(capacity)
    self.bit_array.setall(0)

  # Standard Python hash function
  def _hash1(self,key):
    return hash(key)

  # sha256 hash function
  def _hash2(self,key):
    m = hashlib.sha256()
    m.update(key.encode())
    h = m.hexdigest()
    return int(h,16)

  # md5 hash function
  def _hash3(self,key):
    m = hashlib.md5()
    m.update(key.encode())
    h = m.hexdigest()
    return int(h,16)

  # Calculates all hashes and returns them as a tuple
  def _allhashes(self,key):
    h1 = self._hash1(key)
    h2 = self._hash2(key)
    h3 = self._hash3(key)

    return (h1, h2, h3)

  # Calculates all hashes and mods them by the capacity of the bitarray
  # Returns a tuple
  def _modder(self,key):
    return tuple(h % self.capacity for h in self._allhashes(key))

  # Insert k into the Set
  def insert(self, k):
    indices = self._modder(k)
    for i in indices:
      self.bit_array[i] = 1

  # Searches for k in the set.
  # False means "definitely not in the set"
  # True means "probably in the set"
  def contains(self, k):
    indices = self._modder(k)
    for i in indices:
      if self.bit_array[i] == 0:
        return False
    return True
```