[Algorithm] Data Structure - Bloom Filter

Bloom Filter?

A Bloom Filter is a probabilistic data structure used to test whether an element is a member of a set. It’s highly space-efficient but comes with a trade-off: false positives are possible, meaning it might occasionally indicate that an element is in the set when it’s not. However, false negatives (claiming that an element isn’t in the set when it is) are not possible.

Key Characteristics

1. Probabilistic Nature: It can tell you if an element is either “possibly in the set” or “definitely not in the set.”
2. Space-Efficient: Compared to traditional data structures like hash sets, Bloom filters require much less space to store a large set of items.
3. False Positives: Due to its probabilistic nature, it can sometimes report that an item is in the set when it’s not. The probability of false positives depends on the size of the filter and the number of elements added.

How it Works

1. Bit Array: A Bloom filter consists of a bit array of size m, initialized to 0.
2. Hash Functions: It uses k independent hash functions, each of which maps an element to one of the m array positions uniformly.
3. Insertion: To insert an element, the element is hashed with each of the k hash functions, and the corresponding bit positions in the array are set to 1.
4. Querying: To check whether an element is in the set, you hash the element with the k hash functions. If all the corresponding bits in the array are set to 1, the element is “possibly” in the set. If even one bit is 0, the element is definitely not in the set.

Use Cases

• Databases and Caching: Used to check if an element might exist in a cache or database to avoid expensive lookups.
• Network Systems: Filtering URLs, spam detection, etc.
• Distributed Systems: Quick checks to see if an element exists across distributed databases before performing a more expensive operation.

Time and Space Complexity

• Insertion and Query operations are both O(k), where k is the number of hash functions. This is constant time since k is usually small.
• Space Complexity is O(m), where m is the size of the bit array. Bloom filters are very space-efficient.

Bloom Filter in JavaScript

Here’s an implementation of a simple Bloom Filter in JavaScript:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class BloomFilter {
  constructor(size, numHashFunctions) {
    this.size = size;
    this.numHashFunctions = numHashFunctions;
    this.bitArray = new Array(size).fill(0);
  }

  // Simple hash functions based on a seed value
  hash(item, seed) {
    let hashValue = 0;
    for (let i = 0; i < item.length; i++) {
      hashValue = (hashValue * seed + item.charCodeAt(i)) % this.size;
    }
    return hashValue;
  }

  // Add an item to the Bloom Filter
  add(item) {
    for (let i = 0; i < this.numHashFunctions; i++) {
      const hashIndex = this.hash(item, i + 1);
      this.bitArray[hashIndex] = 1;
    }
  }

  // Check if an item might be in the set
  contains(item) {
    for (let i = 0; i < this.numHashFunctions; i++) {
      const hashIndex = this.hash(item, i + 1);
      if (this.bitArray[hashIndex] === 0) {
        return false; // Definitely not in the set
      }
    }
    return true; // Possibly in the set
  }
}

// Usage Example:
const bloom = new BloomFilter(100, 3);
bloom.add("apple");
bloom.add("banana");

console.log(bloom.contains("apple")); // Output: true (possibly in the set)
console.log(bloom.contains("grape")); // Output: false (definitely not in the set)

Explanation:

• hash is a simple function that generates hash values based on a seed.
• add inserts an item into the Bloom filter by setting bits at multiple positions based on the hash functions.
• contains checks whether an item might be in the set by verifying the bits in the array.

Bloom Filter in Rust

Here’s a Rust implementation of a simple Bloom Filter:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
struct BloomFilter {
    bit_array: Vec<bool>,
    size: usize,
    num_hash_functions: usize,
}

impl BloomFilter {
    // Create a new Bloom Filter
    fn new(size: usize, num_hash_functions: usize) -> BloomFilter {
        BloomFilter {
            bit_array: vec![false; size],
            size,
            num_hash_functions,
        }
    }

    // Simple hash function with a seed
    fn hash(&self, item: &str, seed: usize) -> usize {
        let mut hash_value = 0;
        for byte in item.bytes() {
            hash_value = (hash_value * seed + byte as usize) % self.size;
        }
        hash_value
    }

    // Add an item to the Bloom Filter
    fn add(&mut self, item: &str) {
        for i in 0..self.num_hash_functions {
            let hash_index = self.hash(item, i + 1);
            self.bit_array[hash_index] = true;
        }
    }

    // Check if an item might be in the set
    fn contains(&self, item: &str) -> bool {
        for i in 0..self.num_hash_functions {
            let hash_index = self.hash(item, i + 1);
            if !self.bit_array[hash_index] {
                return false;  // Definitely not in the set
            }
        }
        true  // Possibly in the set
    }
}

fn main() {
    let mut bloom = BloomFilter::new(100, 3);
    bloom.add("apple");
    bloom.add("banana");

    println!("{}", bloom.contains("apple"));  // Output: true (possibly in the set)
    println!("{}", bloom.contains("grape"));  // Output: false (definitely not in the set)
}

Explanation:

• The hash function creates a hash value for an item with a seed to vary the result.
• add modifies the Bloom filter’s bit array to mark the presence of an item.
• contains checks whether all the bits for a given item are set, indicating whether the item might be in the set.

Key Points:

• Bloom Filter is a space-efficient probabilistic data structure with no false negatives but possible false positives.
• It’s used in cases where you need to check quickly and efficiently if an element is part of a large set (e.g., in databases, network filtering).
• Both JavaScript and Rust implementations show how to build a basic Bloom Filter with hash functions and bit arrays.