# HyperLogLog

HyperLogLog is a probabilistic data structure used for estimating the **cardinality** (the number of distinct elements) of a set. It is famous for being able to count billions of unique items using a tiny, fixed amount of memory.

## 1. The Problem: Counting Distinct Items

Counting unique items (e.g., "How many unique visitors did my website have today?") is easy with a small dataset: just use a Hash Set.

However, if you have billions of visitors, storing every unique IP address or User ID in a Set requires massive amounts of RAM. An exact count becomes expensive.

## 2. The Solution: Probabilistic Counting

HyperLogLog trades a small amount of accuracy for massive memory savings. It doesn't store the actual elements. Instead, it observes the randomness of hashed values to estimate the count.

### The Intuition (Coin Flips)
Imagine you flip a coin until you get heads.
*   If you tell me it took you 1 flip, I'm not impressed.
*   If you tell me it took you 10 flips in a row to get heads (0000000001), I assume you probably flipped the coin many, many times to get that lucky sequence.

HyperLogLog hashes every element to a binary string. It looks at the **longest run of leading zeros** in those hashes. The longer the run of zeros, the more distinct elements you have likely seen.

## 3. Accuracy vs. Memory

*   **Memory:** A standard HyperLogLog implementation takes about **1.5 KB** of memory to count up to $10^9$ (1 billion) items.
*   **Accuracy:** The typical error rate is around **0.81%**.

## 4. Operations

*   **Add:** Hash the item and update the internal registers (buckets).
*   **Count:** Calculate the estimate based on the registers (using harmonic mean to reduce outliers).
*   **Merge:** You can merge two HyperLogLogs (e.g., merge "Monday Uniques" and "Tuesday Uniques" to get "Total Uniques") without losing precision.

## 5. Use Cases

*   **Big Data Analytics:** Counting unique users, distinct search queries, or unique video views.
*   **Databases:** Redis has built-in commands (`PFADD`, `PFCOUNT`) for HyperLogLog.
*   **Networking:** Detecting distinct flows or IP addresses passing through a router.

[[programming/bloom-filters]]
[[programming/hash-tables]]
[[programming/distributed-systems]]