区块链-布隆过滤器原理

布隆过滤器

参考

这个过滤器的作用就是判定一个元素是否在一个集合里。之前常用的判定元素是否在集合里可以用链表，平衡二叉树，散列表等等来一个个比对元素的方式。这几种判定方式都有比较大的时间复杂度。

链表查询O(N)也就是逐一比对，随着集合的增大时间会正相关增大

平衡二叉树O(logn)如下图，虽然斜率比较低，但是还是正相关

散列表（哈希）查询 O(1) 具体参见

布隆过滤器

• 初始化一个m位的数组，初始值都是0

• 定义k个符合随机分布的哈希函数

  比如输入任意key，作为k个哈希函数的输入，会得到k个不同的哈希值，为什么不同呢？他可能是函数1填充了字符串a，函数2填充了字符串b。这样，得到了很多个哈希，这个哈希值mod m后取余就作为位置

• 当添加一个元素的时候，以这个元素作为key，执行这k个哈希函数，得到了k个位置，在m数组把k个位置置为1

如上图，m=18，k=3。经过执行函数后，假设m数组中置为1的情况

• 查询一个数是否在集合里面

  以这个数作为输入，去执行k个哈希函数，得到k个位置，去查询这k个位置是否都是1，如果有一个不是1，就可以确定返回这个数不在这个集合里面，如果都是1，表示可能在这个集合里面，因为它的位置可能因为其他数的添加而恰好都被置为1了。

布隆过滤和散列表有缺点对比

以hashmap为例子，里面的哈希表长度会随着集合的大小而自动扩充，而哈希冲突同一个桶下的，会采用链表，到后面采用红黑二叉树的方式去存取。

布隆过滤多个哈希函数降低了哈希冲突的可能性。