On: Ask HN: What are some cool but obscure data struct...

[noname120]

HyperLogLog[1] — approximately count distinct elements from an extremely large set (e.g. 10⁹ elements) super efficiently.

→ Distinct count time complexity[2]: O(1)

See Redis's PFCOUNT[4].

[1] https://en.wikipedia.org/wiki/HyperLogLog

[2] For a fixed number of registers (e.g. Redis's implementation)

[3] https://redis.io/commands/pfcount/