布隆过滤器

布隆过滤器

一个很长的二进制向量和一系列随机映射函数（Hash函数）组成了布隆过滤器

添加、查询的时间复杂度都是： O ( k ) ，k 是哈希函数的个数。空间复杂度是： O ( m ) ，m 是二进制位的个数

常见应用：网页黑名单系统、垃圾邮件过滤系统、爬虫的网址判重系统、解决缓存穿透问题

判断 1 个元素是否存在：

• 一般使用哈希表（HashSet、HashMap）时间复杂度： O ( 1 ) ，
  • 空间利用率不高，需要占用比较多的内存资源
• 巨量数据使用布隆过滤器

优缺点：

• 优点：空间效率和查询时间都远远超过一般的算法
• 缺点：有一定的误判率、删除困难

原理：

• 假设布隆过滤器由 20位二进制、 3 个哈希函数组成，每个元素经过哈希函数处理都能生成一个索引位置
• 添加元素：将每一个哈希函数生成的索引位置都设为 1
• 查询元素是否存在
  • 如果有一个哈希函数生成的索引位置不为 1，就代表不存在（100%准确）
  • 如果每一个哈希函数生成的索引位置都为 1，就代表存在（存在一定的误判率）