---
title: Skip Lists & Probabilistic Structures
module: Data Structures
moduleNumber: 4
lessonNumber: 9
order: 409
summary: |
  Balanced trees achieve $O(\log n)$ with rotations and invariants; randomization
  gives the same bound far more simply. A skip list is a layered linked list whose
  express lanes are chosen by coin flips, giving expected $O(\log n)$ search and
  insert with no rebalancing. A Bloom filter trades exactness for space: a bit
  array and a few hashes answer set membership with no false negatives and a
  tunable false-positive rate, but cannot delete.
topics: [Probabilistic Structures]
sources:
  - book: CLRS
    ref: "Ch. 11 — Hash Tables / App. C — Probability"
  - book: Skiena
    ref: "§3.x — Randomized Data Structures"
  - book: Erickson
    ref: "Ch. — Randomized Algorithms"
practice:
  - title: 'Design Skiplist'
    slug: design-skiplist
    difficulty: Hard
  - title: 'Insert Delete GetRandom O(1)'
    slug: insert-delete-getrandom-o1
    difficulty: Medium
  - title: 'Design HashSet'
    slug: design-hashset
    difficulty: Easy
  - title: 'Implement Trie (Prefix Tree)'
    slug: implement-trie-prefix-tree
    difficulty: Medium
---

A [balanced search tree](/algorithms/data-structures/balanced-trees) earns its $O(\log n)$ guarantee with machinery:
height invariants, rotations, and fix-up cases you have to get exactly right.
This lesson takes a different route to the same bound: **randomization**. Instead
of _forcing_ balance with invariants, we _expect_ it from coin flips, and the
resulting structures are far simpler to implement. This lesson covers two. The
**skip list** is a sorted dictionary that matches a balanced tree's bounds with
nothing but linked lists and a random number generator. The **Bloom filter**
gives up exactness entirely: it answers set membership in a few bits per element,
accepting a controlled rate of false positives in exchange for tiny space.

## Skip lists: express lanes by coin flip

Start with an ordinary **sorted linked list**. Search is $O(n)$ because you must
walk node by node; there is no way to skip ahead. To speed this up, add **express
lanes**: a sparse second list linking every other node, then a sparser third
linking every fourth, and so on. A search rides the top express lane until it
would overshoot, drops down a level, and repeats. With $\log n$ lanes each twice
as sparse as the one below, a search takes $O(\log n)$ steps — the same idea as a
balanced tree, built from lists.

The catch is keeping those lanes perfectly spaced under insertion and deletion,
which would cost as much as rebalancing a tree. The **skip list** avoids this:
instead of maintaining exact spacing, it assigns each node a random
height by **flipping a coin**.[^skiena-rand] Every new node enters level $1$.
Then flip a fair coin: heads promotes the node into level $2$; another heads
promotes it into level $3$; the tower stops growing at the first tails. A node
therefore reaches level $\ell$ with probability $2^{-(\ell-1)}$: every node sits
in level $1$, about half rise to level $2$, a quarter to level $3$, an eighth to
level $4$. On _average_ the lanes are spaced just like the deterministic version,
but no rebalancing is ever needed.

> **Definition (Skip list).** A skip list is a hierarchy of sorted linked lists
> $L_1 \supseteq L_2 \supseteq \cdots \supseteq L_h$. Every element appears in
> $L_1$; an element in $L_i$ appears in $L_{i+1}$ with probability $\tfrac12$,
> independently. Each level begins with a sentinel head; vertical links connect a
> node's copies across the levels it reaches.

