什么是布隆过滤器
布隆过滤器本质上是一种数据结构，比拟奇妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查问，能够用来通知你 “某样货色肯定不存在或者可能存在”。
相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，然而毛病是其返回的后果是概率性的，而不是确切的。
构造特点
布隆过滤器实际上是一个bit数组，数组的每一位只有0，1两种值，通过将一个key进行屡次不同的hash生成多个hash值，而后贮存在bit数组中；当判断某个key是否存在时，将key进行屡次hash，在bit数组中查问多个hash值是否存在，当多个hash值的查问后果都为1时，则该key可能存在，留神仅仅是【可能存在】，因为可能有其余的key也映射到了雷同的地位，若存在查问后果为0的hash值，则该key【肯定不存在】
优缺点
当bit数组长度过小时，计算hash值寄存的地位很大概率会产生重叠，则误判的几率增大
当bit数组长度过大时，误判几率小，然而可能导致内存空间占用过大，空间换工夫性价比低
实际
redis 的 setbit 和 getbit 就能够实现布隆过滤器，但当key的长度很长时，占用的内存空间会十分大，例如一个10位的数字，须要耗费100M以上的空间来存储