喜欢就点关注吧!
哈希表与哈希函数
在简单数组或列表中插入新数据时,插入数据的索引不是从要插入的值确定的。这意味着密钥(索引)和值(数据)之间没有直接关系。因此,如果需要在数组中搜索值,则必须在所有索引中进行搜索。在哈希表中,您可以通过散列值来确定键或索引。这意味着密钥是根据值确定的,每次需要检查列表中是否存在该值时,您只需对值进行散列并搜索该密钥,查找速度非常快,时间复杂度为O(1)。
现在,假如你有一个庞大的弱密码列表,它存储在一些远程服务器上。由于数据量比较大,无法在RAM中一次加载它们。每次用户输入密码时,都要检查它是否是弱密码。如果是,你想给他/她一个警告,如果将数据存储在哈希表中,每次根据给定的密码进行匹配,匹配可能很快,但是在磁盘上或通过远程服务器上的网络查找的成本非常大,如何在尽量小的成本里得到匹配结果,就需要考虑使用布隆过滤器。
布隆过滤器
布隆过滤器是一种概率数据结构,由长度为m的位向量或位列表(仅包含0或1位值的列表)组成。最初所有值都设置为零,如下所示。
如果要将数据添加到bloom过滤器,需要将其提供给k个不同的哈希函数,并在位向量中将这些位设置为1。在哈希表中使用单个哈希函数,因此只有一个索引作为输出。但在bloom过滤器中,我们将使用多个哈希函数,也将得到多个索引。
如上图,我们存入geeks得到位向量中的1、4、7的位置为1,而其他位置为0。现在我们再存入nerd得到位向量中的3、4、5的位置为1,其中4的位置被重复置1。
现在如果我们想要查找元素是否在数据集中,假如我们想要查找“nerd”,将其通过三个哈希函数映射,根据刚才存储的情况会返回3、4、5位置上值为1。如果我们想要查找“cat”呢,假如返回1、3、7位置为1,虽然刚才我们没有存储该元素,但仍返回位置都为1,这就说明发生了误报。布隆过滤器查找原理图如下:
因此总结得到:
基本布隆过滤器支持两种操作:测试和添加。
在实验中如果布隆过滤器的太小,则很快就会将所有位字段全变为1。那么布隆过滤器将有很高的“误报率”。因此布隆过滤器的大小是一个非常重要。
较大的过滤器将具有较少的误报但速度越慢,而较小的过滤器将具有较多的误报。另一个重要参数是我们将使用多少哈希函数。我们使用的哈希函数越多,布隆过滤器就越慢,填充的速度就越快。但如果哈希函数太少,就可能会有更多误报。其关系图如下:
还可以根据滤波器的大小(m)、散列函数的数量(k)和插入的元素数n来计算误报率p,公式如下:
因此得到m、k与误报率的关系式为:
应用
Bloom过滤器主要是用于检测元素是否在集合中的。使用bloom过滤器的主要目的是减少磁盘(或网络)查找元素的代价。我们可以看到布隆过滤器可以在O(k)的时间内搜索元素,其中k是哈希函数的数量,查找速度非常快。
如果元素不在bloom过滤器中,那么我们肯定不需要继续查找。如果它在布隆过滤器中,我们也可以预期得到查找的准确率。下面是布隆过滤器的一些应用例子:
参考
https://medium.com/better-programming/probabilistic-data-structures-bloom-filter-5374112a7832