关于「两端的修正:线性计数、切换点偏差与哈希位数」,《布隆过滤器与基数估计》给出的定量结论是什么?

结论:第三章处理两端:基数低于 2.5 倍寄存器个数时改用线性计数,切换点有 0.0144 的正偏差;32 位哈希在十亿访客时丢掉 0.1079。

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

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.1079, 32

threshold 2^32 / 30143165577
distinct n32-bit seen undercount 64-bit undercount
1e+06999884 0.0001 2.71e-14
1e+079988367 0.0012 2.71e-13
1e+0898844829 0.0116 2.71e-12
1.432e+08140839071 0.0165 3.88e-12
5e+08471993428 0.0560 1.36e-11
1e+09892117359 0.1079 2.71e-11
2e+091598931006 0.2005 5.42e-11
4e+092602611761 0.3493 1.08e-10
n1e+09: corrected 1000000000, error amplified by 1.262
n4e+09: corrected 4000000000, error amplified by 2.538
hash 32 bits, b12: max register 21, needs 5 bits
hash 64 bits, b12: max register 53, needs 6 bits
hash 64 bits, b14: 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}
}

本书其他章节结论