Show HN: SIMD-Optimized Bloom Filters in Mojo for Large-Scale Systems
9 months ago
- #data-structures
- #probabilistic
- #optimization
- 布隆过滤器是一种用于集合成员测试的空间高效概率型数据结构。
- 关键特性：无假阴性、可能存在假阳性、空间效率高、操作快速（O(k)）、固定大小。
- 常见应用场景：网络爬虫、数据库、分布式系统。
- 提供两种布隆过滤器变体：标准布隆过滤器和分块布隆过滤器（SIMD优化版）。
- 标准布隆过滤器：内存占用可预测，适合较小数据集。
- 分块布隆过滤器：缓存效率高，专为大数据集设计，利用SIMD指令。
- 两种变体共享相同接口，包含添加、包含检测、合并、交集等方法。
- 其他实用方法：置位比特数、填充率、预估基数、当前误判率、轮转检测。
- 项目灵感来自高性能Go语言实现及缓存优化的布隆过滤器设计研究。
- 基于BSD 2-Clause许可证开源。