Probabilistic structures: Bloom filters and skip lists

Bloom filters and the false positive rate you trade for memory, counting variants, the expected cost of skip list operations, and count-min sketches for frequency estimates.

Bloom filters: no false negatives

A Bloom filter answers "is this item in the set" using a fixed bit array and k hash functions. It can say yes when the answer is no (a false positive), but it never says no when the answer is yes.

import math
from bitarray import bitarray

class Bloom:
    def __init__(self, n, error_rate=0.01):
        # m = -(n ln p) / (ln 2)^2 ; k = (m/n) ln 2
        self.m = int(-(n * math.log(error_rate)) / (math.log(2) ** 2))
        self.k = max(1, int(round((self.m / n) * math.log(2))))
        self.bits = bitarray(self.m)
        self.bits.setall(0)

    def _hashes(self, item):
        h1 = hash(item)
        h2 = hash((item, 0x5bd1e995))
        return (abs(h1 + i * h2) % self.m for i in range(self.k))

    def add(self, item):
        for i in self._hashes(item):
            self.bits[i] = 1

    def __contains__(self, item):
        return all(self.bits[i] for i in self._hashes(item))

Ten bits per element gives roughly a one percent false positive rate. Nothing can be deleted, because a bit may be shared by several items — clearing it would create false negatives.

Counting and the alternatives

• Counting Bloom filter — replace each bit with a small counter so deletion becomes possible, at several times the memory.
• Cuckoo filter — stores short fingerprints and supports deletion with a better false positive rate at similar size.
• Scalable Bloom filter — adds new filters as the set grows, keeping the error rate bounded.
• Count-min sketch — estimates how often an item appeared, always overestimating, using counters per hash row.
• HyperLogLog — counts distinct items in a few kilobytes with about two percent error.

# typical use: skip a disk lookup for keys that definitely do not exist
# query path
if key not in bloom:        # definitely absent — never a false negative
    return None
value = store.get(key)      # maybe present; false positives land here

Skip lists: expected O(log n) without rotations

A skip list is a linked list with express lanes. Each node is promoted to the next level with probability p, usually one half, creating a hierarchy that lets searches skip most of the list.

level 2:  1 ----------------------> 9
level 1:  1 -------> 4 -----------> 9
level 0:  1 -> 2 -> 4 -> 6 -> 7 -> 9

search 7: level 2 -> 9 is too far, drop
          level 1 -> 4, then 9 is too far, drop
          level 0 -> 6 -> 7 found

FAQ

Related

Heaps and priority queues Tries and prefix trees

Last refreshed 2026-09-18.