How do you count unique visitors without remembering every visitor?

Hash each visitor identifier to a random-looking value and keep only a small summary statistic of those hashes. Identical identifiers produce identical hashes, so a repeat changes nothing; a fixed number of small counters then estimates how many distinct visitors there were without storing any identifier. The answer is an estimate, not an exact list, and its memory is chosen by the error you can tolerate rather than by the number of visitors.

The hash is the same every time the same visitor arrives. If visitor A hashes to a value beginning 0101 and visitor B to one beginning 0001, then A returning later brings 0101 again, not a new value. A sketch that keeps only a statistic of hashes, such as the longest run of leading zeros seen, therefore cannot be affected by repetition. It never needs a set of seen identifiers, a bloom filter, or a database key, because repetition is invisible by construction.

A uniform hash begins with a zero with probability one half, with two zeros with probability one quarter, and with k zeros with probability $1/2^k$. Turn that round: if the longest run of leading zeros observed is k, the number of distinct hashes drawn is probably around $2^k$. Seeing seven leading zeros suggests about $2^7 = 128$ distinct visitors; eleven suggests about $2^{11} = 2048$. The estimate moves in powers of two, so one such counter is far too coarse to report, but it is a real estimate and it uses one small integer.

The natural guess is that an exact distinct count needs every identifier, so the only way round it is a bigger machine or a disk. That does not remove the requirement; it postpones it. A hundred million identifiers at sixteen bytes each is 1.6 billion bytes, about 1.6 gigabytes, and a billion is sixteen gigabytes. Accepting an estimate changes the requirement: memory is then set by the error you want, not by how many visitors arrive.

One counter has enormous variance, so split the hash instead of hashing many times. Take the first fourteen bits as a bucket number, giving $2^{14} = 16384$ buckets, and use the rest of the hash for the leading-zero count inside that bucket. Each bucket sees roughly one sixteen-thousandth of the distinct visitors and holds one small integer. Combining the buckets with a harmonic mean, rather than an arithmetic mean, stops one wild bucket from dominating, and a constant correction removes the remaining bias.

The error depends on the number of buckets and not on the number of visitors. With 16384 buckets and c about 1.04, $e = 1.04 / \sqrt{16384} = 1.04 / 128 = 0.008125$, which is 0.8125 per cent, rounded to about one per cent. At six bits per register, 16384 registers need $16384 \times 6 = 98304$ bits, and $98304 / 8 = 12288$ bytes, about twelve kilobytes. That size stays twelve kilobytes whether the stream has a thousand distinct visitors or a billion.