布隆过滤器

        本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构，特点是高效地插入和查询，用来告诉我们“某样东西一定不存在或者可能存在”。相比于传统的 List、Set、Map等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。拥有极高的性能，无论写入 *** 作还是读取 *** 作，时间复杂度是O(1)。

• 用途
  1. 解决Redis缓存穿透
  2. 在爬虫时，对爬虫网址进行过滤，已经存在布隆中的网址，不在爬取。
  3. 垃圾邮件过滤，对每一个发送邮件的地址进行判断是否在布隆的黑名单中，如果在就判断为垃圾邮件。
• 原理

        在初始状态时，对于长度为 m 的位数组，它的所有位都被置为0。当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。查询某个变量的时候，使用N个哈希算法，计算出N个地址下标，然后检查它们里面的二进制数是否全是 1，如果都是1，则变量可能存在；如果这些点有任何一个是0，则查询变量一定不存在。

• 特性
  1. 一个元素如果判断结果为存在的时候元素不一定存在，但是判断结果为不存在的时候则一定不存在。
  2. 布隆过滤器可以添加元素，但是不能删除元素。因为删掉元素会导致误判率增加。
• 优缺点
  1. 优点：优点很明显，二进制组成的数组，占用内存极少，并且插入和查询速度都足够快。
  2. 缺点：随着数据的增加，误判率会增加；还有无法判断数据一定存在；另外还有一个重要缺点，无法删除数据
• 为何存在误判？误判率是多少？如何减小误判？

        布隆过滤器的误判是指多个变量经过哈希之后在相同的bit位置都是1，这样就无法判断究竟是哪个变量产生的，因此误判的根源在于相同的 bit 位被多次映射且设置为1。这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。如果我们直接删除这一位的话，会影响其他的元素。

        为何相同的bit位被多次映射为1，因为映射函数本身就是散列函数，散列函数是会有碰撞的。

布隆过滤器的默认误算率大概为3%。

布隆过滤器有一个可预测的误判率(FPP)：

• n 是已经添加元素的数量；
• k 哈希的次数；
• m 布隆过滤器的长度(如比特数组的大小)；

通过以上算法可知，减小误判率方式：

1. 选择多个 Hash 函数计算多个 hash 值，可以减少误判
2. m/n越大，hash次数越多，误判率越低。

        在预估出大概总元素的数量后，根据可接受的误判率，选择初始化比特数组的大小和哈希的次数。如果布隆过滤器的长度太小，所有的 bit 位很快就会被用完，此时任何查询都会返回可能存在；如果布隆过滤器的长度太大，那么误判的概率会很小，但是内存空间浪费严重。类似的，哈希函数的个数越多，则布隆过滤器的 bit 位被占用的速度越快；哈希函数的个数越少，则误判的概率又会上升。因此，布隆过滤器的长度和哈希函数的个数需要根据业务场景来权衡。

Bloom Filter Calculator（输入预期元素数量和可接受的误判率，可看到最佳配置）

• 哈希碰撞

1、Hash碰撞：如果不同的输入经哈希映射得到了同一个哈希值，就发生了"哈希碰撞"（collision）。

2、为何会有hash碰撞？

        由于通过哈希函数产生的哈希值是有限的，而要哈希的数据是无穷的，导致经过哈希函数处理后仍然有不同的数据对应相同的值。这时候就产生了哈希冲突。一般情况下，哈希值越长的哈希算法，散列冲突的概率越低。

3、Hash碰撞解决方案

1. 开放寻址法（再散列法）：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。（线性探测再散列、二次探测再散列、伪随机探测再散列）
2. 再哈希法（Rehash）：同时构造多个不同的哈希函数，当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
3. 链地址法（拉链法）：基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。【HashMap的哈希冲突解决方法】