教程目录

想要实际看看算法是如何工作的吗?

通过交互式可视化深入理解算法运行过程

查看算法可视化

布隆过滤器教程

介绍

布隆过滤器(Bloom Filter)是一种空间效率很高的概率型数据结构,它用于判断一个元素是否在一个集合中。布隆过滤器的特点是:对于一个元素,如果布隆过滤器说它不存在,那么它一定不存在;如果布隆过滤器说它存在,那么它可能存在(有一定的误判率)。

布隆过滤器的核心组成部分包括:

  • 位数组(Bit Array):一个由二进制位(0或1)组成的数组,初始时所有位都设为0
  • 哈希函数(Hash Functions):多个不同的哈希函数,用于将元素映射到位数组的不同位置
  • 误判率(False Positive Rate):表示不在集合中的元素被误判为在集合中的概率

核心特性

  1. 高效的空间利用率:相比于传统的存储方式,布隆过滤器使用的空间非常小
  2. 常数时间复杂度:判断元素是否存在的操作时间复杂度为O(k),k为哈希函数的个数,通常很小
  3. 可能存在误判:布隆过滤器可能会将不在集合中的元素误判为在集合中(假阳性),但不会将在集合中的元素误判为不在(没有假阴性)
  4. 不可移除元素:标准的布隆过滤器不支持删除元素的操作

基本操作

布隆过滤器支持两种基本操作:

  1. 添加元素(Add):

...

目录