关于「布隆过滤器:误判率公式、最优探查数与 1.44 倍空间」,《布隆过滤器与基数估计》给出的定量结论是什么?

结论:第四章实测布隆过滤器,说明最优探查数与 1.443 倍的空间因子。

数据口径:示意网络中,各站独立访客相加是真实人数的 2.224 倍。 书中的站点、访客、订单与流量参数均为示意;全部计算由书中程序生成;本书是非个人化经营建议;访客统计只用匿名化、加密钥哈希的标识,不收集个人身份信息,须遵守所在地个人信息保护法规与站点隐私声明,法规只述大意,以上架前人工复核为准。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 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
查看完整验算程序
# 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))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《布隆过滤器与超对数对数基数估计、千字节内存统计百站独立访客与去重订单母典》第 4 章「布隆过滤器:误判率公式、最优探查数与 1.44 倍空间」(版本 1.0.0). 5D Library. DOI 待发布

DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 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}
}

本书其他章节结论