简介

1970年由布隆提出，至今仍广泛应用

原理

  1. 根据数据量定义一个长度为n的bitMap(bitMap的长度要和hash值能产出对应起来，n越大，越消耗性能)
  2. 定义k个hash函数给存在的键求得值，在bitMap上标1(k和长度n关联,k越大，误判越低)
  3. 有数据来时，通过n个hash函数计算，只有求得的bitMap位都为1的时候才能判断这个键可能存在

核心要素

通过则表示键可能存在，不通过则键一定不存在

优点

  1. 判断高效，占用内存很少
  2. 保密性好

缺点

  1. 删除会比较不友好，不能直接修改bitMap(因为可能有其他键会用)，只能定期全部rehash
  2. 会有机率误判