哈希算法题目：设计一个基于哈希的分布式事件去重系统 题目描述 设计一个分布式事件去重系统，用于处理高并发场景下的事件流（如用户点击、日志记录等）。要求： 支持在分布式节点中判断事件是否重复（同一事件可能在短时间内被多次提交）。 允许一定的误判率（假阳性），但需严格控制内存占用。 支持动态调整去重的时间窗口（例如最近1小时内的重复事件需过滤）。 解题过程 步骤1：明确核心需求 去重逻辑 ：同一事件（如相同事件ID）在时间窗口内仅处理一次。 分布式挑战 ：事件可能被发送到任意节点，需全局去重。 资源限制 ：内存有限，需用空间效率高的数据结构。 结论 ：适合使用 布隆过滤器（Bloom Filter） 结合时间窗口滑动机制。 步骤2：选择基础数据结构——布隆过滤器 布隆过滤器的特点： 使用位数组和多个哈希函数，空间效率高。 支持快速插入和查询，但存在假阳性（可能误判重复）。 无法删除元素（需额外设计）。 哈希函数设计 ： 选择多个独立的哈希函数（如 MurmurHash、SHA-256 的不同种子），将事件ID映射到位数组的不同位置。 步骤3：处理时间窗口滑动 问题：布隆过滤器无法直接删除过期事件。 解决方案： 分层布隆过滤器（Sliding Window Bloom Filter） ： 将时间窗口划分为多个小时间片（例如1小时窗口分为60个1分钟的分片），每个分片独立维护一个布隆过滤器。 滑动逻辑： 当前时间片接收新事件，插入对应分片的布隆过滤器。 每隔一个分片时长，淘汰最旧的分片，创建新分片。 查询时，检查所有活跃分片（当前时间窗口内的分片），若任一布隆过滤器认为事件存在，则判为重复。 步骤4：分布式协同设计 挑战：多个节点需共享去重状态。 方案： 中心化存储 ：将所有分片的布隆过滤器位数组存储在共享存储（如 Redis Cluster）。 优点：状态一致性强。 缺点：网络开销大，需解决并发冲突。 本地缓存+同步机制 ： 每个节点缓存部分时间窗口的布隆过滤器，定期同步到中心存储。 查询时，先查本地缓存，再查中心存储（减少延迟）。 步骤5：控制误判率与内存优化 布隆过滤器的误判率公式： \[ P \approx \left(1 - e^{-kn/m}\right)^k \] 其中： \(m\)：位数组大小 \(n\)：预期事件数量 \(k\)：哈希函数个数 优化策略 ： 根据时间窗口内预期事件数 \(n\) 和可接受误判率 \(P\)，计算所需位数组大小 \(m\) 和哈希函数数量 \(k\)。 示例：若 \(n=10^6, P=0.01\)，则 \(m \approx 9.6 \times 10^6\) 位（约 1.2 MB），\(k \approx 7\)。 步骤6：处理哈希冲突与边界情况 哈希冲突 ：多个事件可能映射到相同位，导致误判。可通过增加位数组大小或哈希函数数量降低概率。 时间同步 ：分布式节点需时间同步（如使用 NTP），确保时间窗口划分一致。 容错机制 ：某分片数据丢失时，可允许短暂误判（视为新事件），避免系统阻塞。 总结 该系统通过 分层布隆过滤器 实现时间窗口滑动，结合分布式存储与本地缓存平衡性能与一致性。核心优势在于空间效率高，适合海量事件去重；缺点是无法避免假阳性，需根据场景调整参数。