Skip to content
Deduplicating 4 Billion QQ Numbers in 1GB Memory: Bitmap and Bloom Filter Deep Dive
Fundamentals 12 min read

Deduplicating 4 Billion QQ Numbers in 1GB Memory: Bitmap and Bloom Filter Deep Dive

This article explains how to deduplicate 4 billion unsigned integers within a 1GB memory constraint using Bitmap and Bloom Filter data structures, detailing memory calculations, implementation principles, false-positive trade-offs, and practical Java code examples with Guava, Apache Commons, and Redis.

Java Architect Handbook
Java Architect Handbook
Java Architect Handbook

The article opens with a concrete problem: 4 billion QQ numbers (unsigned 32‑bit integers) would require roughly 14.9 GB if stored directly ( 4 * 4000000000 / 1024 / 1024 / 1024 = 14.9G), far exceeding a 1 GB limit.

Bitmap Solution

A Bitmap uses a single bit per possible value. For 4 billion numbers the memory drops to 4000000000 * 1 / 8 / 1024 / 1024 = 476M, well within the budget. The author illustrates the mechanism: to insert QQ number 907607222, set the bit at index 907607222 to 1. After processing all numbers, every index with value 1 represents a unique number; duplicates naturally collapse because setting an already‑set bit changes nothing. A diagram shows the QQ number mapped to its bit position.

What Is a Bitmap?

A Bitmap is simply a bit array where each position holds 0 or 1. The article compares storing the set {1, 4, 6} with three unsigned int values (3 × 4 bytes = 12 bytes = 96 bits) versus a Bitmap needing only 7 bits (indices 0–6). The key advantage is space efficiency. Bitmaps suit deduplication and sorting; the famous Bloom Filter is built on top of them. The limitation: a Bitmap can only represent true/false, not arbitrary values.

Bloom Filter Principles

A Bloom Filter is a probabilistic data structure that tests whether an element might be in a set. It uses k independent hash functions to map an element to k bit positions in a bit array, setting all those bits to 1 on insertion. On query, if all k bits are 1 the element may exist; if any bit is 0 the element definitely does not exist. Because different elements can hash to the same positions (hash collisions), false positives are possible — an absent element may appear present. The article includes a diagram showing three hash functions mapping a “Hero” element to bits that happen to be set by other elements, causing a false positive.

To reduce the false‑positive rate, one can increase the bit‑array size (lowering collision probability) or add more hash functions (at the cost of slower inserts/lookups).

Bloom Filter Workflow

Initialization – specify expected element count and target false‑positive rate; the filter allocates a bit array and prepares k hash functions.

Add element – compute k hash indexes, set each corresponding bit to 1 (idempotent).

Query element – compute the same k indexes; if all bits are 1 return “possibly present”, otherwise “definitely absent”.

Drawbacks noted: (1) inherent false‑positive rate; (2) deletion is hard because clearing a bit might affect other elements that share that bit.

Typical Application Scenarios

Web crawlers – filter already‑crawled URLs to avoid duplicate work.

Cache systems – quickly check if a key might be in cache, reducing cache misses; also used to mitigate cache penetration.

Distributed systems – avoid querying every node for key existence.

Spam filtering – test email addresses against a spam blocklist.

Blacklist filtering – block malicious IPs or phone numbers.

Java Implementation Examples

The article provides ready‑to‑run code for three popular libraries.

Google Guava

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

public class BloomFilterExample {
    public static void main(String[] args) {
        // Expected 100 elements, 1% false‑positive rate
        BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(), 100, 0.01);
        bloomFilter.put("Lynn");
        bloomFilter.put("666");
        bloomFilter.put("八股文");
        System.out.println(bloomFilter.mightContain("Lynn"));   // true
        System.out.println(bloomFilter.mightContain("张三"));  // false
    }
}

Apache Commons Collections4

import org.apache.commons.collections4.BloomFilter;
import org.apache.commons.collections4.functors.HashFunctionIdentity;
import org.apache.commons.lang3.StringUtils;

public class BloomFilterExample {
    public static void main(String[] args) {
        BloomFilter<String> bloomFilter = new BloomFilter<>(
                HashFunctionIdentity.hashFunction(StringUtils::hashCode), 100, 0.01);
        bloomFilter.put("Lynn");
        bloomFilter.put("666");
        bloomFilter.put("八股文");
        System.out.println(bloomFilter.mightContain("Lynn"));   // true
        System.out.println(bloomFilter.mightContain("张三"));  // false
    }
}

Redis 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();

Redis via Jedis (using Redis Bloom module)

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();

Each snippet follows the same pattern: create/initialize the filter with expected capacity and error rate, add sample strings, then test membership. The article notes that the Redisson example uses tryInit for lazy initialization, while Jedis calls the Redis Bloom commands directly ( bfCreate, bfAdd, bfExists).

Original Source

Signed-in readers can open the original source through BestHub's protected redirect.

Sign in to view source
Republication Notice

This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactadmin@besthub.devand we will review it promptly.

JavaMemory OptimizationRedisBitmapDeduplicationGuavaData StructuresBloom Filter
Reader feedback

How this landed with the community

Sign in to like

Rate this article

Was this worth your time?

Sign in to rate
Discussion

0 Comments

Thoughtful readers leave field notes, pushback, and hard-won operational detail here.