# 布隆过滤器

> 布隆过滤器（英语：Bloom Filter）是1970年由伯顿·霍华德·布隆（Burton Howard Bloom）提出的高空间效率的概率数据结构。由一个通过一系列散列函数对样本元素映射而成的二进制位数组组成。布隆过滤器可用于检索一个元素是否在一个集合中，其空间效率和查询时间效率都远超一般算法。它不会产生假阴性（漏报），但有一定的假阳性（误报）率且难以删除元素。

- ID: m04559
- 分类: decide
- 领域: 决策科学

## 定义

一种极省空间的算法，用于判断一个元素是否在一个集合中。它能告诉你"某样东西一定不存在"或者"可能存在"，但绝不会告诉你"一定存在"（有误报率），且不支持删除。脚手架作用： 建立快速否定机制。在做决策或筛选信息时，不要追求精准的确认，而要追求高效的否定。先用低成本的筛子（布隆过滤器）过滤掉99%"一定不靠谱"的选项，把昂贵的精力留给那1%"可能靠谱"的选项进行二次核查。

## 机制

布隆过滤器是一种空间高效的概率数据结构，用多个哈希函数把元素映射到位阵列；可快速判断“某元素一定不在”或“可能在”集合中，允许假阳性但不允许假阴性。

## 练习

1) 在需要去重/存在性判断且容许多判的场景使用；2) 据可接受假阳性率定位数组大小与哈希数；3) 用它做缓存前置过滤、爬虫URL去重等。

## 脚手架用法

建立快速否定机制。在做决策或筛选信息时，不要追求精准的确认，而要追求高效的否定。先用低成本的筛子（布隆过滤器）过滤掉99%"一定不靠谱"的选项，把昂贵的精力留给那1%"可能靠谱"的选项进行二次核查。

[阅读网页](https://thinkingmodels.site/entries/detail/m04559)