布隆过滤器

什么是布隆过滤器？

布隆过滤器（Bloom Filter）是一种用于快速检索某个元素是否存在于集合中的概率型数据结构。它基于一系列哈希函数和一个比特数组实现。

原理

哈希函数

哈希函数是一种将输入数据（任意长度）转换为固定长度的输出数据的算法。它的主要特点是：

1. 固定输出长度：无论输入数据的长度如何，哈希函数的输出长度是固定的。这使得哈希函数在处理不同大小的数据时具有一致性。

2. 确定性：对于相同的输入数据，哈希函数总是产生相同的输出。这意味着哈希函数是可预测的。

3. 不可逆性：通过哈希函数生成的输出（哈希值）通常不可逆地映射回原始输入数据。这意味着在常规情况下，无法从哈希值中恢复原始数据。

4. 高效性：哈希函数的计算速度通常很快，使其适用于大量数据的处理。

哈希冲突

哈希冲突指的是在使用哈希函数时，两个不同的输入值经过哈希函数运算后产生了相同的哈希值。具体来说，如果两个不同的输入数据经过哈希函数运算后得到的哈希值相同，就称为哈希冲突。

哈希冲突是不可避免的，因为哈希函数将无限数量的输入值映射到有限数量的输出值，这就意味着多个不同的输入可能会映射到同一个输出。哈希函数的设计旨在尽可能地减少哈希冲突的概率，但无法完全消除。

哈希冲突可能会导致数据丢失或不一致，尤其是在哈希表等数据结构中，因为哈希函数通常用于确定数据存储位置。因此，在设计和使用哈希函数时，需要考虑如何处理哈希冲突，常见的处理方法包括开放地址法、链地址法等。

插入数据

布隆过滤器首先需要一个数组（位图），每一位上是0/1，初始值都设置为0，插入数据时将原始数据经过哈希运算得到一个下标值，将对应的下标的数组值从0改成1。

随着不断的插入数据会有越来越多的值从0置为1。

查询数据

在查询某个元素是否存在时，对该元素取Hash，得到对应的下标，然后检查下标是否为1，如果为0则表示一定没有该数据，因为没有任何输入使得该位从0变成1。反之如果下标的值1，则表示可能存在，记住这里是可能存在，这是由于哈希碰撞的问题，不同输入可能对应同一输出，也就是说，不同的data经过哈希运算后得到了同一个下标。

删除数据

布隆过滤器并不能删除数据，同样是由于哈希碰撞的原因，如上图，假设我要删除data02这个元素，需要将下标为2的数组值从1改成0，这个操作会导致data01这个元素也被删除。

解决哈希冲突的方法

为了减小哈希碰撞的可能，通常会增加多个哈希函数，插入时多个哈希函数会得到不同的下标，将这些下标的值都设置成1。从而减小哈希碰撞的概率。

在查询时需要检验所有对应的下标值，有一个为0都表示元素不存在。此外，使用更多的哈希函数通常会使用更大的数组，这是由于哈希函数需要落在更大的区间。

优点和缺点

• 优点：
  • 布隆过滤器具有高效的查询速度，减少内存使用量。不需要存储元素本身，只需要存储少量的比特数组和使用多个哈希函数。
  • 可以用来过滤掉大量的负面查询，提高数据库、缓存等的性能。
• 缺点：
  • 布隆过滤器存在一定的误判率（False Positive Rate），即在判断某个元素是否存在时，可能会误判为存在，但实际上并不存在。这是由于不同元素的哈希值可能会产生冲突，导致多个元素映射到同一个位置。
  • 布隆过滤器不支持删除元素操作，因为删除元素可能影响到其他元素的哈希位置。

适用场景

• 网络爬虫中的 URL 去重
• 分布式系统中的缓存击穿、穿透等问题的缓解
• 数据库查询的快速过滤
• 黑名单过滤等。

原文地址：https://blog.csdn.net/pan_1214_/article/details/137676710

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！