Bloom Filters and Bitmaps

When working with billions of data items (e.g., checking if a URL is malicious in Chrome, or checking if a username is already taken on Instagram), standard Hash Sets consume gigabytes of expensive RAM.

Probabilistic Data Structures sacrifice 100% precision in exchange for massive, exponential memory savings. The prime example is the Bloom Filter.

What is a Bloom Filter?

A Bloom Filter is a space-efficient probabilistic data structure that tests whether an element is a member of a set:

• It can report: "Possibly in the set" (False positive possible).
• Or it can report: "Definitely not in the set" (NO false negatives possible!).

The Golden Rule: A Bloom filter never lies when it says NO. It might be wrong when it says YES.

How It Works Internally

A Bloom Filter consists of:

1. A Bit Array of m bits, all initially set to 0.
2. k independent, uniform hash functions: h_1, h_2, ..., h_k.

Copy codeBit Array (m = 8): [ 0, 0, 0, 0, 0, 0, 0, 0 ]

Adding an Element:

1. Feed the element into all k hash functions.
2. Set the bits at the resulting indices to 1.

Copy codeInsert "apple":
h1("apple") = 1
h2("apple") = 4
h3("apple") = 7
Set bits 1, 4, 7 to 1:
Bit Array: [ 0, 1, 0, 0, 1, 0, 0, 1 ]

Querying an Element:

1. Feed the element into all k hash functions.
2. If ANY of the corresponding bits is 0, the element was DEFINITELY NOT added.
3. If ALL corresponding bits are 1, the element is PROBABLY in the set (or other keys coincidentally flipped those same bits, creating a false positive).

What is a Bitmap (Bitset)?

A Bitmap (or Bit Array) represents a dense set of booleans using individual hardware bits instead of bytes.

• In Java/Kotlin, a Boolean array uses 1 byte (8 bits) per boolean value.
• A BitSet packs 64 boolean flags into a single 64-bit Long primitive!
• Memory reduction: 8x less RAM!

Copy codeimport java.util.BitSet

val bitSet = BitSet(1000) // 1000 boolean flags
bitSet.set(42)            // Sets bit 42 to 1
val isSet = bitSet.get(42) // Returns true

Production Applications

1. Google Chrome Safe Browsing: Checks visited URLs against a local Bloom filter of malicious websites before querying Google's remote servers.
2. Databases (Cassandra, RocksDB, PostgreSQL): Uses Bloom filters to prevent costly disk reads for non-existent row keys.
3. Content Delivery Networks (CDNs): Avoids caching "one-hit-wonder" web pages that are requested only once.

Summary

• Bloom Filters use a bit array and k hash functions to test set membership with zero false negatives and small configurable false positives.
• Bitmaps pack boolean flags into individual bits, cutting memory consumption by 87.5%.
• Essential for database storage engines and high-scale distributed systems.