This site's Probabilistic category holds eleven entries, and unlike most categories on this site they don't share one contract with different trade-offs layered on — they share one trick (spend real randomness to buy a guarantee that would otherwise cost a deterministic rule to enforce) applied to three completely unrelated problems, two of which this guide compares head to head below and one of which stands alone. Skip List and Treap both replace a rotation-based balanced tree — same job AVL and red-black trees do, treap's own opening paragraph names skip list directly as "this page's sibling in Probabilistic" using the identical randomization-does-the-work idea via a different mechanism. Cuckoo Filter, XOR Filter, Count-Min Sketch, Count Sketch, and HyperLogLog are a different animal entirely: fixed, tiny memory that answers one narrow question about an unbounded stream approximately, instead of remembering everything and answering exactly. That second group is actually six-strong, not five — the Bloom Filter (filed under Hash-Based on this site, since it's built from a plain bit array and hash functions rather than anything cuckoo-hashed) is the sixth member, and HyperLogLog's own page says so explicitly: "the Bloom filter answers 'have I seen this?' and the Count-Min Sketch answers 'roughly how many times?' — HyperLogLog answers a third narrow question in the same spirit." Reservoir Sampling belongs in this same stream-summarization family by shape (fixed memory, one pass, unbounded length) even though, as its own closing section on the tree below explains, it answers a genuinely different kind of question than the other three. Morris Counter is the family's eighth and most primitive member — it doesn't answer a question about any item at all, only "how many events, total," and is the only one of the eight that needs no hash function, since it never has to tell one item apart from another. Locality-Sensitive Hashing is a third, standalone problem: unlike every other entry here, it doesn't answer a question about one item at all — it estimates similarity between items and buckets similar ones together, its own opening paragraph draws this exact line against every other entry in the category. Alias Method is a fourth, equally standalone problem, and the odd one out in the opposite direction: every entry above either builds up state from a stream one item at a time, or replaces a rotation-based tree — Alias Method instead takes a whole, already-known distribution up front and answers "draw from this, repeatedly, in O(1)" with no stream, no hashing, and no per-item question about identity at all. Neither of these two competes with the balanced-tree pair or the stream-summarization family below, and neither is compared further in this guide; see each one's own page for what it does instead. Two unrelated needs plus two standalone ones, not one flat "which one do I use" — treat the first two as separate questions and skip LSH or Alias Method if neither describes what's needed.
Need a sorted, searchable structure — insert, search, delete, all balanced without enforcing an explicit shape rule? Go to Skip List vs. Treap below. Need to answer one narrow question about a stream too large (or too open-ended) to store in full, using memory that stays flat no matter how long the stream runs? Go to the stream-summarization family below. Nothing about one question's answer affects the other — a system can easily need both, for entirely separate parts of itself, and picking one says nothing about which fits the other job.
Both entries reach O(log n) search/insert/delete expected, not guaranteed
— real, computed worst cases remain possible on unlucky randomness, the same honest trade both
pages' own Pitfalls sections make rather than hide. The difference is what each buys beyond that
shared baseline.
Need split/merge over positions, or a Cartesian-tree construction? Treap, decisively — its own "Where treaps show up" section
names two capabilities Skip List's own linked-layer shape has no equivalent for: an
implicit treap (drop the search key, let in-order position be the key) splits
into "everything before index k" / "everything from k on" and merges two treaps back together, both
O(log n), turning a plain array into a structure supporting insert-in-the-middle,
delete-a-range, and reverse-a-range — none of which a plain array offers. Separately, building a
treap-shaped tree with priority set to the array's own values (not random) produces a Cartesian
tree, the standard O(n)-preprocessing/O(1)-query answer to range-minimum
queries by reduction to Lowest Common Ancestor.
Need genuinely lock-free concurrent writes, or want to avoid rotation code and parent
pointers entirely? Skip List — not a claim
this guide is making up, it's the reason three real systems reach for it specifically: Redis's
ZSET, LevelDB and RocksDB's default memtable, and Java's
ConcurrentSkipListMap all cite concurrent lock-free insertion as easier to get right
on a skip list than on a rotating tree, since no write ever needs to briefly lock a wide swath of
the structure the way a rotation touching multiple nodes at once would. A skip list's insert and
delete only ever attach or unsplice a node's own forward pointers — no parent pointer needed
anywhere, unlike a treap's rotate-and-reparent dance.
Neither of the above, just "a simpler balanced structure than AVL or red-black"?
Either works, and the honest answer is the trade is close. Skip list carries roughly twice
the total pointers of a plain linked list holding the same elements (measured directly: 2,000.1
total forward pointers at n = 1,000, 20,000.2 at n = 10,000, both within
a hair of the predicted 2n) in exchange for zero rotation logic. Treap needs a parent
pointer plus a priority field per node — the same pointer shape as a red-black tree, just a float
standing in for a color bit — but its insert/delete are each a single straightforward
rotate-while-comparing-priorities loop, with none of AVL or red-black's rotation-case taxonomy to
get right. Measured balance quality for both, against log₂(n) directly:
| n | Skip List: avg levels in use | Treap: avg height ÷ log₂(n) | log₂(n) |
|---|---|---|---|
| 10 | — | 1.69 (3,000 trials) | 3.32 |
| 100 | 7.96 (3,000 trials) | 2.00 (1,000 trials) | 6.64 |
| 1,000 | 11.29 (1,000 trials) | 2.19 (200 trials) | 9.97 |
| 10,000 | 14.94 (200 trials) | 2.34 (30 trials) | 13.29 |
Both gaps stay small and grow slowly rather than blowing up, consistent with each page's own
O(log n) claim — a skip list's level count tracks close to log₂(n)
directly, a treap's height climbs toward a known constant (a random BST's expected height has a
leading constant near 4.311 in natural-log terms) rather than sitting flat at small n. Neither
number is "better" than the other in any comparable unit; both are here to show the claim is
measured, not assumed, the same standing discipline this site applies to every entry.
All eight structures below share the same shape — one hash (or one random draw) per item or event, a fixed amount of memory that never grows no matter how long the stream runs, and no way to enumerate or recover what was actually seen. What splits them is which single question about that stream the fixed memory is spent answering. Redis's own RedisBloom module ships three of these eight together (Bloom Filter, Count-Min Sketch, HyperLogLog) specifically because they answer three different approximate questions with the same fixed-memory trade, not because any one of them subsumes the others.
"Have I seen this exact item before?" Bloom Filter if delete is never needed — insertion
always succeeds, no matter how full the filter gets (the false-positive rate just climbs), and
it's the simplest of the five, and — among the structures here that support inserting into a
running stream — typically the most space-efficient at ordinary false-positive targets. Cuckoo Filter if delete is a real requirement — its
fingerprint-per-slot design (the same displacement idea as cuckoo hashing) lets one entry be found and
cleared without disturbing anyone else's, something a plain Bloom filter's shared-bit design can't
support without a whole separate counting variant. The real cost: unlike a Bloom filter, a Cuckoo
filter's add can fail outright once displacement runs out of kicks — measured at 15
of 20 successes (93.75% of the demo's tiny 16-slot table) in the small worked example, and roughly
99%, 99.8%, and 99.8% fill before failure at bucket sizes 1, 2, and 4 respectively in a
larger-scale check — a real ceiling a caller has to check for and handle, not silent
degradation. XOR Filter if the key set is fully
known up front and never needs to grow one item at a time — trading away incremental insertion
entirely (it's built once, from the whole set, by peeling a 3-hash hypergraph) buys back space
even a size-optimized Bloom Filter can't match: this site's own measurements put it at
~9.84 bits/key at scale for the same ~0.39% false-positive target where the Bloom
Filter's optimal-configuration formula needs ~11.54 bits/item, and queries become three fixed
reads and two XORs with no probing or displacement at all. The trade shows up at build time
instead: peeling can hit a stuck "2-core" and force a full-array retry with fresh hash seeds,
though that was measured to need more than one attempt only rarely (average 1.00-1.13 attempts
across n from 1,000 to 100,000).
"Roughly how many times has this specific item appeared?" Two of these eight
answer a per-item frequency question, trading the same axis against each other. Count-Min Sketch if a hard one-directional bound
matters more than the average case — its own worked example (d=3, w=12): querying a
word added four times reads 5, 6, and 5 across the three independent rows — every row polluted by
something — and the minimum (5) is the tightest safe reading available, guaranteed never to
undercount (estimate(item) ≥ true_count(item), always) and bounded above by
ε·N with confidence 1 − e⁻ᵈ (about 95% at this exact configuration,
measured at 99.43% across 2,000 randomized streams — comfortably inside the theory's own
guarantee). Count Sketch if the estimate needs to
be right on average instead — same d×w grid, but a random sign per row lets colliding
contributions partly cancel instead of only ever stacking, and the query takes a median instead of
a minimum. Measured on the same kind of skewed stream: Count-Min Sketch overestimated 99.4% of
5,000 trials (mean error +4.198), while Count Sketch landed above the truth 37.3% of the time,
below it 37.7%, and exact the rest (mean error 0.003) — at the cost of losing the "never below the
truth" guarantee entirely; Count Sketch can even read a small negative number for an item never
added.
"Roughly how many distinct items total, not how many times any one of them?" HyperLogLog, the only one of these six answering a
cardinality question rather than a per-item one — it can't say whether any specific item was seen
at all, only the size of the whole distinct set. Its own worked example: 8 distinct animals fed
into m = 16 registers give a raw estimate of ≈16.03 (nearly double, the small-range
regime this configuration sits in) corrected to ≈9.21 by linear counting — still approximate, but
much closer, exactly the fix the page's own Pitfalls insists is not optional at this scale. Error
scales as 1.04/√m: about 26% at this demo's m = 16, dropping to 3.3% at
a production-realistic m = 1024 (1KB), under 1% at m = 16384 (16KB) — more
registers trades directly for less noise, with no way to shrink the error after the fact without
starting a fresh sketch, since past hashes are never kept.
"Give me k of the actual items, chosen fairly, not a statistic about them." Reservoir Sampling — the odd one out among
these seven in one specific, important way: it's the only one whose answer is exact, not
approximate. The other six each quantify a real error rate against a true value they're
estimating; reservoir sampling doesn't estimate anything — every item that has ever passed through
the stream ends with a provably exact k/n probability of surviving to the end (proved
by induction on this site's own page, then checked against a 50,000-trial frequency sweep landing
within 0.002 of the theoretical 0.3333 at k=4, n=12). What it trades away isn't
accuracy, it's information about anything other than the k survivors — there's no way to
ask what was discarded, and no membership or frequency answer for anything not currently sitting in
the reservoir.
"Roughly how many events have happened, period — not which ones, not how many distinct
ones." Morris Counter — the only one of
these eight with no item identity in its question at all, and the only one that doesn't hash
anything. Where the other seven each need to place an item somewhere (a bit position, a bucket, a
register, a reservoir slot), a Morris Counter only ever touches one small number: increment it with
probability 1/2^c instead of every time, and read 2^c - 1 back as the
estimate. Proved unbiased by induction on its own page (E[2^c] = n + 1) and checked at
n=100 across 20,000 trials: a single counter's mean landed at 100.38 (matching the true
count) but with a standard deviation of 71.04 — correct on average, wide on any one run,
the same honest trade every other entry here makes, just for the single simplest question in the
family. It's also the oldest idea here by a wide margin — Robert Morris's 1978 paper predates
HyperLogLog by nearly thirty years, and the site's own HyperLogLog page inherits the same "spend a
random draw instead of an exact tally" trick this entry introduced.
| Entry | Balances via | Time | Space | Reach for it when |
|---|---|---|---|---|
| Skip List | independent coin-flipped level per node | O(log n) expected | ~2n pointers (measured) | no rotations/parent pointers wanted, or genuine concurrent lock-free writes needed |
| Treap | one random priority per node, heap-ordered | O(log n) expected | priority + 2 child + 1 parent pointer per node | need split/merge over positions (implicit treap) or a Cartesian-tree/O(1)-RMQ build |
| Entry | Answers | Time | Space | Reach for it when |
|---|---|---|---|---|
| Bloom Filter | "have I seen this?" — no false negatives | O(k) | O(m) bits | membership only, insert must never fail, delete never needed |
| Cuckoo Filter | "have I seen this?" — with real delete | O(1) amortized add, O(1) worst-case query/delete | fingerprint bits per item | delete is required, and a real (checked) insertion-failure ceiling is acceptable |
| XOR Filter | "have I seen this?" — smallest space, no add/delete after build | O(1) query, O(n) build (1.00-1.13 attempts avg, measured) | ~9.84 bits/key (measured, ~0.39% target rate) | the whole key set is known up front and rebuilt wholesale, not grown incrementally |
| Count-Min Sketch | "roughly how many times has X appeared?" | O(d) | O(d·w) counters | per-item frequency, never an undercount, overcount bounded by ε with confidence 1−e⁻ᵈ |
| Count Sketch | "roughly how many times has X appeared?" — unbiased, two-sided error | O(d) | O(d·w) signed counters | per-item frequency, estimate needs to be right on average or sketches get combined/averaged |
| HyperLogLog | "roughly how many distinct items total?" | O(1) | O(m) bytes | cardinality only, error ~1.04/√m, no per-item answer needed at all |
| Reservoir Sampling | "give me k fairly-chosen actual items" | O(n) total, O(1) amortized per item | O(k) | need real surviving items back, with exact (not approximate) fairness |
| Morris Counter | "roughly how many events total?" — no item identity, no hashing | O(1) | O(log log n) bits | a single running count, memory too tight even for an exact O(log n)-bit counter |