$$
% caption: A skip list over the keys $3, 6, 9, 17, 21, 25$. Level $1$ holds every key; higher
%          levels hold a random subset of the level below. Searching for $17$ rides the top
%          lane from $H$ to $9$; the next key, $21$, would overshoot, so the search drops a
%          level. Level $2$ overshoots at $21$ again, so it drops to level $1$ and steps
%          right to $17$.
\begin{tikzpicture}[
  >=stealth, font=\footnotesize,
  cell/.style={draw, minimum width=8mm, minimum height=6mm, inner sep=1pt},
  head/.style={draw, minimum width=8mm, minimum height=6mm, inner sep=1pt, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9E55}
  % x positions for keys
  \def\xa{1.3}\def\xb{2.6}\def\xc{3.9}\def\xd{5.2}\def\xe{6.5}\def\xf{7.8}
  % --- level 3 (sparsest): head, 9, 21 ---
  \node[head] (h3) at (0,2.4) {$H$};
  \node[cell] (c3) at (\xc,2.4) {$9$};
  \node[cell] (e3) at (\xe,2.4) {$21$};
  \draw[->] (h3) -- (c3); \draw[->] (c3) -- (e3); \draw[->] (e3) -- (8.6,2.4);
  % --- level 2: head, 6, 9, 21 ---
  \node[head] (h2) at (0,1.2) {$H$};
  \node[cell] (b2) at (\xb,1.2) {$6$};
  \node[cell] (c2) at (\xc,1.2) {$9$};
  \node[cell] (e2) at (\xe,1.2) {$21$};
  \draw[->] (h2) -- (b2); \draw[->] (b2) -- (c2); \draw[->] (c2) -- (e2); \draw[->] (e2) -- (8.6,1.2);
  % --- level 1 (full): head, 3, 6, 9, 17, 21, 25 ---
  \node[head] (h1) at (0,0) {$H$};
  \node[cell] (a1) at (\xa,0) {$3$};
  \node[cell] (b1) at (\xb,0) {$6$};
  \node[cell] (c1) at (\xc,0) {$9$};
  \node[cell, fill=green!16, draw=green, thick] (d1) at (\xd,0) {$17$};
  \node[cell] (e1) at (\xe,0) {$21$};
  \node[cell] (f1) at (\xf,0) {$25$};
  \draw[->] (h1) -- (a1); \draw[->] (a1) -- (b1); \draw[->] (b1) -- (c1);
  \draw[->] (c1) -- (d1); \draw[->] (d1) -- (e1); \draw[->] (e1) -- (f1); \draw[->] (f1) -- (8.6,0);
  % --- search path for 17 (blue) ---
  % express-lane hop: a clean shallow arc along the top level, H to 9, pulled
  % back from both node edges, clearly skipping over the gap
  \draw[acc, very thick, ->] (h3.east) ++(1.5mm,1.2mm)
        to[bend left=18] ($(c3.west)+(-1.5mm,1.2mm)$);
  % drop from level 3 to level 2, then to level 1, at key 9
  \draw[acc, very thick, ->] (c3.south) -- (c2.north);
  \draw[acc, very thick, ->] (c2.south) -- (c1.north);
  % advance along level 1 to the target
  \draw[acc, very thick, ->] (c1.east) -- (d1.west);
  % overshoot annotations, in the empty band between lanes
  \node[acc, font=\scriptsize, anchor=west] at (4.25,1.8) {next is 21: drop};
  \node[acc, font=\scriptsize, anchor=west] at (4.25,0.6) {next is 21: drop};
  \node[acc, anchor=west] at (8.9,0) {search $17$};
  \node[green, font=\scriptsize, anchor=north] at (d1.south) {found};
\end{tikzpicture}
$$

**Search.** Begin at the head of the top level. Move right while the next key is
$\le$ the target; when the next key would overshoot, drop down one level and
continue. You reach level $1$ at the target (if present) or its predecessor. Each
rightward step and each drop is $O(1)$.

```algorithm
caption: $\textsc{Search}(L, k)$ — locate key $k$ in skip list $L$
number: 1
$x \gets head(L)$ // top-level sentinel
for $i \gets h$ down to $1$ do // walk levels top to bottom
  while $next_i(x) \ne \text{nil}$ and $key(next_i(x)) \le k$ do
    $x \gets next_i(x)$ // ride this lane right while it stays $\le k$
return $x$ if $key(x) = k$ else not found
```

Trace $\textsc{Search}(L, 17)$ on the list above. Start at $H$ on level $3$. The
next key, $9$, is $\le 17$: advance to $9$. The next key on level $3$ is $21 >
17$: drop to level $2$'s copy of $9$. On level $2$ the next key is again $21 >
17$: drop to level $1$. There the next key is $17 \le 17$: advance, and
$key(x) = 17$: found after two rightward moves and two drops, where the plain
list would have walked four nodes. Searching for an _absent_ key, say $15$,
follows the identical path but stops at $9$ on level $1$ (since $17 > 15$) and
reports not-found. The search lands on the **predecessor** of the missing key —
the node an insertion needs.

### Insert: search, flip, splice

Insertion is a search with bookkeeping, followed by coin flips, followed by
pointer surgery. Three phases:

1. **Search and remember.** Walk the usual search path for the new key $k$, but
   at each level record the last node visited before dropping: the
   **update vector** $update_1, \dots, update_h$. Node $update_i$ is $k$'s
   predecessor on level $i$: the node whose level-$i$ pointer must be redirected
   if the new tower reaches level $i$.
2. **Flip for a height.** Set $\ell \gets 1$ and flip until tails, incrementing
   $\ell$ on each heads.
3. **Splice.** For each level $i = 1, \dots, \ell$: the new node's level-$i$
   pointer takes over $update_i$'s old target, and $update_i$'s level-$i$ pointer
   is redirected to the new node. Two assignments per level. If $\ell$ exceeds
   the current height, the new levels start at the head sentinel.

```algorithm
caption: $\textsc{Insert}(L, k)$ — insert key $k$ with a random height
number: 2
$x \gets head(L)$
for $i \gets h$ down to $1$ do
  while $next_i(x) \ne \text{nil}$ and $key(next_i(x)) < k$ do
    $x \gets next_i(x)$
  $update_i \gets x$ // predecessor of $k$ on level $i$
$\ell \gets 1$
while $\textsc{CoinFlip}() = \text{heads}$ do $\ell \gets \ell + 1$ // geometric height
create node $z$ with key $k$ and height $\ell$
for $i \gets 1$ to $\ell$ do // splice, bottom level up
  $next_i(z) \gets next_i(update_i)$
  $next_i(update_i) \gets z$
```

Run $\textsc{Insert}(L, 14)$ on the running example. The search path is the one
already traced for $17$: on level $3$, advance $H \to 9$, see $21 > 14$, record
$update_3 = 9$, drop; on level $2$, see $21 > 14$, record $update_2 = 9$, drop;
on level $1$, see $17 > 14$, record $update_1 = 9$. The update vector is the
tower of $9$ at every level; the new key falls in the gap between $9$ and $17$.

$$
% caption: Phase one of $\textsc{Insert}(L, 14)$: the search path (blue) overshoots at $21$ on
%          levels $3$ and $2$ and at $17$ on level $1$, so the last node visited on every level
%          is $9$ (filled). The update vector is $update_3 = update_2 = update_1 = 9$; the new
%          node will be spliced into the gap just right of this tower.
\begin{tikzpicture}[
  >=stealth, font=\footnotesize,
  cell/.style={draw, minimum width=8mm, minimum height=6mm, inner sep=1pt},
  upd/.style={draw=acc, thick, fill=acc!12, minimum width=8mm, minimum height=6mm, inner sep=1pt},
  head/.style={draw, minimum width=8mm, minimum height=6mm, inner sep=1pt, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9E55}
  \def\xa{1.3}\def\xb{2.6}\def\xc{3.9}\def\xd{5.2}\def\xe{6.5}\def\xf{7.8}
  % --- level 3: head, 9, 21 ---
  \node[head] (h3) at (0,2.4) {$H$};
  \node[upd] (c3) at (\xc,2.4) {$9$};
  \node[cell] (e3) at (\xe,2.4) {$21$};
  \draw[->] (h3) -- (c3); \draw[->] (c3) -- (e3); \draw[->] (e3) -- (8.6,2.4);
  % --- level 2: head, 6, 9, 21 ---
  \node[head] (h2) at (0,1.2) {$H$};
  \node[cell] (b2) at (\xb,1.2) {$6$};
  \node[upd] (c2) at (\xc,1.2) {$9$};
  \node[cell] (e2) at (\xe,1.2) {$21$};
  \draw[->] (h2) -- (b2); \draw[->] (b2) -- (c2); \draw[->] (c2) -- (e2); \draw[->] (e2) -- (8.6,1.2);
  % --- level 1: full ---
  \node[head] (h1) at (0,0) {$H$};
  \node[cell] (a1) at (\xa,0) {$3$};
  \node[cell] (b1) at (\xb,0) {$6$};
  \node[upd] (c1) at (\xc,0) {$9$};
  \node[cell] (d1) at (\xd,0) {$17$};
  \node[cell] (e1) at (\xe,0) {$21$};
  \node[cell] (f1) at (\xf,0) {$25$};
  \draw[->] (h1) -- (a1); \draw[->] (a1) -- (b1); \draw[->] (b1) -- (c1);
  \draw[->] (c1) -- (d1); \draw[->] (d1) -- (e1); \draw[->] (e1) -- (f1); \draw[->] (f1) -- (8.6,0);
  % --- search path for 14 ---
  \draw[acc, very thick, ->] (h3.east) ++(1.5mm,1.2mm)
        to[bend left=18] ($(c3.west)+(-1.5mm,1.2mm)$);
  \draw[acc, very thick, ->] (c3.south) -- (c2.north);
  \draw[acc, very thick, ->] (c2.south) -- (c1.north);
  \node[acc, font=\scriptsize, anchor=west] at (4.25,1.8) {next is 21: drop};
  \node[acc, font=\scriptsize, anchor=west] at (4.25,0.6) {next is 21: drop};
  \node[acc, anchor=west] at (8.9,0) {insert $14$};
  % where the new node will go
  \node[green, font=\scriptsize] (slot) at (4.55,-1.0) {14 goes here};
  \draw[green, ->] (slot) -- (4.55,-0.35);
\end{tikzpicture}
$$

Suppose the flips come up heads, then tails: the tower stops at
$\ell = 2$, so $14$ joins levels $1$ and $2$ only. The splice is four pointer
assignments. On level $1$: $14$'s pointer takes $9$'s old target $17$, and $9$
now points to $14$. On level $2$: $14$'s pointer takes the level-$2$ copy of
$9$'s old target $21$, and that copy now points to $14$. Level $3$ is untouched
because the tower never reached it. Nothing else in the list moves.

$$
% caption: Phase three of $\textsc{Insert}(L, 14)$: the coin came up heads, then tails, so the
%          new tower (green) has height $2$. On each of levels $1$ and $2$, $14$ takes over its
%          predecessor's old pointer and the predecessor points to $14$ — four assignments in
%          all. Level $3$ is untouched; no other node moves.
\begin{tikzpicture}[
  >=stealth, font=\footnotesize,
  cell/.style={draw, minimum width=8mm, minimum height=6mm, inner sep=1pt},
  new/.style={draw=green, thick, fill=green!16, minimum width=8mm, minimum height=6mm, inner sep=1pt},
  head/.style={draw, minimum width=8mm, minimum height=6mm, inner sep=1pt, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9E55}
  \def\xa{1.2}\def\xb{2.4}\def\xc{3.6}\def\xn{4.9}\def\xd{6.2}\def\xe{7.4}\def\xf{8.6}
  % --- level 3: head, 9, 21 (untouched) ---
  \node[head] (h3) at (0,2.4) {$H$};
  \node[cell] (c3) at (\xc,2.4) {$9$};
  \node[cell] (e3) at (\xe,2.4) {$21$};
  \draw[->] (h3) -- (c3); \draw[->] (c3) -- (e3); \draw[->] (e3) -- (9.4,2.4);
  % --- level 2: head, 6, 9, NEW 14, 21 ---
  \node[head] (h2) at (0,1.2) {$H$};
  \node[cell] (b2) at (\xb,1.2) {$6$};
  \node[cell] (c2) at (\xc,1.2) {$9$};
  \node[new] (n2) at (\xn,1.2) {$14$};
  \node[cell] (e2) at (\xe,1.2) {$21$};
  \draw[->] (h2) -- (b2); \draw[->] (b2) -- (c2);
  \draw[green, thick, ->] (c2) -- (n2);
  \draw[green, thick, ->] (n2) -- (e2);
  \draw[->] (e2) -- (9.4,1.2);
  % --- level 1: full list with NEW 14 ---
  \node[head] (h1) at (0,0) {$H$};
  \node[cell] (a1) at (\xa,0) {$3$};
  \node[cell] (b1) at (\xb,0) {$6$};
  \node[cell] (c1) at (\xc,0) {$9$};
  \node[new] (n1) at (\xn,0) {$14$};
  \node[cell] (d1) at (\xd,0) {$17$};
  \node[cell] (e1) at (\xe,0) {$21$};
  \node[cell] (f1) at (\xf,0) {$25$};
  \draw[->] (h1) -- (a1); \draw[->] (a1) -- (b1); \draw[->] (b1) -- (c1);
  \draw[green, thick, ->] (c1) -- (n1);
  \draw[green, thick, ->] (n1) -- (d1);
  \draw[->] (d1) -- (e1); \draw[->] (e1) -- (f1); \draw[->] (f1) -- (9.4,0);
  % vertical link of the new tower
  \draw[green, thick] (n2.south) -- (n1.north);
  % coin-flip annotation above the new tower
  \node[green, font=\scriptsize, anchor=south] at (\xn,3.0) {coin: heads, then tails};
\end{tikzpicture}
$$

**Delete** is the mirror image, with no coins at all. Search for the key with
the same bookkeeping, so $update_i$ is the node _before_ the victim on each
level; then, for every level $i$ the victim occupies, redirect
$next_i(update_i)$ past it to the victim's own level-$i$ successor. Deleting
$14$ from the list above reverses the four assignments of the insert and
restores the original picture exactly. Neither operation rebalances anything;
the random heights keep the structure well-spaced _in expectation_, whatever
the order of insertions and deletions.

### Heights are geometric

The height assigned to a node is $1$ plus the number of consecutive heads, so

$$
\Pr[\text{height} = \ell] = 2^{-\ell},
\qquad
\Pr[\text{height} \ge \ell] = 2^{-(\ell-1)} :
$$

a **geometric distribution**. Two consequences follow immediately. First,
**space**: the number of pointers a node carries equals its height, and

$$
\mathbb{E}[\text{height}]
  = \sum_{\ell \ge 1} \Pr[\text{height} \ge \ell]
  = \sum_{\ell \ge 1} 2^{-(\ell-1)}
  = 1 + \tfrac12 + \tfrac14 + \cdots
  = 2,
$$

so a skip list stores about $2n$ pointers in expectation, the same order as
the $2n$ child pointers of a binary tree. The express lanes cost only one extra
pointer per node on average.

$$
% caption: Sixteen towers with the ideal geometric profile: every node reaches level $1$,
%          half reach level $2$, a quarter level $3$, and so on — each promotion survives a
%          fresh coin flip with probability $\tfrac12$. The expected tower height, and so the
%          expected number of pointers per node, is exactly $2$.
\begin{tikzpicture}[font=\scriptsize, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % dashed level guides first, so towers draw over them
  \draw[black, dashed] (0.1,0.42) -- (9.1,0.42);
  \draw[black, dashed] (0.1,0.84) -- (9.1,0.84);
  \draw[black, dashed] (0.1,1.26) -- (9.1,1.26);
  \draw[black, dashed] (0.1,1.68) -- (9.1,1.68);
  \draw[black, dashed] (0.1,2.10) -- (9.1,2.10);
  % 16 towers; height of tower i is 1 + (trailing zeros of i)
  \foreach \h [count=\i from 1] in {1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5} {
    \draw[fill=acc!10, draw=acc] (\i*0.55-0.18,0) rectangle (\i*0.55+0.18,\h*0.42);
  }
  \draw[black] (0.1,0) -- (9.1,0);
  % level labels at the right, clear of the towers
  \node[black, anchor=west] at (9.3,0.21) {level 1: n};
  \node[black, anchor=west] at (9.3,0.63) {level 2: n/2};
  \node[black, anchor=west] at (9.3,1.05) {level 3: n/4};
  \node[black, anchor=west] at (9.3,1.47) {level 4: n/8};
  \node[black, anchor=west] at (9.3,1.89) {level 5: n/16};
\end{tikzpicture}
$$

Second, **height of the whole list**, which is the maximum of $n$ independent
geometrics. That maximum concentrates tightly around $\log_2 n$, and the next
two results make the guarantee precise.

### Why the expected height and search cost are $O(\log n)$

The whole guarantee rests on two facts about the coin flips.

> **Lemma.** The expected number of levels is $O(\log n)$, and with high
> probability the height is $O(\log n)$.

> **Proof.** A given element reaches level $\ell$ with probability
> $2^{-(\ell-1)}$, so the expected number of elements at level $\ell$ is
> $n \cdot 2^{-(\ell-1)}$. By a union bound, the probability that _any_ element
> reaches level $\ell$ is at most $n \cdot 2^{-(\ell-1)}$, which drops below $1$
> once $\ell > 1 + \log_2 n$. Sharper: for any $c \ge 1$,
> $$
> \Pr[\text{height} > c\log_2 n + 1] \;\le\; n \cdot 2^{-c \log_2 n} \;=\; n^{1-c},
> $$
> polynomially small: the height exceeds $3\log_2 n$ with probability at most
> $1/n^2$. The expected height is
> $\sum_{\ell \ge 1} \Pr[\text{some element at level } \ell] \le
> \sum_{\ell} \min\parens{1,\, n\,2^{-(\ell-1)}}
> \le (1 + \log_2 n) + \sum_{j \ge 1} 2^{-j} = \log_2 n + 2 = O(\log n)$. $\qed$

> **Theorem.** A search visits $O(\log n)$ nodes in expectation.

> **Proof sketch.** Trace the search path _backwards_ from the target, up and to
> the left. Standing at any node on the path, ask: does this node's tower
> continue above the current level? If **yes**, the forward search must have
> arrived here by dropping down, so the backward step goes _up_. If **no**, the
> forward search arrived along the current level, so the backward step goes
> _left_. Whether the tower continues is decided by a coin flip that the
> backward walk has not yet examined (the geometric height is memoryless), so
> each backward step goes up with probability $\tfrac12$, independently. The
> walk ends when it has climbed to the top level, which is at height
> $O(\log n)$ with high probability by the lemma. Reaching height $c\log_2 n$
> therefore needs $c\log_2 n$ successes in a sequence of fair coin flips: the
> total number of steps is a negative-binomial variable with expectation
> $2c\log_2 n$. Adding the $O(\log n)$ expected nodes on the top level, the
> whole path has $O(\log n)$ expected length; a Chernoff bound tightens
> this to $O(\log n)$ with high probability. $\qed$

So **search, insert, and delete are all expected $O(\log n)$**, matching a
balanced tree — but the code is a few dozen lines with no rotation cases, and the
bound holds _in expectation over the random heights_, independent of the input
order.[^erickson-rand] The result is a balanced-tree guarantee from a coin and a linked
list.[^clrs-prob] Skip lists also parallelize and support concurrent updates more gracefully
than rotation-based trees, which is why several production key-value stores use
them.

::impl{algo="skip_list"}

## Bloom filters: membership in a handful of bits

A skip list still stores every key. Sometimes that is too expensive: with a
billion URLs, the only question may be whether a given URL has been seen before,
and storing the URLs themselves is out of the question. A **Bloom filter**
answers that membership question in a tiny, fixed amount of space, by giving up
the ability to answer it _exactly_.

The structure is a bit array $B[0\dots m-1]$, initially all $0$, plus $k$
independent hash functions $h_1, \dots, h_k$, each mapping a key to a position in
$[0, m)$.

- **Insert $x$:** set the $k$ bits $B[h_1(x)], \dots, B[h_k(x)]$ to $1$.
- **Query $x$:** report _present_ only if **all** $k$ bits
  $B[h_1(x)], \dots, B[h_k(x)]$ are $1$; otherwise report _absent_.

$$
% caption: A Bloom filter with $k = 3$ hashes over a $10$-bit array. Inserting $x$ sets the
%          three bits $h_1(x) = 1$, $h_2(x) = 4$, $h_3(x) = 9$. Querying $y$ probes bits $3$,
%          $4$, $6$ and finds two of them still $0$, so $y$ is definitely absent; a query whose
%          three bits all happen to be $1$ would report present, possibly a false positive.
\begin{tikzpicture}[
  >=stealth, font=\footnotesize,
  bit/.style={draw, minimum width=6.5mm, minimum height=6.5mm, inner sep=0}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9E55}
  % bit array: only x's bits 1, 4, 9 are set
  \foreach \v [count=\i from 0] in {0,1,0,0,1,0,0,0,0,1} {
    \ifnum\v=1
      \node[bit, fill=acc!15] (b\i) at (\i*0.7,0) {$1$};
    \else
      \node[bit] (b\i) at (\i*0.7,0) {$0$};
    \fi
  }
  % insert x -> bits 1, 4, 9 (set, blue)
  \node[acc] (x) at (1.4,2.0) {insert $x$};
  \draw[acc, ->] (x) -- (b1.north);
  \draw[acc, ->] (x) -- (b4.north);
  \draw[acc, ->] (x) -- (b9.north);
  % query y -> bits 3, 4, 6; bits 3 and 6 are 0 -> absent (green)
  \node[green] (y) at (4.55,-2.0) {query $y$: two bits are $0$, so absent};
  \draw[green, ->] (y) -- (b3.south);
  \draw[green, ->] (y) -- (b4.south);
  \draw[green, ->] (y) -- (b6.south);
\end{tikzpicture}
$$

The two answers are not symmetric. If even one of $x$'s $k$ bits is $0$, then $x$
was never inserted (inserting would have set it), so a _"absent"_ answer is
**always correct** — a Bloom filter has **no false negatives**. But a _"present"_
answer can be wrong: the $k$ bits for some never-inserted $y$ might all have been
set to $1$ by _other_ elements' insertions, a **false positive**.

This is precisely the [soundness / completeness](/algorithms/foundations/what-is-an-algorithm) framing from the foundations.
Read as a test for _"$x$ is **not** in the set,"_ the filter is **sound**:
whenever it says "absent" it is right. Read as a test for _"$x$ **is** in the
set,"_ it is **incomplete**: "present" may be a false alarm. A Bloom filter is a
_definitely-not-present_ oracle: a negative answer is a proof, a positive answer
is only a strong hint.

### The false-positive rate

How often is "present" wrong? Inserting $n$ elements evaluates $kn$ hashes, each
choosing a position uniformly in $[0, m)$. A fixed bit survives as $0$ only if
every one of those $kn$ throws misses it:

$$
\Pr[\text{bit still } 0]
  = \parens{1 - \frac{1}{m}}^{kn}
  = e^{\,kn \ln(1 - 1/m)}
  \approx e^{-kn/m},
$$

using $\ln(1 - 1/m) \approx -1/m$ for large $m$. So after the insertions a
fraction $\rho = 1 - e^{-kn/m}$ of the array is set. A false positive needs
_all $k$_ of a query's probes to land on set bits, and treating the probes as
independent hits on that fraction gives the false-positive probability

$$
p \;\approx\; \rho^k \;=\; \parens{1 - e^{-kn/m}}^{k}.
$$

Two effects compete in the formula. More hashes make each _query_ harder to
pass by accident (the exponent $k$ grows), but they also _fill the array
faster_ (the base $\rho$ grows). Somewhere in between is a best $k$.

> **Theorem.** For a fixed array size $m$ and element count $n$, the
> false-positive rate $p$ is minimized at $k = (m/n)\ln 2$, giving
> $p \approx (1/2)^k = (0.6185)^{m/n}$.

> **Proof sketch.** Treat $k$ as continuous, write $u = e^{-kn/m}$, so
> $k = -(m/n) \ln u$ and
> $$
> \ln p \;=\; k \ln(1 - u) \;=\; -\frac{m}{n}\,\ln u \,\ln(1 - u).
> $$
> The product $\ln u \ln(1-u)$ is symmetric under $u \leftrightarrow 1-u$ and,
> by calculus, has its maximum on $(0,1)$ at the symmetric point $u = \tfrac12$,
> which minimizes $\ln p$. So the optimum leaves each bit set with probability
> exactly $\tfrac12$ (a maximally informative, maximum-entropy array), and
> $e^{-kn/m} = \tfrac12$ solves to $k = (m/n)\ln 2$. Substituting back,
> $p \approx (1/2)^k = 2^{-(m/n)\ln 2} = (0.6185)^{m/n}$. $\qed$

Concrete numbers. Suppose you track $n = 10^6$ URLs with $m = 10^7$ bits, a
$1.25$ MB array and $m/n = 10$ bits per element. The optimum is $k = 10 \ln 2
\approx 6.93$; take $k = 7$. Then $kn/m = 0.7$, each bit ends up set with
probability $\rho = 1 - e^{-0.7} \approx 0.503$, almost exactly half as the
theorem predicts, and

$$
p \;\approx\; (0.503)^7 \;\approx\; 0.008,
$$

about $8$ false alarms per $1000$ queries of absent keys. Doubling the budget to
$20$ bits per element drives the rate to $(0.6185)^{20} \approx 7 \times
10^{-5}$, under one in ten thousand. A hash set storing the URLs themselves
would need hundreds of bits per element before a single pointer is counted.

$$
% caption: False-positive rate as $k$ varies, at a fixed budget of $m/n = 10$ bits per element.
%          One hash fills the array slowly but lets queries pass with a single lucky bit:
%          $p \approx 9.5\%$. More hashes demand more coincidences per query yet set more bits;
%          the two effects balance at $k = (m/n)\ln 2 \approx 7$, where $p \approx 0.82\%$. The
%          bowl is shallow: $k$ from $5$ to $9$ is within a whisker of optimal.
\begin{tikzpicture}[font=\scriptsize, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % axes
  \draw[->, black] (0.2,0) -- (11.0,0);
  \draw[->, black] (0.2,0) -- (0.2,4.4);
  % bars: height = 40 p(k) for k = 1..10
  \draw[fill=acc!12, draw=acc] (0.7,0) rectangle (1.3,3.81);
  \draw[fill=acc!12, draw=acc] (1.7,0) rectangle (2.3,1.32);
  \draw[fill=acc!12, draw=acc] (2.7,0) rectangle (3.3,0.70);
  \draw[fill=acc!12, draw=acc] (3.7,0) rectangle (4.3,0.47);
  \draw[fill=acc!12, draw=acc] (4.7,0) rectangle (5.3,0.38);
  \draw[fill=acc!12, draw=acc] (5.7,0) rectangle (6.3,0.34);
  \draw[fill=acc!35, draw=acc] (6.7,0) rectangle (7.3,0.33);
  \draw[fill=acc!12, draw=acc] (7.7,0) rectangle (8.3,0.34);
  \draw[fill=acc!12, draw=acc] (8.7,0) rectangle (9.3,0.37);
  \draw[fill=acc!12, draw=acc] (9.7,0) rectangle (10.3,0.41);
  % x tick labels
  \foreach \k in {1,2,3,4,5,6,7,8,9,10} {
    \node[black, anchor=north] at (\k,-0.1) {\k};
  }
  \node[black, anchor=north] at (5.5,-0.6) {\texttt{number of hashes k}};
  % callouts
  \node[acc, anchor=south] at (1,3.9) {near 10\%};
  \node[acc, anchor=south] at (7,0.5) {under 1\%};
  \node[black, anchor=south, rotate=90] at (-0.15,1.2) {\texttt{false-positive rate}};
\end{tikzpicture}
$$

$$
% caption: A false positive. Earlier insertions have set bits $1, 4, 6, 9$ (shaded). A query
%          for $z$ — never inserted — happens to hash to bits $1, 4, 9$, all of which are
%          already $1$, so the filter wrongly reports present. A genuine absent answer would
%          have needed at least one of those bits to be $0$.
\begin{tikzpicture}[
  >=stealth, font=\footnotesize,
  bit/.style={draw, minimum width=6.5mm, minimum height=6.5mm, inner sep=0}]
  \definecolor{acc}{HTML}{2348F2}
  % bit array with bits 1,4,6,9 set by earlier inserts
  \foreach \v [count=\i from 0] in {0,1,0,0,1,0,1,0,0,1} {
    \ifnum\v=1
      \node[bit, fill=acc!15] (b\i) at (\i*0.7,0) {$1$};
    \else
      \node[bit] (b\i) at (\i*0.7,0) {$0$};
    \fi
  }
  \node[black, anchor=west, font=\scriptsize] at (6.6,0) {bits set by earlier inserts};
  % query z hashes to 1, 4, 9 -- all already 1 -> false positive
  \node[acc] (z) at (3.15,-2.0) {query $z$: all three bits are $1$, reported present};
  \draw[acc, ->] (z) -- (b1.south);
  \draw[acc, ->] (z) -- (b4.south);
  \draw[acc, ->] (z) -- (b9.south);
\end{tikzpicture}
$$

The practical reading: the rate falls **exponentially in the bits-per-element**
$m/n$. About $9.6$ bits per element with $k = 7$ hashes gives a $1\%$
false-positive rate; $14.4$ bits and $k = 10$ gives $0.1\%$ — orders of magnitude
less than the dozens of _bytes_ per element a hash set storing the keys would
need.

> **Remark (no deletion).** You cannot delete from a standard Bloom filter.
> Clearing a key's $k$ bits would also clear bits _shared_ with other inserted
> elements, introducing false negatives and breaking soundness. Variants —
> **counting Bloom filters** (replace each bit with a small counter) — restore
> deletion at a few times the space.

Bloom filters are everywhere a cheap, conservative pre-check pays off: a database
skips a disk lookup when the filter says a key is absent; a CDN avoids caching a
one-hit URL; a spell-checker rejects obvious non-words. In each case the filter's
**no-false-negative** guarantee is what makes it safe — a "definitely absent"
answer can be trusted to short-circuit the expensive exact check, and a "maybe
present" answer simply falls through to that check.

::impl{algo="bloom_filter"}

## Where the coin flips run

Both structures are core pieces of widely-used systems, and each has refined
descendants.

**Skip lists in production.** Redis stores its **sorted sets** (`ZSET`) as a skip
list paired with a hash table, precisely because a skip list gives $O(\log n)$
ordered operations _and_ range queries with far simpler concurrent code than a
balanced tree: there are no rotations to coordinate, so lock-free and
fine-grained-locking skip lists are practical, which is why concurrent maps
(Java's `ConcurrentSkipListMap`) favor them. The MemSQL/LevelDB-style in-memory
**memtable** is often a skip list for the same reason.

**Bloom filters and the LSM tree.** The dominant use of Bloom filters today is
inside **log-structured merge trees** (LevelDB, RocksDB, Cassandra): each on-disk
table carries a Bloom filter, so a read that would otherwise probe many tables
skips the ones whose filter says "absent," turning most negative lookups into a
few in-memory bit tests. This is the "skip a disk lookup" case at industrial
scale.

**Filters past Bloom.** The no-deletion limitation and Bloom's cache-unfriendly
$k$ scattered probes drove better designs. A **counting Bloom filter** restores
deletion; a **cuckoo filter** (Fan et al., 2014) stores small fingerprints in a
cuckoo-hash table, supporting deletion _and_ better locality at the same false-
positive rate; a **quotient filter** is a cache-friendly, mergeable alternative.
And for the related question "how many _distinct_ items," the same probabilistic
spirit gives HyperLogLog, taken up in
[Data-Stream Algorithms](/algorithms/data-structures/data-stream-algorithms).[^btb-skip]

## Takeaways

- **Randomization** reaches a balanced tree's $O(\log n)$ bounds without
  invariants or rotations — _expected_ balance from coin flips, far simpler to
  implement.
- A **skip list** layers sorted linked lists; each element rises to the next level
  with probability $\tfrac12$. Search rides express lanes top-down, dropping a
  level on overshoot.
- **Insert** is a search that records the **update vector** (the predecessor on
  each level), a run of coin flips for the height, then two pointer assignments
  per level. Delete reverses the splice. No rebalancing, ever.
- Tower heights are **geometric**: expected height $2$, so about $2n$ pointers in
  total: one extra pointer per node over a plain list.
- The height is $O(\log n)$ **with high probability**, and search/insert/delete are
  all **expected $O(\log n)$**, independent of input order.
- A **Bloom filter** is a bit array plus $k$ hashes. Insert sets $k$ bits; query
  reports _present_ only if all $k$ are set.
- It has **no false negatives** — a _sound_ "definitely-not-present" test —
  but is _incomplete_ as a presence test, with false-positive rate
  $p \approx (1 - e^{-kn/m})^k$, minimized at $k = (m/n)\ln 2$.
- The rate drops **exponentially in bits-per-element**; the cost is that you
  **cannot delete** (without a counting variant).

[^skiena-rand]: **Skiena**, §3.x — Randomized Data Structures: skip lists as a coin-flip alternative to balanced trees with expected $O(\log n)$ operations.
[^clrs-prob]: **CLRS**, App. C — Counting and Probability: the union-bound and geometric-variable arguments behind the expected $O(\log n)$ height and search cost.
[^erickson-rand]: **Erickson**, Ch. — Randomized Algorithms: analysis of randomized structures, including expectation over internal coin flips rather than over inputs.
[^btb-skip]: Pugh, "Skip lists: a probabilistic alternative to balanced trees" (1990); Fan, Andersen, Kaminsky & Mitzenmacher, "Cuckoo filter: practically better than Bloom" (2014); the LSM-tree Bloom-filter pattern is standard in LevelDB/RocksDB.