Bitmaps and HyperLogLog

[!NOTE] This module explores the core principles of Bitmaps and HyperLogLog, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Bitmaps: The Power of Bits

A Bitmap is not a data structure; it’s a set of bit-level operations on a String. Since a String can be 512MB, you can store 2^{32} bits.

  • Space: 1 million users take ~128KB of RAM.
  • Speed: O(1) to set/get a bit.
  • Use Case: Real-time Analytics (DAU - Daily Active Users).

Tracking Daily Active Users

Assign each user an integer ID (offset). If User 100 logs in, set bit 100 to 1.

// User 100 logged in today
jedis.setbit("visits:2023-10-01", 100, true);

// Count active users
long dau = jedis.bitcount("visits:2023-10-01");

// Check if User 100 was active
boolean active = jedis.getbit("visits:2023-10-01", 100);