Bitmap Dedup Slices 4 Billion QQ Numbers to 476MB
Membership checks at scale hit the same 15GB-versus-1GB wall, and the bitmap/Bloom filter pair is the standard escape. These patterns drop directly into caching, dedup, and blacklist code, with a clear trade-off between space and exactness that you tune by picking a false-positive rate.
The memory wall is real: 4 billion unsigned ints need 14.9GB, so a raw array is impossible on a 1GB budget. A bitmap allocates one bit per possible value, cutting the total to 476MB and making dedup a matter of setting bits and iterating over set bits. That's the core trick, and it costs nothing but a single bit per QQ number.
Bloom filters generalize the bitmap by using multiple hash functions to map elements into a bit array. Membership checks return "possibly present" when all mapped bits are set, which guarantees zero false negatives but allows false positives. The error rate shrinks with more hash functions and a larger bit array, but deletion becomes painful because bits are shared.
The typical applications are web crawler dedup, cache-penetration protection, spam filtering, and blacklist checks. Java implementations show up in Guava's BloomFilter, Apache Commons Collections, and Redis via Redisson or Jedis, each requiring an expected element count and a target false-positive probability.
The 476MB-to-15GB ratio shows why a bitmap is the go-to for presence checks; any exact count or frequency requirement forces a different structure.
Bloom filters trade exactness for space and speed, but the inability to delete elements makes them best for append-only workloads like crawled URLs or accumulated blacklists.
The post's per-element cost is so low that even a billion-scale dataset fits in a memory budget that many single instances can spare, which is what makes these patterns practical in production.