Bloom Filter

布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，用于快速判断一个元素是否可能属于某个集合。它允许一定的误判率（False Positive），即可能将不在集合中的元素误判为存在；但绝不会漏判（False Negative）——若元素确实在集合中，则查询结果必定为“存在”。

布隆过滤器广泛应用于需要在海量数据中快速排除“绝对不存在”情况的场景，例如：缓存穿透防护、URL 去重、数据库查询优化、恶意请求拦截等。

⚙️ 基本原理

布隆过滤器的核心思想是：利用多个独立的哈希函数，将元素映射到位数组中的多个位置，并通过这些位置的状态来推断元素的存在性。

数据结构组成

• 位数组（Bit Array）：长度为 m 的二进制数组，初始所有位都为 0
• 哈希函数集合：k 个独立的哈希函数，每个函数都能将输入元素映射到 [0, m-1] 范围内的位置

工作流程

1. 添加元素（Insert）

当向布隆过滤器中添加一个元素时：

• 使用 k 个哈希函数分别计算该元素的 k 个哈希值
• 将位数组中对应 k 个位置的值设为 1

注意：多个元素可能共享同一位，因此位只能从 0 → 1，不可逆。

2. 查询元素（Lookup）

当查询一个元素是否存在时：

• 使用相同的 k 个哈希函数计算该元素的 k 个哈希值
• 检查位数组中对应的 k 个位置是否都为 1
  • 如果全部为 1：元素可能存在（有误判可能）
  • 如果任意一个为 0：元素一定不存在

关键特性：为什么布隆过滤器敢说 “不存在的一定不存在”？

✅ 不会漏报（False Negative）

• 如果元素确实存在于集合中，查询结果一定是"存在"
• 因为添加元素时已经将对应的位设为 1，后续查询时这些位仍为 1

❌ 可能误报（False Positive），假阳性

• 如果元素不存在于集合中，但查询结果显示"存在"
• 原因：其他元素的哈希映射恰好覆盖了该元素的所有哈希位置

为什么布隆过滤器需要独立哈希函数？

布隆过滤器的核心思想是：通过多个独立的哈希函数将元素"随机"映射到位数组中，这样可以：

• 独立且均匀分布：避免某些位置被过度使用
• 降低冲突：减少不同元素映射到完全相同位置的概率
• 可控误判率：通过数学公式精确控制误判概率

时间复杂度和空间复杂度

• 时间复杂度：插入和查询的时间复杂度均为 O(k)（k为哈希函数数量），且占用内存极小。
• 空间复杂度：O(m)，位数组大小

其中 k 通常很小（如 3～7），因此实际性能接近常数时间。

不可逆，不可删除元素

传统布隆过滤器不支持删除操作，因为：

• 多个元素可能共享同一位；
• 若将某位置 1 → 0，可能误删其他元素的信息。

变种方案：计数布隆过滤器（Counting Bloom Filter）使用计数器替代位，支持删除，但空间开销更大。

这也是为什么布隆过滤器只能判断存在性，而不能列出所有元素。

数学分析

误判率计算

假设：位数组长度：m，哈希函数数量：k，已插入元素数量：n

经过推导，最优的哈希函数数量和对应的误判率为：

最优哈希函数数量：

$$k=\frac{m}{n}\ln (2)$$

最小误判率：

$$P={\left(0.5\right)}^k\approx {\left(0.6185\right)}^{\frac{m}{n}}$$

或者更精确的公式：

$$P={(1-e^{-\frac{kn}{m}})}^k$$

根据这个经验公式，可以对内存占用进行估算，利用最小误判率公式反推数组长度 m：

$$m=-\frac{n\ln p}{(\ln 2{)}^2}$$

可以看出：m 与 n 成正比（线性关系），但比例系数由 p（误判率）决定

