This site's Probabilistic category holds thirteen 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 five completely unrelated problems, three of which this guide compares head to head below and two of which stand apart, from the other three and from each other. 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 and SimHash are a third head-to-head pair: unlike every other entry here, neither answers a question about one item at all — both estimate similarity between items and bucket similar ones together, LSH's own opening paragraph draws this exact line against every other entry in the category, and SimHash's own opening paragraph draws the same line against LSH specifically. The difference is what "similar" means and what shape the input takes — compared head to head below. Alias Method and Fisher–Yates Shuffle are the odd ones out, together: every entry above either builds up state from a stream one item at a time, replaces a rotation-based tree, or compares two items to each other — these two instead each take a whole, already-known collection up front and answer one question about it in a single pass, no stream, no hashing, no pairwise comparison. They don't compete with the three families above, or with each other — compared head to head below, in the one respect that's actually worth comparing: what kind of one-shot question each answers. Three genuinely different head-to-head needs, plus two one-shot answers that stand apart from everything else and from each other — not one flat "which one do I use."
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. Need to compare two items to each other, or find which pairs among many are even worth comparing, instead of asking a question about any one item alone? Go to Locality-Sensitive Hashing vs. SimHash below. Need a single answer about a whole collection that's already fully in memory — not a stream, not a comparison between items? Go to Alias Method vs. Fisher–Yates Shuffle below. Nothing about one question's answer affects the others — a system can easily need any combination of the four, for entirely separate parts of itself, and picking one says nothing about which fits the others.
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.
Both entries turn a comparison that would otherwise mean touching every element of two large inputs into a fixed-size signature comparison — a handful of numbers checked directly instead of a full item scanned twice, plus a way to prune which pairs are even worth checking before doing that. The difference is what "an item" means, and what "similar" means for it.
Items are sets — do two things share a lot of the same discrete elements (words,
shingles, k-mers), with no notion of "how much" of any one element? Locality-Sensitive Hashing's MinHash +
banding: signs each set down to k minimum-hash values, estimates Jaccard similarity
(|A∩B|/|A∪B|) from how many agree, and bands the signatures to generate only the
candidate pairs worth checking further. Measured on its own eight-document worked example, the
balanced banding scheme found 80% of real near-duplicate pairs at a 0.6% false-positive rate.
Items are weighted vectors — do two things share a lot of the same weighted features (term frequencies, tag weights, purchase counts), where how much each feature is emphasized matters as much as whether it's present at all? SimHash: projects each weighted vector onto b random hyperplanes (one sign bit per hyperplane) into a single b-bit fingerprint, estimates cosine similarity from the two fingerprints' Hamming distance, and uses the same "only compare candidates" idea LSH's banding does, keyed off exact-match blocks of the fingerprint instead of hashed bands. A set is a special case of a weighted vector (every present element weighted 1, every absent one weighted 0) — SimHash would technically still run on LSH's own eight sentences, but throws away exactly the information (how many times a word repeats, not just whether it appears) that's the whole reason to reach for it over LSH once real weights are in play.
Neither is a strict upgrade of the other. A codebase compared by shared n-grams has no weight information to lose in the first place, and Jaccard is the more natural, standard measure for it — reach for SimHash there and it's pure overhead for no accuracy gain. A corpus of term-frequency-weighted documents has real weight information a set-based comparison would throw away, exactly the case SimHash's own page measures a real accuracy cost for ignoring. Pick by what the input actually is, not by which one sounds more sophisticated.
Both entries here start from the same place — a whole collection already sitting in memory, no stream, no per-pair comparison — and both answer their question in a single pass with no build step that depends on which draw or permutation comes out. That's the entire resemblance; the questions themselves don't overlap at all.
Need to draw repeatedly from a fixed, arbitrarily-weighted distribution — the same
collection, sampled with replacement, over and over? Alias Method. One O(n) build turns any
set of weights into two flat arrays, then every draw after that is O(1): one uniform
index, one coin flip, done — forever, no matter how skewed the weights or how many draws are
needed.
Need every item exactly once, in an order that's fair and never repeats a draw?
Fisher–Yates Shuffle. A single
O(n) pass with no build step at all produces one permutation, chosen uniformly from
all n! possibilities — not a sequence of independent draws from the same distribution,
but a single rearrangement of the one collection itself.
A system that needs both — say, dealing a shuffled deck (Fisher–Yates) and then weighting which of several players acts first by a handicap (Alias Method) — reaches for each independently; one producing the other's input or vice versa isn't a pattern either page's own measurements or worked examples rely on.
| 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 |