本质上是一个很长的二进制向量和一系列随机映射函数
布隆过滤器可以用于检索一个元素是否在一个集合中
优点： 空间效率和查询时间都远远超过一般算法

缺点：

  • 有一定的误识别率（判定不存在则一定不存在，判定存在则有可能存在）
  • 删除困难

使用场景

商品页面：防止爬虫大量请求无效商品页面，流量打到数据库。缓存穿透

image.png

原理

当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们设置为1。检索时，只要看这些点是不是1就知道集合中有没有它了：

  1. 如果这些点有任何一个0，则被检索元素一定不存在
  2. 如果都是1，则被检索元素可能在。
  1. package datastruct.bloomfilter;
  3. import java.util.BitSet;
  4. import java.util.Random;
  5. import java.util.Iterator;
  7. class BloomFilter implements Cloneable {
  8.     private BitSet hashes;
  9.     private RandomInRange prng;
  10.     private int k; // Number of hash functions
  11.     private static final double LN2 = 0.6931471805599453; // ln(2)
  13.     /**
  14.      * Create a new bloom filter.
  15.      *
  16.      * @param n Expected number of elements
  17.      * @param m Desired size of the container in bits
  18.      **/
  19.     public BloomFilter(int n, int m) {
  20.         k = (int) Math.round(LN2 * m / n);
  21.         if (k <= 0) {
  22.             k = 1;
  23.         }
  24.         this.hashes = new BitSet(m);
  25.         this.prng = new RandomInRange(m, k);
  26.     }
  28.     /**
  29.      * Create a bloom filter of 1Mib.
  30.      *
  31.      * @param n Expected number of elements
  32.      **/
  33.     public BloomFilter(int n) {
  34.         this(n, 1024 * 1024 * 8);
  35.     }
  37.     /**
  38.      * Add an element to the container
  39.      **/
  40.     public void add(Object o) {
  41.         prng.init(o);
  42.         for (RandomInRange r : prng) {
  43.             hashes.set(r.value);
  44.         }
  45.     }
  47.     /**
  48.      * If the element is in the container, returns true.
  49.      * If the element is not in the container, returns true with a probability ≈ e^(-ln(2)² * m/n), otherwise false.
  50.      * So, when m is large enough, the return value can be interpreted as:
  51.      * - true  : the element is probably in the container
  52.      * - false : the element is definitely not in the container
  53.      **/
  54.     public boolean contains(Object o) {
  55.         prng.init(o);
  56.         for (RandomInRange r : prng) {
  57.             if (!hashes.get(r.value)) {
  58.                 return false;
  59.             }
  60.         }
  61.         return true;
  62.     }
  64.     /**
  65.      * Removes all of the elements from this filter.
  66.      **/
  67.     public void clear() {
  68.         hashes.clear();
  69.     }
  71.     /**
  72.      * Create a copy of the current filter
  73.      **/
  74.     @Override
  75.     public BloomFilter clone() throws CloneNotSupportedException {
  76.         return (BloomFilter) super.clone();
  77.     }
  79.     /**
  80.      * Generate a unique hash representing the filter
  81.      **/
  82.     @Override
  83.     public int hashCode() {
  84.         return hashes.hashCode() ^ k;
  85.     }
  87.     /**
  88.      * Test if the filters have equal bitsets.
  89.      * WARNING: two filters may contain the same elements, but not be equal
  90.      * (if the filters have different size for example).
  91.      */
  92.     public boolean equals(BloomFilter other) {
  93.         return this.hashes.equals(other.hashes) && this.k == other.k;
  94.     }
  96.     /**
  97.      * Merge another bloom filter into the current one.
  98.      * After this operation, the current bloom filter contains all elements in
  99.      * other.
  100.      **/
  101.     public void merge(BloomFilter other) {
  102.         if (other.k != this.k || other.hashes.size() != this.hashes.size()) {
  103.             throw new IllegalArgumentException("Incompatible bloom filters");
  104.         }
  105.         this.hashes.or(other.hashes);
  106.     }
  108.     private static class RandomInRange
  109.             implements Iterable<RandomInRange>, Iterator<RandomInRange> {
  111.         private Random prng;
  112.         private int max; // Maximum value returned + 1
  113.         private int count; // Number of random elements to generate
  114.         private int i = 0; // Number of elements generated
  115.         public int value; // The current value
  117.         RandomInRange(int maximum, int k) {
  118.             max = maximum;
  119.             count = k;
  120.             prng = new Random();
  121.         }
  123.         public void init(Object o) {
  124.             prng.setSeed(o.hashCode());
  125.         }
  127.         public Iterator<RandomInRange> iterator() {
  128.             i = 0;
  129.             return this;
  130.         }
  132.         @Override
  133.         public RandomInRange next() {
  134.             i++;
  135.             value = prng.nextInt() % max;
  136.             if (value < 0) {
  137.                 value = -value;
  138.             }
  139.             return this;
  140.         }
  142.         @Override
  143.         public boolean hasNext() {
  144.             return i < count;
  145.         }
  147.         @Override
  148.         public void remove() {
  149.             throw new UnsupportedOperationException();
  150.         }
  151.     }
  152. }