Skip Lists & Probabilistic Structures

A balanced search tree 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.¹ 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.

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)$.

Trace $\text{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 $updat{e}_1,\dots ,updat{e}_h$. Node $updat{e}_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 \leftarrow 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 $updat{e}_i$'s old target, and $updat{e}_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.

Run $\text{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 $updat{e}_3=9$, drop; on level $2$, see $21>14$, record $updat{e}_2=9$, drop; on level $1$, see $17>14$, record $updat{e}_1=9$. The update vector is the tower of $9$ at every level; the new key falls in the gap between $9$ and $17$.

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.

Delete is the mirror image, with no coins at all. Search for the key with the same bookkeeping, so $updat{e}_i$ is the node before the victim on each level; then, for every level $i$ the victim occupies, redirect $nex{t}_i(updat{e}_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

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

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.

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.

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.² The result is a balanced-tree guarantee from a coin and a linked list.³ Skip lists also parallelize and support concurrent updates more gracefully than rotation-based trees, which is why several production key-value stores use them.

from collections.abc import Iterator
from random import Random
from typing import Generic, Optional, TypeVar

from comparable import Comparable

Key = TypeVar("Key", bound=Comparable)
Value = TypeVar("Value")

class SkipListNode(Generic[Key, Value]):
  """
    One tower in the skip list: a key, its associated value, and a list of\n
    forward links — one per level the node was promoted to. `forward[i]` is\n
    the next node on level `i + 1`, or None at the end of that lane.\n
    The head sentinel reuses this node with no key and no value.\n
  """

  def __init__(self, key: Optional[Key], value: Optional[Value], height: int) -> None:
    self.key: Optional[Key] = key
    self.value: Optional[Value] = value
    self.forward: list[Optional[SkipListNode[Key, Value]]] = [None for _ in range(height)]

  def __repr__(self) -> str:
    return f"SkipListNode({self.key!r} -> {self.value!r}, h={len(self.forward)})"

class SkipList(Generic[Key, Value]):
  """
    An ordered map from comparable keys to values.\n
    Keys must support `<`; duplicate inserts overwrite the stored value.\n
  """

  def __init__(self, max_height: int = 16, seed: Optional[int] = None) -> None:
    """
      Build an empty skip list. `max_height` caps the tower height (16 levels\n
      comfortably index millions of keys); `seed` pins the coin flips for\n
      reproducible structure in tests.\n
    """
    self._max_height: int = max_height
    self._random: Random = Random(seed)

    # the head sentinel owns one forward link per possible level.
    self._head: SkipListNode[Key, Value] = SkipListNode(None, None, max_height)

    # current number of populated levels and number of stored keys.
    self._height: int = 1
    self._size: int = 0

  def __len__(self) -> int:
    return self._size

  def _random_height(self) -> int:
    """
      Flip a fair coin to choose a new tower's height: start at level 1 and\n
      keep rising while heads come up, capped at `max_height`.\n
    """
    height: int = 1
    while height < self._max_height and self._random.random() < 0.5:
      height += 1
    return height

  def _predecessors(
    self, key: Key
  ) -> list[SkipListNode[Key, Value]]:
    """
      The `update` vector: for each level, the last node whose key is strictly\n
      less than `key`. Splicing and unlinking both happen at these nodes.\n
    """
    update: list[SkipListNode[Key, Value]] = [self._head for _ in range(self._max_height)]
    current: SkipListNode[Key, Value] = self._head

    # walk levels top to bottom, riding each lane right while it stays < key.
    for level in range(self._height - 1, -1, -1):
      next_node = current.forward[level]
      # every non-head node carries a real key (only the head sentinel is None,
      # and `current.forward` never points back at the head).
      while next_node is not None and next_node.key is not None and next_node.key < key:
        current = next_node
        next_node = current.forward[level]
      update[level] = current
    return update

  def search(self, key: Key) -> Optional[Value]:
    """
      The value stored under `key`, or None if `key` is absent.\n
      Expected O(log n) comparisons.\n
    """
    # ride each lane right while it stays < key, then drop a level.
    current: SkipListNode[Key, Value] = self._head
    for level in range(self._height - 1, -1, -1):
      next_node = current.forward[level]
      # only the head sentinel has a None key, and it is never a forward target.
      while next_node is not None and next_node.key is not None and next_node.key < key:
        current = next_node
        next_node = current.forward[level]

    # one step on level 1 lands on the candidate (or its successor).
    candidate = current.forward[0]
    if candidate is not None and candidate.key == key:
      return candidate.value
    return None

  def __contains__(self, key: Key) -> bool:
    return self.search(key) is not None

  def insert(self, key: Key, value: Value) -> None:
    """
      Store `value` under `key`, overwriting any existing entry.\n
      A fresh key gets a random tower height; an existing key keeps its tower\n
      and only updates the value. Expected O(log n).\n
    """
    update: list[SkipListNode[Key, Value]] = self._predecessors(key)

    # if the key already exists it sits right after its level-1 predecessor.
    existing = update[0].forward[0]
    if existing is not None and existing.key == key:
      existing.value = value
      return

    height: int = self._random_height()

    # any new levels start with the head as their predecessor.
    if height > self._height:
      for level in range(self._height, height):
        update[level] = self._head
      self._height = height

    new_node: SkipListNode[Key, Value] = SkipListNode(key, value, height)

    # pointer surgery: splice the tower in at each remembered predecessor.
    for level in range(height):
      new_node.forward[level] = update[level].forward[level]
      update[level].forward[level] = new_node
    self._size += 1

  def delete(self, key: Key) -> bool:
    """
      Remove `key` and its value. Returns False if the key was absent.\n
      Unlinks the tower from every level it occupies. Expected O(log n).\n
    """
    # the target, if present, sits right after its level-1 predecessor.
    update: list[SkipListNode[Key, Value]] = self._predecessors(key)
    target = update[0].forward[0]
    if target is None or target.key != key:
      return False

    # detach the tower wherever a predecessor still points at it.
    for level in range(self._height):
      if update[level].forward[level] is target:
        update[level].forward[level] = target.forward[level]

    # drop now-empty top levels so the height stays tight.
    while self._height > 1 and self._head.forward[self._height - 1] is None:
      self._height -= 1
    self._size -= 1
    return True

  def __iter__(self) -> Iterator[Key]:
    """
      Yield every stored key in ascending order — a level-1 walk.\n
    """
    current = self._head.forward[0]
    while current is not None:
      # past the head, every node stores a real key.
      key = current.key
      assert key is not None
      yield key
      current = current.forward[0]

  def items(self) -> Iterator[tuple[Key, Value]]:
    """
      Yield every `(key, value)` pair in ascending key order.\n
    """
    current = self._head.forward[0]
    while current is not None:
      # past the head, both key and value are populated.
      key = current.key
      value = current.value
      assert key is not None and value is not None
      yield key, value
      current = current.forward[0]

from typing import Any, Protocol, TypeVar


class Comparable(Protocol):
  """
    Anything orderable with `<` (int, float, str, tuple, date, …).\n
  """

  # `other` is position-only so built-ins (int, str, …), whose dunder
  # operands are position-only, structurally satisfy the protocol.
  def __lt__(self, other: Any, /) -> bool: ...
  def __gt__(self, other: Any, /) -> bool: ...
  def __le__(self, other: Any, /) -> bool: ...
  def __ge__(self, other: Any, /) -> bool: ...

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.

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 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:

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

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$.

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

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.

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.

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.

from __future__ import annotations

from hashlib import blake2b
from math import ceil, exp, log
from typing import Generic, Hashable, TypeVar

Element = TypeVar("Element", bound=Hashable)

def optimal_size(expected_count: int, false_positive_rate: float) -> int:
  """
    The bit-array size `m` that holds `expected_count` elements at the target\n
    false-positive rate: m = -n * ln(p) / (ln 2)^2, rounded up.\n
  """
  if expected_count <= 0:
    raise ValueError("expected_count must be positive")
  if not 0.0 < false_positive_rate < 1.0:
    raise ValueError("false_positive_rate must be in (0, 1)")

  # m = -n ln(p) / (ln 2)^2, never below one bit.
  size: float = -expected_count * log(false_positive_rate) / (log(2) ** 2)
  return max(1, ceil(size))

def optimal_hash_count(size: int, expected_count: int) -> int:
  """
    The hash count `k` that minimizes the false-positive rate for a given\n
    array size and load: k = (m / n) * ln 2, rounded to the nearest positive\n
    integer.\n
  """
  if expected_count <= 0:
    raise ValueError("expected_count must be positive")

  # k = (m / n) ln 2, at least one hash.
  count: int = round((size / expected_count) * log(2))
  return max(1, count)

class BloomFilter(Generic[Element]):
  """
    A space-efficient probabilistic set with no false negatives.\n
    Built either from explicit (`size`, `hash_count`) or, via\n
    `from_capacity`, from a target capacity and false-positive rate.\n
  """

  def __init__(self, size: int, hash_count: int) -> None:
    """
      A filter over a `size`-bit array probed by `hash_count` hashes.\n
    """
    if size <= 0:
      raise ValueError("size must be positive")
    if hash_count <= 0:
      raise ValueError("hash_count must be positive")

    # back the bit array with enough bytes to cover `size` bits.
    self._size: int = size
    self._hash_count: int = hash_count
    self._bits: bytearray = bytearray((size + 7) // 8)
    self._count: int = 0

  @classmethod
  def from_capacity(
    cls, expected_count: int, false_positive_rate: float = 0.01
  ) -> BloomFilter[Element]:
    """
      Size a filter for `expected_count` elements at `false_positive_rate`,\n
      choosing the array size and hash count that minimize space.\n
    """
    # pick the space-minimizing array size and hash count for the target rate.
    size: int = optimal_size(expected_count, false_positive_rate)
    hash_count: int = optimal_hash_count(size, expected_count)
    return cls(size, hash_count)

  @property
  def size(self) -> int:
    """
      The number of bits in the underlying array.\n
    """
    return self._size

  @property
  def hash_count(self) -> int:
    """
      The number of hash probes per key.\n
    """
    return self._hash_count

  def __len__(self) -> int:
    return self._count

  def _positions(self, element: Element) -> list[int]:
    """
      The `hash_count` bit indices an element maps to. Two independent base\n
      hashes are combined as `base_one + index * base_two` (Kirsch-Mitzenmacher\n
      double hashing), which behaves like `hash_count` independent hashes.\n
    """
    # split one 128-bit digest into two base hashes (second forced odd).
    digest: bytes = blake2b(
      repr(element).encode("utf-8"), digest_size=16
    ).digest()
    base_one: int = int.from_bytes(digest[:8], "big")
    base_two: int = int.from_bytes(digest[8:], "big") | 1

    # combine them into k indices, Kirsch-Mitzenmacher style.
    return [
      (base_one + index * base_two) % self._size
      for index in range(self._hash_count)
    ]

  def add(self, element: Element) -> None:
    """
      Insert `element`, setting each of its `hash_count` bits to 1.\n
    """
    # set each selected bit, then bump the inserted count.
    for position in self._positions(element):
      self._bits[position >> 3] |= 1 << (position & 7)
    self._count += 1

  def __contains__(self, element: Element) -> bool:
    """
      Whether `element` is possibly present. False means definitely absent;\n
      True means present or a false positive.\n
    """
    # any clear bit proves absence; all set means possibly present.
    for position in self._positions(element):
      if not (self._bits[position >> 3] >> (position & 7)) & 1:
        return False
    return True

  def estimated_false_positive_rate(self) -> float:
    """
      The expected false-positive rate at the current load, from the inserted\n
      count `n`, array size `m`, and hash count `k`:\n
      p ~ (1 - e^(-k n / m))^k.\n
    """
    # p ~ (1 - e^(-k n / m))^k.
    exponent: float = -self._hash_count * self._count / self._size
    return (1.0 - exp(exponent)) ** self._hash_count

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.⁴

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 $\frac{1}{2}$. 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).