布隆过滤器

  • 一个很长的二进制向量和一个映射函数
  • 可以用来检索一个元素是否在一个集合中（判断元素不在这个集合中，正确率100%，判断在时，准确率不确定）
  • 优点：空间效率和查询时间都远远超过一般的算法
  • 缺点：有一定的误识别率和删除困难

案例：

  1. 比特币
  2. redis
  3. 分布式系统mapreduce ：用来判断子任务是否在一台机器上