关于「布隆过滤器:误判率公式、最优探查数与 1.44 倍空间」,《布隆过滤器与基数估计》给出的定量结论是什么?
结论:第四章实测布隆过滤器,说明最优探查数与 1.443 倍的空间因子。
数据口径:示意网络中,各站独立访客相加是真实人数的 2.224 倍。 书中的站点、访客、订单与流量参数均为示意;全部计算由书中程序生成;本书是非个人化经营建议;访客统计只用匿名化、加密钥哈希的标识,不收集个人身份信息,须遵守所在地个人信息保护法规与站点隐私声明,法规只述大意,以上架前人工复核为准。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 1.443
| base 2^-ln2 | 0.6185, factor 1/ln2 = 1.4427 |
| bits/key k*=c ln2 best int k FP at best k bits set at k | |
| 4.0 | 2.773 3 0.146892 0.528 |
| 6.0 | 4.159 4 0.056057 0.487 |
| 8.0 | 5.545 6 0.021577 0.528 |
| 9.6 | 6.654 7 0.009965 0.518 |
| 10.0 | 6.931 7 0.008194 0.503 |
| 12.0 | 8.318 8 0.003142 0.487 |
| 14.4 | 9.981 10 0.000989 0.501 |
| 16.0 | 11.090 11 0.000459 0.497 |
| 20.0 | 13.863 14 0.000067 0.503 |
| target FP bits/key Bloom floor log2(1/p) overhead | |
| 0.0500 | 6.24 4.32 1.443 |
| 0.0100 | 9.59 6.64 1.443 |
| 0.0010 | 14.38 9.97 1.443 |
| 0.0001 | 19.17 13.29 1.443 |
| cost of k | 1 at 10 bits/key: FP 0.0952 vs 0.0082 |
| cost of k | 14 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}
}