什么是布隆过滤器
布隆过滤器本质上是一种数据结构，比拟奇妙的概率型数据结构（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 以上的空间来存储