布隆过滤器
💡
原文中文，约5900字，阅读约需15分钟。
📝
内容提要
布隆过滤器是一种判断元素是否存在于集合中的高效数据结构，通过随机映射函数将元素映射到位图中。它具有空间效率和查询时间高的优点，但存在误判率和无法删除元素的缺点。可以应用于URL去重、垃圾邮件过滤等场景。使用开源库bits-and-blooms/bloom可以方便实现布隆过滤器。
🎯
关键要点
- 布隆过滤器是1970年由布隆提出的高效数据结构，用于判断元素是否存在于集合中。
- 布隆过滤器的优点是空间效率高和查询时间快，但存在误判率和无法删除元素的缺点。
- 查找问题可以通过线性结构、散列表结构和树形结构等多种数据结构建模。
- 布隆过滤器通过K个哈希函数将元素映射到位图中，判断元素是否存在于集合中。
- 如果任意一个映射位置为0，则元素一定不存在；如果都是1，则元素可能存在。
- 布隆过滤器无法提供“一定存在”的保证，因为可能存在哈希冲突导致误判。
- 元素不允许被删除，以避免影响其他元素的存在判断。
- 布隆过滤器的应用场景包括URL去重、垃圾邮件过滤等。
- 实现布隆过滤器需要规划元素长度和哈希映射值的数据结构，通常使用bitmap。
- 选择合适的哈希函数（如Murmur3）可以显著降低碰撞率，提高性能。
- 布隆过滤器的数学参数包括哈希空间大小、元素集合大小、哈希函数个数和误判概率。
- 可以使用在线工具计算所需的哈希函数个数和空间。
- 开源库bits-and-blooms/bloom提供了布隆过滤器的实现，支持Go语言。
- 布隆过滤器的优点包括空间和时间复杂度优势，适合对数据保密要求高的场景。
- 布隆过滤器的缺点是误判率随元素数量增加而增加，且不支持删除元素。
➡️
