Probabilistic & randomized data structures, made tangible
These structures trade a small, known chance of error for massive savings in memory and time, often turning an O(n) memory problem into O(log n) or O(1). Each page below lets you add real items and watch the internal bits, counters, buckets, and registers change live, so the trade-off stops being abstract. Two pages are explicit exceptions: Roaring Bitmap is exact rather than probabilistic, included for its shared "bit array at scale" lineage, and Consistent Hashing is a randomized partitioning/routing structure rather than an approximate sketch, included for its shared "hash the input, trade a knob for a better distribution" lineage. Neither broadens the site into general-purpose data structures.
Two families, one idea (plus two explicit exceptions)
Set membership ("have I seen this exact item?")
Bloom Filter, Counting Bloom Filter, and Cuckoo Filter all answer "is x possibly in this set?" using far less memory than storing the set itself, accepting rare false positives (saying "maybe" for something never added) in exchange for never producing false negatives.
Stream summarization ("how many / how many distinct / how similar / what percentile?")
Count-Min Sketch estimates frequency, HyperLogLog estimates distinct count (cardinality), HyperMinHash rides a small MinHash signature on top of HLL registers to add set similarity to that same cardinality estimate, MinHash estimates set similarity directly, and t-digest estimates percentiles: each compresses a potentially huge stream into a small, fixed-size sketch with a mathematically bounded error.
Compressed exact sets ("which of these integers are in the set, fast?")
Roaring Bitmap doesn't fit the trade-off above: it stores a set of integers exactly, with no error rate at all. It's here because it answers a closely related question with the same family of bit-level tricks, not because this site is broadening into general-purpose exact data structures.
Partitioning / routing ("which node owns this key?")
Consistent Hashing also doesn't fit the trade-off above: given a fixed set of nodes it deterministically routes each key, with no error rate to bound. Its randomization is in how evenly keys spread across nodes and how little remaps when membership changes, not in whether a lookup is correct.
Explore a structure
Bloom Filter
Is this item possibly in the set?
Open interactive demo →Counting Bloom Filter
A Bloom filter that supports deletion
Open interactive demo →Scalable Bloom Filter
A Bloom filter that grows to keep its false-positive rate bounded
Open interactive demo →Stable Bloom Filter
Membership testing over unbounded streams in bounded memory
Open interactive demo →Cuckoo Filter
Membership testing with deletion and better space use
Open interactive demo →Count-Min Sketch
How many times has this item appeared?
Open interactive demo →Top-K / Space-Saving
What are the most frequent items in this stream?
Open interactive demo →HyperLogLog
How many distinct items have I seen?
Open interactive demo →UltraLogLog
HyperLogLog, but each register can learn more from every hash
Open interactive demo →ExaLogLog
UltraLogLog's successor: registers that remember more, for exa-scale counts
Open interactive demo →Recordinality
How many distinct items, counted by "records" instead of runs?
Open interactive demo →HyperMinHash
How similar are these two streams, straight from HLL registers?
Open interactive demo →MinHash / LSH
How similar are these two sets?
Open interactive demo →Theta Sketch
Cardinality estimation with exact union/intersection/difference
Open interactive demo →t-digest
What is the p50 / p95 / p99 of this stream?
Open interactive demo →Xor Filter
Static membership testing, smaller and faster than Bloom or Cuckoo
Open interactive demo →Roaring Bitmap
A compressed exact bitmap for fast set operations over integers
Open interactive demo →Skip List
A randomized alternative to balanced trees for ordered data
Open interactive demo →Consistent Hashing
Which node owns this key, without reshuffling everything?
Open interactive demo →HNSW
What are the nearest vectors to this one?
Open interactive demo →Reservoir Sampling
Pick a uniform random sample from a stream you can only see once
Open interactive demo →