从位图转换至布隆过滤器，有何具体实现步骤？

本文共计3718个文字，预计阅读时间需要15分钟。

前言+本文将简要介绍伪原创的原理和内容。

前言

本文将以 C# 语言来实现一个简单的布隆过滤器，为简化说明，设计得很简单，仅供学习使用。

感谢@时总百忙之中的指导。

布隆过滤器简介

布隆过滤器（Bloom filter）是一种特殊的 Hash Table，能够以较小的存储空间较快地判断出数据是否存在。常用于允许一定误判率的数据过滤及防止缓存击穿及等场景。

相较于 .NET 中的 HashSet 这样传统的 Hash Table，存在以下的优劣势。

优势：

1. 占用的存储空间较小。不需要像 HashSet 一样存储 Key 的原始数据。

劣势：

1. 存在误判率，过滤器认为不存在的数据一定不存在，但是认为存在的数据不一定真的存在。这个和布隆过滤器的实现方式有关。
2. 不支持数据的删除，下文会讲为什么不支持删除。

数据的存储

布隆过滤器的数据保存在 位图（Bitmap）上。Bitmap 简而言之是二进制位（bit）的数组。Hash Table 保存每个元素的位置，我们称之为 桶（bucket）， Bitmap 上的每一位就是布隆过滤器的 bucket。

布隆过滤器的每一个 bucket 只能存储 0 或 1。