What does Bloom Filters and HyperLogLog for Many Sites conclude, in numbers, about “The Bloom Filter: the False-Positive Formula, the Optimal Probe Count and 1.44 Times the Space”?

Answer: Chapter 4 measures Bloom filters and explains the optimal probe count and the space factor of 1.443.

Scope of the numbers: In an illustrative network, per-site unique visitors add up to 2.224 times the true number of people. Marked boxes separate published evidence, Python calculations (20 programs), classical sources and the author's hypotheses.

中文版

Data table

The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 1.443

base 2^-ln20.6185, factor 1/ln2 = 1.4427
bits/key k*=c ln2 best int k FP at best k bits set at k
4.02.773 3 0.146892 0.528
6.04.159 4 0.056057 0.487
8.05.545 6 0.021577 0.528
9.66.654 7 0.009965 0.518
10.06.931 7 0.008194 0.503
12.08.318 8 0.003142 0.487
14.49.981 10 0.000989 0.501
16.011.090 11 0.000459 0.497
20.013.863 14 0.000067 0.503
target FP bits/key Bloom floor log2(1/p) overhead
0.05006.24 4.32 1.443
0.01009.59 6.64 1.443
0.001014.38 9.97 1.443
0.000119.17 13.29 1.443
cost of k1 at 10 bits/key: FP 0.0952 vs 0.0082
cost of k14 at 10 bits/key: FP 0.0190
Show the full program
# Chapter 4. p42: the optimal number of hash probes and the 1.44 factor.
# Closed form p(k) = (1 - exp(-k / c))^k with c = m / n bits per key.
# Calculus gives k* = c ln 2, where half the bits are set and
# p = 2^-k* = 0.6185^c. For a target p the bits per key are
# c = log2(1/p) / ln 2 = 1.4427 log2(1/p), against the lower bound of
# log2(1/p) bits per key for any structure with no false negatives
# (Broder and Mitzenmacher 2004, sec. 2.2). Integer k found by scanning.
import math

LN2 = math.log(2)


def p_of(k, c):
    return (1.0 - math.exp(-k / c)) ** k


print("base 2^-ln2 = %.4f, factor 1/ln2 = %.4f" % (0.5 ** LN2, 1 / LN2))
print("bits/key  k*=c ln2  best int k  FP at best k  bits set at k")
for c in (4, 6, 8, 9.6, 10, 12, 14.4, 16, 20):
    kbest = min(range(1, 40), key=lambda k: p_of(k, c))
    print("%8.1f %9.3f %11d %13.6f %14.3f"
          % (c, c * LN2, kbest, p_of(kbest, c),
             1.0 - math.exp(-kbest / c)))
print("target FP   bits/key Bloom  floor log2(1/p)  overhead")
for p in (0.05, 0.01, 0.001, 0.0001):
    floor = math.log2(1.0 / p)
    print("%9.4f %16.2f %16.2f %9.3f"
          % (p, floor / LN2, floor, 1 / LN2))
print("cost of k = 1 at 10 bits/key: FP %.4f vs %.4f"
      % (p_of(1, 10), p_of(7, 10)))
print("cost of k = 14 at 10 bits/key: FP %.4f" % p_of(14, 10))

Single source and citation

Fan, Y. (2026). Bloom Filters and HyperLogLog Cardinality Estimation: Counting Unique Visitors and Deduplicating Orders across a Hundred Sites in Kilobytes (Version 1.0.0), Chapter 4: The Bloom Filter: the False-Positive Formula, the Optimal Probe Count and 1.44 Times the Space. 5D Library. DOI pending

DOI pending · monograph page goes live after publication · 5DL-B-294 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026294,
  author    = {Fan, Yafu},
  title     = {Bloom Filters and HyperLogLog Cardinality Estimation: Counting Unique Visitors and Deduplicating Orders across a Hundred Sites in Kilobytes},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

Other chapter answers in this book