关于「两端的修正:线性计数、切换点偏差与哈希位数」,《布隆过滤器与基数估计》给出的定量结论是什么?
结论:第三章处理两端:基数低于 2.5 倍寄存器个数时改用线性计数,切换点有 0.0144 的正偏差;32 位哈希在十亿访客时丢掉 0.1079。
数据口径:示意网络中,各站独立访客相加是真实人数的 2.224 倍。 书中的站点、访客、订单与流量参数均为示意;全部计算由书中程序生成;本书是非个人化经营建议;访客统计只用匿名化、加密钥哈希的标识,不收集个人身份信息,须遵守所在地个人信息保护法规与站点隐私声明,法规只述大意,以上架前人工复核为准。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.1079, 32
| threshold 2^32 / 30 | 143165577 |
| distinct n | 32-bit seen undercount 64-bit undercount |
| 1e+06 | 999884 0.0001 2.71e-14 |
| 1e+07 | 9988367 0.0012 2.71e-13 |
| 1e+08 | 98844829 0.0116 2.71e-12 |
| 1.432e+08 | 140839071 0.0165 3.88e-12 |
| 5e+08 | 471993428 0.0560 1.36e-11 |
| 1e+09 | 892117359 0.1079 2.71e-11 |
| 2e+09 | 1598931006 0.2005 5.42e-11 |
| 4e+09 | 2602611761 0.3493 1.08e-10 |
| n | 1e+09: corrected 1000000000, error amplified by 1.262 |
| n | 4e+09: corrected 4000000000, error amplified by 2.538 |
| hash 32 bits, b | 12: max register 21, needs 5 bits |
| hash 64 bits, b | 12: max register 53, needs 6 bits |
| hash 64 bits, b | 14: max register 51, needs 6 bits |
查看完整验算程序
# Chapter 3. p32: a 32-bit hash runs out of room; a 64-bit hash does not.
# With an L-bit hash, n distinct items occupy about 2^L (1 - exp(-n/2^L))
# distinct hash values (balls in bins), so even a perfect sketch of the
# hash values undercounts. Flajolet et al. (2007) invert this above
# 2^32 / 30; the inversion is exact in expectation but multiplies any
# relative error in E by exp(n / 2^L), the slope of the inverse.
# Register width: values run up to L + 1 - b, so 5 bits for L = 32 and
# 6 bits for L = 64. Item counts below are illustrative.
import math
def occupied(n, bits):
return 2.0 ** bits * -math.expm1(-n / 2.0 ** bits)
def corrected(e, bits):
return -(2.0 ** bits) * math.log1p(-e / 2.0 ** bits)
print("threshold 2^32 / 30 = %.0f" % (2.0 ** 32 / 30))
print(" distinct n 32-bit seen undercount 64-bit undercount")
for n in (1e6, 1e7, 1e8, 1.432e8, 5e8, 1e9, 2e9, 4e9):
s32 = occupied(n, 32)
s64 = occupied(n, 64)
print("%12.4g %13.0f %11.4f %18.2e"
% (n, s32, 1.0 - s32 / n, 1.0 - s64 / n))
for n in (1e9, 4e9):
print("n = %.0e: corrected %.0f, error amplified by %.3f"
% (n, corrected(occupied(n, 32), 32), math.exp(n / 2.0 ** 32)))
for bits, b in ((32, 12), (64, 12), (64, 14)):
top = bits + 1 - b
print("hash %d bits, b = %d: max register %d, needs %d bits"
% (bits, b, top, top.bit_length()))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《布隆过滤器与超对数对数基数估计、千字节内存统计百站独立访客与去重订单母典》第 3 章「两端的修正:线性计数、切换点偏差与哈希位数」(版本 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}
}