How Bitmap and Bloom Filter Save Memory and Speed Up Java Applications

Storing 4 billion unsigned integers directly would require about 14.9 GB of memory: 4*4000000000 /1024/1024/1024 = 14.9G Because many values may repeat, a bitmap can dramatically shrink the footprint.

With a bitmap each number occupies only one bit, so the same 4 billion numbers need: 4000000000 * 1 /8 /1024/1024 = 476M This reduces the required space from 14.9 GB to roughly 476 MB.

For example, to store the QQ number 907607222 in a bitmap you set the bit at position 907607222 to 1.

After inserting all numbers, bits set to 1 indicate presence, and scanning the bitmap yields the unique values.

What Is a Bitmap? What Is It Used For?

A bitmap (BitMap) is a bit array where each position holds a single bit (0 or 1). It is the smallest addressable unit in a computer and can represent the existence of an element.

The array can be visualised as:

For instance, the bitmap below represents the numbers 1, 4, 6:

Without a bitmap, storing three integers would need 3 × 4 bytes = 12 bytes = 96 bits, whereas the bitmap uses only 3 bits, demonstrating the space‑saving advantage.

Bitmaps are ideal for deduplication, fast membership tests, and are the foundation of Bloom filters.

Limitation: a bitmap can only represent two states (0/1) and cannot store arbitrary values.

What Is a Bloom Filter? How Does It Work?

A Bloom filter is a probabilistic data structure that tests whether an element may be in a set using a bit array and multiple hash functions.

When adding an element, each hash function maps it to several bit positions, which are set to 1. To query, the same hash functions are applied; if all corresponding bits are 1, the element is possibly present, otherwise it is definitely absent.

Bloom filters guarantee no false negatives but may produce false positives due to hash collisions.

False positives occur when different elements hash to the same bits, making a non‑existent element appear present.

Typical Workflow

Initialize the Bloom filter with an expected size and acceptable false‑positive rate.

Add elements by hashing them with multiple functions and setting the resulting bits.

Query an element by checking whether all its hashed bits are set.

Common Application Scenarios

Web crawlers – avoid revisiting already fetched URLs.

Cache systems – quickly test cache membership and prevent cache‑penetration attacks.

Distributed systems – reduce network traffic by pre‑filtering queries.

Spam filtering – check if an email address is in a known spam list.

Blacklist checking – block malicious IPs or phone numbers.

How to Use Bloom Filters in Java

Guava library example:

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class BloomFilterExample {
    public static void main(String[] args) {
        // Create a Bloom filter for up to 100 elements with 1% false‑positive rate
        BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(), 100, 0.01);
        // Add elements
        bloomFilter.put("Lynn");
        bloomFilter.put("666");
        bloomFilter.put("八股文");
        // Query elements
        System.out.println(bloomFilter.mightContain("Lynn")); // true
        System.out.println(bloomFilter.mightContain("张三")); // false
    }
}

Apache Commons Collections example:

import org.apache.commons.lang3.StringUtils;
import org.apache.commons.collections4.BloomFilter;
import org.apache.commons.collections4.functors.HashFunctionIdentity;
public class BloomFilterExample {
    public static void main(String[] args) {
        // Create a Bloom filter for 100 elements with 1% false‑positive rate
        BloomFilter<String> bloomFilter = new BloomFilter<>(HashFunctionIdentity.hashFunction(StringUtils::hashCode), 100, 0.01);
        // Add elements
        bloomFilter.put("Lynn");
        bloomFilter.put("666");
        bloomFilter.put("八股文");
        // Query elements
        System.out.println(bloomFilter.mightContain("Lynn")); // true
        System.out.println(bloomFilter.mightContain("张三")); // false
    }
}

Redis Bloom module via Redisson:

Config config = new Config();
config.useSingleServer().setAddress("redis://127.0.0.1:6379");
RedissonClient redisson = Redisson.create(config);
RBloomFilter<String> bloomFilter = redisson.getBloomFilter("myfilter");
bloomFilter.tryInit(100, 0.01);
 bloomFilter.add("Lynn");
 bloomFilter.add("666");
 bloomFilter.add("八股文");
 System.out.println(bloomFilter.contains("Lynn"));
 System.out.println(bloomFilter.contains("张三"));
 redisson.shutdown();

Jedis example:

Jedis jedis = new Jedis("localhost");
jedis.bfCreate("myfilter", 100, 0.01);
jedis.bfAdd("myfilter", "Lynn");
jedis.bfAdd("myfilter", "666");
jedis.bfAdd("myfilter", "八股文");
System.out.println(jedis.bfExists("myfilter", "Lynn"));
System.out.println(jedis.bfExists("myfilter", "张三"));
jedis.close();