$$\frac{m}{n}=\frac{-\ln p}{(\ln 2{)}^2}\approx \{\begin{array}{ll}9.58& p=1\mathrm{\%}\\ 14.38& p=0.1\mathrm{\%}\\ 19.16& p=0.01\mathrm{\%}\\ 4.80& p=10\mathrm{\%}\end{array}$$

所以，每个元素平均占 ~9.6 个 bit（1% 误判率），可以近似为 10 bit/元素

1 亿条数据， $n=1\times {10}^8$，那么

目标误判率 ($P$)	所需位数 $m$ (bit)	内存 (MB)
0.01% (0.0001)	$\approx 19.16\times {10}^8$	≈ 240 MB
0.1% (0.001)	$\approx 14.38\times {10}^8$	≈ 180 MB
1% (0.01)	$\approx 9.58\times {10}^8$	≈ 120 MB
10% (0.1)	$\approx 4.80\times {10}^8$	≈ 60 MB

✅ 实际工程建议

• 通用场景（如缓存穿透、URL 去重）：选择 1% 误判率 是性价比最高的平衡点 → 约 120 MB。
• 高敏感场景（如账号系统）：建议 ≤ 0.1% → 约 180 MB。
• 内存极度受限：可接受 5~10% 误判率 → 60~120 MB。

📌 注意：这是纯位数组的理论内存。实际库实现（如 Go 的 bloom、RedisBloom）可能有少量元数据开销（通常 < 1%），可忽略。

示例演示

假设我们有：

• 位数组长度 m = 10
• 哈希函数数量 k = 3
• 初始状态：[0,0,0,0,0,0,0,0,0,0]

添加元素 "apple"：

• hash1("apple") = 2
• hash2("apple") = 5
• hash3("apple") = 8
• 更新后：[0,0,1,0,0,1,0,0,1,0]

添加元素 "banana"：

• hash1("banana") = 1
• hash2("banana") = 5
• hash3("banana") = 9
• 更新后：[0,1,1,0,0,1,0,0,1,1]

查询元素 "orange"：

• hash1("orange") = 2 → 位2 = 1 ✓
• hash2("orange") = 5 → 位5 = 1 ✓
• hash3("orange") = 7 → 位7 = 0 ✗
• 结论："orange" 一定不存在

查询元素 "cherry"：

• hash1("cherry") = 1 → 位1 = 1 ✓
• hash2("cherry") = 8 → 位8 = 1 ✓
• hash3("cherry") = 9 → 位9 = 1 ✓
• 结论："cherry" 可能存在（但实际上可能不存在，这就是误判）

优缺点

优点

• 空间效率高：相比存储实际元素，只需要位数组
• 查询速度快：O(k) 时间复杂度，k通常很小
• 支持大规模数据：适合处理海量数据的成员查询

缺点

• 存在误判率：无法完全避免假阳性
• 不支持删除操作：传统布隆过滤器无法安全删除元素（因为多个元素可能共享同一位）
• 无法获取元素列表：只能判断存在性，不能枚举所有元素

代码实现

在 Go 中，常用的布隆过滤器库是 github.com/bits-and-blooms/bloom，其底层借助 github.com/bits-and-blooms/bitse 实现了高效的位数组（与每一位仅存储 0 或 1 一致）和多哈希函数支持。

type BitSet struct {
    length uint     // 逻辑位数（即 m）
    set    []uint64 // 底层存储：每个 uint64 存 64 个 bit
}

// Set 设置第 i 位为 1
func (b *BitSet) Set(i uint) *BitSet {
    if i >= b.length { // if we need more bits, make 'em
        b.extendSet(i)
    }
    b.set[i>>log2WordSize] |= 1 << wordsIndex(i)
    return b
}

// Test 测试第 i 位是否为 1
func (b *BitSet) Test(i uint) bool {
    if i >= b.length {
        return false
    }
    return b.set[i>>log2WordSize]&(1<<wordsIndex(i)) != 0
}

🎯 应用场景

领域	场景	核心作用	是否可接受 FP
缓存系统	Redis 缓存穿透防护	拦截无效 ID，避免 DB 压力	✅ 是
爬虫系统	URL 去重	避免重复抓取，节省带宽	✅ 是（可增量补爬）
安全风控	恶意 IP / 垃圾邮件过滤	快速拦截高风险请求	✅ 是（配合二次验证）
推荐系统	已推荐内容过滤	避免重复曝光	✅ 是（用户无感）
账号系统	用户名/手机号注册校验	减少 DB 查询压力	⚠️ 需配合 DB 最终确认
数据库	HBase / Cassandra / Bigtable RowKey 判断	减少磁盘 IO，跳过空 Region	✅ 是
分布式架构	分库分表路由	快速定位数据所在分片	✅ 是
存储系统	SSD/磁盘缓存预检	提升缓存命中判断速度	✅ 是
网络代理	Squid Cache Digests	快速判断内容是否在远端缓存	✅ 是
浏览器	Chrome 安全浏览（Safe Browsing）	快速判断恶意网址	✅ 是（配合云端验证）

布隆过滤器的所有落地场景，都围绕一个核心需求：在“海量数据”场景下，用“极小的空间”和“极快的速度”，快速排除“绝对不存在”的情况，从而减少后续高成本操作（如数据库查询、磁盘IO、网络请求）。同时，这些场景都满足两个关键前提：

• 可接受“极低的假阳性”（如重复推荐、误判未注册账号）；
• 绝对不能接受“假阴性”（如漏判垃圾邮件、误将已注册账号判为可注册）。

这正是布隆过滤器“零假阴性”特性的核心价值——在“效率优先、可接受微小误差”的场景中，它是无可替代的高效工具。

缓存系统：Redis 缓存穿透防护

场景：恶意用户或爬虫高频请求大量不存在的用户 ID，导致请求绕过 Redis 直接打到数据库，引发 CPU 打满甚至宕机。

解决方案：在 Redis 前置布隆过滤器，预加载所有合法用户 ID；查询时先查布隆过滤器，若返回“不存在”则直接拒绝，不再访问缓存或 DB。

示例：

• 某社交平台注册用户 5000 万，将所有用户 ID 写入布隆过滤器（误判率 0.1%，仅需约 70MB 内存）。此后，99% 的无效 ID 请求被拦截在网关层，DB QPS 下降 85%。
• 电商大促前，将1000万商品ID写入布隆过滤器（仅需约140MB内存），减少90%以上的无效数据库请求。

// UserService 用户查询服务：布隆过滤器 → Redis → 数据库 三级过滤
type UserService struct {
    bloomFilter *bloom.BloomFilter // 布隆过滤器
    redisClient *redis.Client      // Redis 客户端
    userDao     UserDao            // 数据库 DAO
}

// GetUserByID 根据用户ID查询用户信息（核心方法）
func (s *UserService) GetUserByID(ctx context.Context, userID string) (string, error) {
    // 1. 第一级：布隆过滤器预判断（绝对拦截不存在的 ID）
    if !s.bloomFilter.TestString(userID) {
        return "", nil // 不存在，直接返回空（或自定义错误）
    }

    key := "user:" + userID

    // 2. 第二级：Redis 缓存查询
    cacheVal, err := s.redisClient.Get(ctx, key).Result()
    if err == nil {
        if cacheVal == "" {
            // 缓存空值：确定不存在，直接返回
            return "", nil
        }
        // 缓存有值：直接返回
        return cacheVal, nil
    }
    // 缓存未命中（redis.Nil）：继续查DB

    // 3. 第三级：数据库查询
    userInfo, dbErr := s.userDao.FindUserByID(ctx, userID)
    if dbErr != nil {
        return "", dbErr
    }

    if userInfo != "" {
        // 数据库存在：缓存真实数据
        s.redisClient.Set(ctx, key, userInfo, 30*time.Minute)
    } else {
        // 数据库不存在（布隆过滤器假阳性）：缓存空值 1 分钟，防止穿透
        s.redisClient.Set(ctx, key, "", 1*time.Minute)
    }

    return userInfo, nil
}

爬虫系统：URL 去重

场景：通用爬虫抓取全网页面时，需记录已爬 URL 避免重复。若用 HashSet 存储 10 亿 URL，内存消耗超 100GB。

解决方案：使用布隆过滤器替代 HashSet，以极小内存代价实现高效去重。接受极低误判率（如 0.1%），并通过周期性“增量爬取”弥补漏抓。

示例：某搜索引擎爬虫每日处理 5 亿新 URL。布隆过滤器仅占用 600MB 内存（vs. HashMap 的 50GB+）。布隆过滤器的假阳性（将未爬取的 URL 判为已爬取）导致漏抓率 < 0.05%，可通过定期重置过滤器 + 夜间全量重爬弥补。

安全风控：恶意 IP / 垃圾邮件过滤

场景：API 网关需实时拦截高频攻击 IP，但黑名单可能达千万级，传统匹配性能不足。

解决方案：将已知恶意 IP（或垃圾邮件发件人邮箱）写入布隆过滤器。请求到达时先查过滤器，若命中则触发限流或验证码；若未命中则放行。

示例：某支付网关维护 200 万恶意 IP 列表。布隆过滤器（误判率 0.5%）部署在 Nginx 层，每秒可处理 10 万次 IP 检查，CPU 占用 < 5%。误判的正常 IP 会被二次验证放行，无业务影响。

推荐系统：已推荐内容过滤

场景：内容推荐系统（小红书、抖音）需避免向用户重复推荐同一内容（文章、视频），但用户历史行为数据量大（人均 1 万+），实时去重成本高。

解决方案：为每个用户分配一个轻量级布隆过滤器（如 1KB），记录其已观看内容 ID。推荐前过滤掉“可能存在”的内容。

示例：抖音为活跃用户维护本地布隆过滤器（m=8192, k=6）。在非关键、高吞吐的推荐场景（如短视频、商品流）中，即使误判 1% 的新内容为“已看”，用户也能对少量漏推无感，而系统节省了 90% 的重复推荐计算。

账号系统：用户名/手机号注册校验

场景：大促期间，大量用户尝试注册，频繁查询数据库判断“手机号是否已注册”，导致 DB 连接池耗尽。

解决方案：在注册入口前置布隆过滤器，预加载所有已注册手机号。

• 若布隆过滤器返回 “不存在”→ 该手机号一定未注册，可直接进入注册流程（或轻量查 DB 创建）；
• 若返回 “可能存在”→ 必须查询数据库确认是否真的已注册，避免假阳性误拒新用户。

🔔 注意：此处布隆过滤器主要用于 减少对“全新手机号”的无效 DB 查询，而非拦截“重复注册”。真正拦截重复注册仍依赖数据库唯一索引。

示例：某电商活动期间注册请求达 10 万/秒。布隆过滤器（含 1 亿手机号，误判率 1%）拦截了 99% 的重复注册尝试，仅 1% 请求查 DB，DB 负载下降 95%。

数据库：HBase RowKey 存在性判断

• 场景：HBase 查询一个不存在的 RowKey（如订单号）时，仍需扫描对应 Region 文件（HFile），产生大量无意义磁盘 IO。

• 解决方案：HBase 在每个 StoreFile（底层存储单元）中内置布隆过滤器，记录该文件包含的所有 RowKey 哈希值。查询前先查布隆过滤器，若为“不存在”则跳过该文件。

• 示例：某物流系统每天写入 1 亿条运单记录。开启布隆过滤器后，对无效运单号的查询响应时间从 200ms 降至 5ms，RegionServer 磁盘 IO 负载下降 70%。

分布式架构：分库分表路由

• 场景：用户查询订单时，系统需遍历所有 64 个分片以确定订单所在位置，效率低下。

• 解决方案：为每个分片维护一个布隆过滤器，存储该分片内的所有订单 ID。查询时并行检查各分片的布隆过滤器，仅对“可能存在”的分片发起实际查询。

• 示例：电商平台有 64 个订单库分片。使用布隆过滤器后，平均每次查询仅需访问 1~2 个分片（而非全部 64 个），查询延迟降低 90%。

存储系统：SSD/磁盘缓存预检

• 场景：操作系统或数据库的 Buffer Pool 需判断某数据页是否在缓存中，但缓存索引（如 LRU 链表）查找开销随缓存增大而上升。

• 解决方案：在缓存索引前加一层布隆过滤器，记录所有缓存页的标识（如 page ID）。若过滤器返回“不在缓存”，直接读磁盘；否则再查索引。

• 示例：MySQL InnoDB 的 Buffer Pool 为 100GB。加入布隆过滤器后，对冷数据的查询减少 80% 的无效哈希表查找，IOPS 提升 30%。

网络代理：Squid Cache Digests

• 场景：Squid 作为反向代理，需判断某资源是否存在于上游缓存服务器，避免重复拉取。

• 解决方案：上游缓存定期生成“Cache Digest”——一个包含所有缓存 URL 哈希的布隆过滤器，并同步给下游 Squid。Squid 先查 Digest，若未命中则直接回源。

• 示例：CDN 边缘节点通过 Cache Digest 减少 40% 的无效回源请求，带宽成本显著下降，且因 Digest 可压缩传输，网络开销极低。

浏览器：Chrome 安全浏览（Safe Browsing）

• 场景：Chrome 需实时判断用户访问的网址是否为钓鱼/恶意站点，但完整黑名单太大（超 1 亿条），无法全量下发。

• 解决方案：Google 将恶意 URL 哈希存入布隆过滤器，定期推送至浏览器本地。用户访问时先本地查布隆过滤器，若命中再向云端二次验证。

• 示例：Chrome 本地布隆过滤器仅 10MB，覆盖 99% 恶意站点。95% 的安全检查在本地完成，响应延迟 < 1ms，同时保护用户隐私（多数请求无需联网）。

🚀 布隆过滤器的优化

变种和改进

• 计数布隆过滤器（Counting Bloom Filter）：使用计数器代替位，支持删除操作

  把二进制数组换成 “计数器数组”（每个位置存整数，如 4 位）；添加元素时，计数器 + 1；删除时，计数器 - 1；查询时，判断计数器是否 > 0。

  但代价是空间增加（从 1bit 变为多 bit），且仍可能有计数溢出导致的误差。

• 可扩展布隆过滤器（Scalable Bloom Filter）：动态调整大小

• 分布式布隆过滤器（Distributed Bloom Filter）：适用于分布式系统

• 分层布隆过滤器（Layered Bloom Filter）：多层结构降低误判率

布隆过滤器在实际应用中需要根据具体的误判率要求、内存限制和数据规模来选择合适的参数配置。

高并发场景下的优化策略

在高并发场景下使用布隆过滤器（Bloom Filter）时，虽然其查询和插入操作本身是 O(k) 且无锁（只读位数组），但并发写入或共享读写可能引发性能瓶颈或数据竞争。因此，优化需从 并发安全、内存布局、缓存友好性、分片策略、工程实现 等多个维度入手。

只读场景优化

适用场景：如缓存穿透防护、恶意 IP 拦截等，布隆过滤器在服务启动或定期批量更新后不再修改。

优化策略：

• 预加载 + 只读（最常见）
• 使用不可变（immutable）布隆过滤器；
• 所有 goroutine/线程共享同一个实例，无需加锁；
• 利用 CPU 缓存局部性，提升查询速度。

读写场景优化

支持读写布隆过滤器需要频繁插入新元素，如分布式数据库分片路由、URL 去重等，此时位数组写入存在竞态条件（race condition），多个线程同时将同一位从 0 → 1，虽结果正确（幂等），但 CAS 或原子操作会成为瓶颈

分片布隆过滤器 (Sharded Bloom Filter)

将一个大布隆过滤器拆分为 N 个独立子过滤器（shard），每次操作根据元素哈希值路由到某个 shard；

type ShardedBloomFilter struct {
    shards []*bloom.BloomFilter
}

func (sb *ShardedBloomFilter) TestString(s string) bool {
    shard := sb.shards[fnv32(s) % len(sb.shards)]
    return shard.TestString(s)
}

优点：

• 写入/读取仅锁定单个 shard（甚至无锁，若 shard 只读）；
• 减少缓存行竞争（false sharing）；
• 可水平扩展。

📌 建议 shard 数 = CPU 核数 × 2，避免热点。

使用原子操作替代锁

• 位数组底层是 []uint64 或 []byte；
• 对每一位的写入使用 原子 OR 操作（如 Go 的 atomic.OrUint64）；
• 避免互斥锁（Mutex）带来的上下文切换开销。

⚠️ 注意：原子操作仍可能因缓存一致性协议（MESI）导致性能下降，分片 + 原子 是更优组合。

批量写入 + 版本切换（Copy-on-Write）

写操作不直接修改原过滤器，而是：

1. 复制当前布隆过滤器；
2. 在副本上批量插入新元素；
3. 原子切换指针（如 atomic.StorePointer）。

适用场景：写频率低、读频率极高（如每小时更新一次黑名单）。

优势：读操作完全无锁；写操作短暂阻塞但不影响在线服务。

内存与缓存优化

对齐与缓存行友好：

• 位数组长度 m 建议为 64 的倍数（匹配 uint64）；
• 避免跨缓存行（Cache Line, 通常 64 字节）的频繁写入；
• 分片时确保每个 shard 起始地址对齐。

减少内存分配：

• 预分配位数组，避免运行时扩容；
• 复用哈希计算中间结果（如 FNV-1a 可复用前缀）。

典型高并发架构示例（Go）

// 分片布隆过滤器，支持高并发读写
type ConcurrentBloomFilter struct {
    shards []struct {
        mu sync.Mutex // 若写频繁，可保留；若只读，可移除
        bf *bloom.BloomFilter
    }
}

func NewConcurrentBloom(m, k, shards int) *ConcurrentBloomFilter {
    cbf := &ConcurrentBloomFilter{
        shards: make([]struct{ mu sync.Mutex; bf *bloom.BloomFilter }, shards),
    }
    for i := range cbf.shards {
        cbf.shards[i].bf = bloom.NewWithEstimates(uint(m/shards), 0.01)
    }
    return cbf
}

func (cbf *ConcurrentBloomFilter) Add(data []byte) {
    idx := fnv32(data) % uint32(len(cbf.shards))
    // 若写极少，可去掉锁，依赖原子位操作（需自定义底层）
    cbf.shards[idx].mu.Lock()
    cbf.shards[idx].bf.Add(data)
    cbf.shards[idx].mu.Unlock()
}

func (cbf *ConcurrentBloomFilter) Test(data []byte) bool {
    idx := fnv32(data) % uint32(len(cbf.shards))
    return cbf.shards[idx].bf.Test(data) // 无锁读
}

💡 进阶：若使用 github.com/bits-and-blooms/bitset 底层，可自行实现原子 OR 操作，彻底无锁。

📐 公式推导

基本设定

• 位数组长度：$m$
• 插入元素个数：$n$
• 哈希函数个数：$k$
• 目标：求使误判率 $p$ 最小的 $k$

单个 bit 为 0 的概率

每次插入一个元素，会用 $k$ 个哈希函数将 $k$ 个位置置为 1。
总共进行 $kn$ 次独立哈希操作。

某一位在一次哈希中不被选中的概率是：

$$1-\frac{1}{m}$$

经过 $kn$ 次哈希后，该位仍为 0 的概率为：

$${(1-\frac{1}{m})}^{kn}$$

当 $m$ 很大时，利用极限公式 $\underset{m\to \mathrm{\infty }}{lim}{(1-\frac{1}{m})}^m=e^{-1}$，可近似为：

$${(1-\frac{1}{m})}^{kn}\approx e^{-kn/m}$$

因此，该位为 1 的概率为：

$$1-e^{-kn/m}$$

误判率（False Positive Rate）

查询一个不在集合中的元素时，若其 $k$ 个哈希位置全为 1，则发生误判。

假设各位置独立（近似成立），误判率为：

$$\begin{array}{}\text{(1)}& p={(1-e^{-kn/m})}^k\end{array}$$

最小化误判率：求最优 $k$

我们希望选择 $k$ 使得 $p$ 最小。对式 (1) 取自然对数以简化求导：

$$\ln p=k\ln (1-e^{-kn/m})$$

令 $x=\frac{kn}{m}$，即 $k=\frac{mx}{n}$，代入得：

$$\ln p=\frac{mx}{n}\cdot \ln (1-e^{-x})$$

对 $x$ 求导并令导数为 0：

$$\frac{d}{dx}[\frac{mx}{n}\ln (1-e^{-x})]=\frac{m}{n}[\ln (1-e^{-x})+\frac{x{e}^{-x}}{1-e^{-x}}]=0$$

即：

$$\begin{array}{}\text{(2)}& \ln (1-e^{-x})+\frac{x{e}^{-x}}{1-e^{-x}}=0\end{array}$$

令 $y=e^{-x}$，则 $1-y=1-e^{-x}$，方程变为：

$$\ln (1-y)+\frac{-\ln y\cdot y}{1-y}=0$$

通过观察或数值验证，当$y=\frac{1}{2}$（即 $e^{-x}=\frac{1}{2}$）时满足方程：

• $x=\ln 2$
• 代入验证：$$\ln (1-\frac{1}{2})+\frac{\ln 2\cdot \frac{1}{2}}{1-\frac{1}{2}}=\ln \left(\frac{1}{2}\right)+\ln 2=-\ln 2+\ln 2=0$$

✅ 成立！

因此最优解为：

$$\begin{array}{}\text{(3)}& x=\frac{kn}{m}=\ln 2\Rightarrow k_{\text{opt}}=\frac{m}{n}\ln 2\end{array}$$

由于 $\ln 2\approx 0.6931$，常写作：

$$k_{\text{opt}}\approx 0.6931\cdot \frac{m}{n}$$

最小误判率

将 $k=\frac{m}{n}\ln 2$ 代回误判率公式 (1)：

首先计算指数部分：

$$e^{-kn/m}=e^{-\ln 2}=\frac{1}{2}$$

所以：

$$p_{min}={(1-\frac{1}{2})}^k={\left(\frac{1}{2}\right)}^k=2^{-k}$$

再将 $k=\frac{m}{n}\ln 2$ 代入：

$$\begin{array}{}\text{(4)}& p_{min}=2^{-\frac{m}{n}\ln 2}=e^{-\frac{m}{n}(\ln 2{)}^2}\end{array}$$

因为 $(\ln 2{)}^2\approx 0.48045$，也可写为：

$$p_{min}\approx {\left(0.6185\right)}^{m/n}$$

注：$0.6185=e^{-(\ln 2{)}^2}\approx e^{-0.48045}$