布隆过滤器计数布隆过滤器及其的应用57页PPT

布隆过滤器底层原理布隆过滤器是一种数据结构，用于快速判断一个元素是否存在于一个集合中。

它通过使用位数组和多个哈希函数来实现这一功能。

布隆过滤器的底层原理非常巧妙，可以高效地处理大规模的数据集。

布隆过滤器的核心是位数组，它通常是一个固定长度的二进制数组。

位数组的每个位置都对应一个位，初始时都被设置为0。

当一个元素被加入到布隆过滤器中时，它会经过多个哈希函数的处理，得到多个哈希值。

这些哈希值对应的位置在位数组中被设置为1。

当需要判断一个元素是否存在时，同样会经过多个哈希函数的处理，得到多个哈希值。

如果这些哈希值对应的位置都为1，那么可以判断该元素可能存在于集合中。

如果有任何一个位置为0，那么可以确定该元素一定不存在于集合中。

布隆过滤器的核心思想是通过多个哈希函数的处理，将元素分散到位数组中的不同位置。

这样可以减少冲突的概率，提高判断的准确性。

同时，布隆过滤器的空间效率也非常高。

由于位数组的长度是固定的，不受存入元素的个数影响，所以在存储大规模数据集时，布隆过滤器所占用的空间相对较小。

然而，由于布隆过滤器的特殊性，它也存在一些缺点。

首先，布隆过滤器在判断一个元素是否存在时，有一定的误判率。

也就是说，有可能判断一个元素存在于集合中，但实际上并不存在。

这是因为多个元素可能被哈希到同一个位置上，导致冲突。

其次，布隆过滤器只能判断元素是否存在，而不能得到元素的具体信息。

因此，在实际应用中，布隆过滤器通常用于判断一个元素是否存在，如果需要获取具体信息，还需要进一步查询其他数据结构。

布隆过滤器在实际应用中有着广泛的应用。

例如，它可以用于网络爬虫中，判断一个URL是否已经被访问过，从而避免重复爬取。

又如，在大规模的分布式系统中，布隆过滤器可以用于判断一个元素是否已经存在于缓存中，从而减少对数据库的查询次数。

此外，布隆过滤器还可以用于垃圾邮件过滤、黑名单检测等方面。

总的来说，布隆过滤器是一种高效、节省空间的数据结构，用于判断一个元素是否存在于一个集合中。

详解布隆过滤器的原理、使用场景和注意事项英文版Detailed Explanation of Bloom Filter's Principles, Usage Scenarios, and PrecautionsBloom Filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. It was invented by Burton Bloom in 1970 and has found widespread applications in various fields such as caching, network security, and databases.Principles of Bloom Filter:Bloom Filter works by using bit arrays and hash functions. Here's a step-by-step explanation of its principles:Initialization: Bloom Filter starts with an empty bit array of size 'm' bits, initially set to zero.Hashing: Bloom Filter uses 'k' independent hash functions, each mapping the input elements to one of the 'm' bit positions in the bit array.Insertion: When inserting an element into the Bloom Filter, each hash function is applied to the element, and the corresponding bit positions in the bit array are set to 1.Testing: To test whether an element is a member of the set, the same hash functions are applied to the element, and if all the corresponding bit positions in the bit array are 1, then the element is considered to be a member of the set. However, it's important to note that a false positive result (i.e., falsely claiming that an element is a member) is possible, but a false negative (i.e., falsely claiming that an element is not a member) is not possible.Usage Scenarios of Bloom Filter:Bloom Filters are widely used in various scenarios due to their space efficiency and probabilistic nature. Some common usage scenarios include:Caching: Bloom Filters can be used to quickly determine whether a requested item is present in a cache, thus avoiding unnecessary disk I/O operations.Network Security: Bloom Filters are used in network security applications to quickly detect the presence of malicious content in network packets.Databases: Bloom Filters can be used in databases to efficiently search for the presence of specific keys in a large dataset.Precautions When Using Bloom Filter:When using Bloom Filter, it's important to consider the following precautions:False Positives: As mentioned earlier, Bloom Filters can produce false positive results. Therefore, it's crucial to have a fallback mechanism to confirm the membership of elements that are identified as positive by the Bloom Filter.Choosing the Right Parameters: The performance of Bloom Filter depends on the choice of parameters such as the size of the bit array 'm' and the number of hash functions 'k'. It's important to choose these parameters carefully based on the specific requirements of the application.Dynamic Updates: Bloom Filters are typically designed for static sets, and updating them dynamically (e.g., adding or removing elements) can be challenging. If dynamic updates are required, it's advisable to consider alternative data structures or modify the Bloom Filter accordingly.In summary, Bloom Filter is a powerful probabilistic data structure that offers efficient membership testing with space efficiency. However, it's crucial to understand its principles, limitations, and precautions to ensure its effective usage in various scenarios.中文版详解布隆过滤器的原理、使用场景和注意事项布隆过滤器是一种空间效率高的概率性数据结构，用于测试一个元素是否属于某个集合。

布隆过滤器的原理和应用场景布隆过滤器的概述布隆过滤器是一种空间效率非常高的概率型数据结构，用于判断一个元素是否在一个集合中。

它由布隆过滤器的位数组和哈希函数组成，可以高效地判断一个元素是否存在于集合中，但有一定的误判率。

布隆过滤器的原理布隆过滤器的主要原理是利用位数组和多个哈希函数来表示一个集合，并判断一个元素是否存在于集合中。

1.初始化：将位数组初始化为全0。

2.添加元素：对于要添加的元素，使用多个哈希函数计算出多个哈希值，然后将对应的位数组位置设为1。

3.判断元素：对于要判断的元素，同样使用多个哈希函数计算出多个哈希值，然后检查对应的位数组位置是否都是1。

若有任意一个位数组位置为0，则判定元素不存在于集合中；若全部位数组位置都为1，则判定元素可能存在于集合中。

布隆过滤器的优点布隆过滤器具有以下优点： - 空间效率高：布隆过滤器只需要占用很少的内存空间，比其他数据结构如散列表等要小得多。

- 查询效率高：布隆过滤器只需要进行位操作和哈希计算，所以查询效率非常高。

- 可并行处理：布隆过滤器的查询和插入操作可以并行处理，因为它们对位数组的操作没有依赖关系。

布隆过滤器的应用场景布隆过滤器在以下场景中具有较大的应用价值：1.网络爬虫中的URL去重：爬虫在抓取网页时，通常需要判断一个URL是否已经抓取过，布隆过滤器可以非常高效地进行URL去重。

2.邮件服务器中的垃圾邮件过滤：布隆过滤器可以帮助邮件服务器快速判断一封邮件是否是垃圾邮件，从而提高邮件过滤的效率。

3.分布式系统中的缓存穿透控制：布隆过滤器可以用于控制分布式系统中的缓存穿透问题，减轻数据库压力。

4.数据库查询缓存：布隆过滤器可以用于缓存数据库的部分查询结果，提高数据库查询效率。

布隆过滤器的误判率布隆过滤器的误判率是根据哈希函数的数量和位数组的大小决定的。

误判率主要取决于以下两个因素： - 哈希函数的数量：哈希函数越多，误判率越低，但算法的效率也会降低。

GoogleGuava中布隆过滤器的介绍和使⽤⼀、简介布隆过滤器（Bloom Filter）是⾮常经典的，以空间换时间的算法。

布隆过滤器由布隆在 1970 年提出。

它实际上是⼀个很长的⼆进制向量和⼀系列随机映射函数。

布隆过滤器可以⽤于检索⼀个元素是否在⼀个集合中。

它的优点是空间效率和查询时间都远远超过⼀般的算法，缺点是有⼀定的误识别率和删除困难。

⼆、实现原理布隆过滤器的核⼼实现是⼀个超⼤的位数组和⼏个哈希函数。

假设位数组的长度为 m，哈希函数的个数为 k。

以上图为例，具体的操作流程：假设集合⾥⾯有 3 个元素 {x, y, z}，哈希函数的个数为 3。

⾸先将位数组进⾏初始化，将⾥⾯每个位都设置位0。

对于集合⾥⾯的每⼀个元素，将元素依次通过 3 个哈希函数进⾏映射，每次映射都会产⽣⼀个哈希值，这个值对应位数组上⾯的⼀个点，然后将位数组对应的位置标记为 1。

查询 W 元素是否存在集合中的时候，同样的⽅法将 W 通过哈希映射到位数组上的 3 个点。

如果 3个点的其中有⼀个点不为 1，则可以判断该元素⼀定不存在集合中。

反之，如果 3 个点都为 1，则该元素可能存在集合中。

注意：此处不能判断该元素是否⼀定存在集合中，可能存在⼀定的误判率。

可以从图中可以看到：假设某个元素通过映射对应下标为 4、5、6 这 3 个点。

虽然这 3 个点都为 1，但是很明显这 3 个点是不同元素经过哈希得到的位置，因此这种情况说明元素虽然不在集合中，也可能对应的都是 1，这是误判率存在的原因。

1、布隆过滤器添加元素将要添加的元素给 k 个哈希函数得到对应于位数组上的 k 个位置将这 k 个位置设为 12、布隆过滤器查询元素将要查询的元素给 k 个哈希函数得到对应于位数组上的 k 个位置如果 k 个位置有⼀个为 0，则肯定不在集合中如果 k 个位置全部为 1，则可能在集合中3、布隆过滤器的优缺点优点相⽐于其它的数据结构，布隆过滤器在空间和时间⽅⾯都有巨⼤的优势。

浅析布隆过滤器（BloomFilter）的实现原理及应⽤⼀、什么情况下需要布隆过滤器？1、先来看⼏个⽐较常见的例⼦：字处理软件中，需要检查⼀个英语单词是否拼写正确在 FBI，⼀个嫌疑⼈的名字是否已经在嫌疑名单上在⽹络爬⾍⾥，⼀个⽹址是否被访问过yahoo, gmail 等邮箱垃圾邮件过滤功能 这⼏个例⼦有⼀个共同的特点：如何判断⼀个元素是否存在⼀个集合中？2、常规思路：数组链表树、平衡⼆叉树、TrieMap (红⿊树)哈希表 虽然上⾯描述的这⼏种数据结构配合常见的排序、⼆分搜索可以快速⾼效的处理绝⼤部分判断元素是否存在集合中的需求。

但是当集合⾥⾯的元素数量⾜够⼤，如果有500万条记录甚⾄1亿条记录呢？这个时候常规的数据结构的问题就凸显出来了。

数组、链表、树等数据结构会存储元素的内容，⼀旦数据量过⼤，消耗的内存也会呈现线性增长，最终达到瓶颈。

有的同学可能会问，哈希表不是效率很⾼吗？查询效率可以达到O(1)。

但是哈希表需要消耗的内存依然很⾼。

使⽤哈希表存储⼀亿个垃圾 email 地址的消耗？哈希表的做法： ⾸先，哈希函数将⼀个email地址映射成8字节信息指纹；考虑到哈希表存储效率通常⼩于50%（哈希冲突）；因此消耗的内存：8 * 2 * 1亿字节 = 1.6G 内存，普通计算机是⽆法提供如此⼤的内存。

这个时候，布隆过滤器（Bloom Filter）就应运⽽⽣。

在继续介绍布隆过滤器的原理时，先讲解下关于哈希函数的预备知识。

3、HashMap 的问题 讲述布隆过滤器的原理之前，我们先思考⼀下，通常你判断某个元素是否存在⽤的是什么？应该蛮多⼈回答 HashMap 吧，确实可以将值映射到 HashMap 的 Key，然后可以在 O(1) 的时间复杂度内返回结果，效率奇⾼。

但是 HashMap 的实现也有缺点，例如存储容量占⽐⾼，考虑到负载因⼦的存在，通常空间是不能被⽤满的，⽽⼀旦你的值很多例如上亿的时候，那 HashMap 占据的内存⼤⼩就变得很可观了。

布隆过滤器（BloomFilter）详解直观的说，bloom算法类似⼀个hash set，⽤来判断某个元素（key）是否在某个集合中。

和⼀般的hash set不同的是，这个算法⽆需存储key的值，对于每个key，只需要k个⽐特位，每个存储⼀个标志，⽤来判断key是否在集合中。

算法：1. ⾸先需要k个hash函数，每个函数可以把key散列成为1个整数2. 初始化时，需要⼀个长度为n⽐特的数组，每个⽐特位初始化为03. 某个key加⼊集合时，⽤k个hash函数计算出k个散列值，并把数组中对应的⽐特位置为14. 判断某个key是否在集合时，⽤k个hash函数计算出k个散列值，并查询数组中对应的⽐特位，如果所有的⽐特位都是1，认为在集合中。

优点：不需要存储key，节省空间缺点：1. 算法判断key在集合中时，有⼀定的概率key其实不在集合中2. ⽆法删除典型的应⽤场景：某些存储系统的设计中，会存在空查询缺陷：当查询⼀个不存在的key时，需要访问慢设备，导致效率低下。

⽐如⼀个前端页⾯的缓存系统，可能这样设计：先查询某个页⾯在本地是否存在，如果存在就直接返回，如果不存在，就从后端获取。

但是当频繁从缓存系统查询⼀个页⾯时，缓存系统将会频繁请求后端，把压⼒导⼊后端。

这是只要增加⼀个bloom算法的服务，后端插⼊⼀个key时，在这个服务中设置⼀次需要查询后端时，先判断key在后端是否存在，这样就能避免后端的压⼒。

布隆过滤器［1］（Bloom Filter）是由布隆（Burton Howard Bloom）在1970年提出的。

它实际上是由⼀个很长的⼆进制向量和⼀系列随机映射函数组成，布隆过滤器可以⽤于检索⼀个元素是否在⼀个集合中。

它的优点是空间效率和查询时间都远远超过⼀般的算法，缺点是有⼀定的误识别率（假正例False positives，即Bloom Filter报告某⼀元素存在于某集合中，但是实际上该元素并不在集合中）和删除困难，但是没有识别错误的情形（即假反例False negatives，如果某个元素确实没有在该集合中，那么Bloom Filter 是不会报告该元素存在于集合中的，所以不会漏报）。

浅谈布隆过滤器不知道从什么时候开始，本来默默⽆闻的布隆过滤器⼀下⼦名声⼤燥，仿佛⾝在互联⽹，做着开发的，⽆⼈不知，⽆⼈不晓，哪怕对技术不是很关⼼的⼩伙伴也听过它的名号。

我也花了不少时间去研究布隆过滤器，看了不少博客，⽆奈不是科班出⾝，⼜没有那么聪明的头脑，⼜⽐较懒...经过“放弃，拿起，放弃，拿起”的⽆限轮回，应该算是了解了布隆过滤器的核⼼思想，所以想给⼤家分享下。

布隆过滤器的应⽤我们先来看下布隆过滤器的应⽤场景，让⼤家知道神奇的布隆过滤器到底能做什么。

缓存穿透我们经常会把⼀部分数据放在Redis等缓存，⽐如产品详情。

这样有查询请求进来，我们可以根据产品Id直接去缓存中取数据，⽽不⽤读取数据库，这是提升性能最简单，最普遍，也是最有效的做法。

⼀般的查询请求流程是这样的：先查缓存，有缓存的话直接返回，如果缓存中没有，再去数据库查询，然后再把数据库取出来的数据放⼊缓存，⼀切看起来很美好。

但是如果现在有⼤量请求进来，⽽且都在请求⼀个不存在的产品Id，会发⽣什么？既然产品Id都不存在，那么肯定没有缓存，没有缓存，那么⼤量的请求都怼到数据库，数据库的压⼒⼀下⼦就上来了，还有可能把数据库打死。

虽然有很多办法都可以解决这问题，但是我们的主⾓是“布隆过滤器”，没错，“布隆过滤器”就可以解决（缓解）缓存穿透问题。

⾄于为什么说是“缓解”，看下去你就明⽩了。

⼤量数据，判断给定的是否在其中现在有⼤量的数据，⽽这些数据的⼤⼩已经远远超出了服务器的内存，现在再给你⼀个数据，如何判断给你的数据在不在其中。

如果服务器的内存⾜够⼤，那么⽤HashMap是⼀个不错的解决⽅案，理论上的时间复杂度可以达到O(1)，但是现在数据的⼤⼩已经远远超出了服务器的内存，所以⽆法使⽤HashMap，这个时候就可以使⽤“布隆过滤器”来解决这个问题。

但是还是同样的，会有⼀定的“误判率”。

什么是布隆过滤器布隆过滤器是⼀个叫“布隆”的⼈提出的，它本⾝是⼀个很长的⼆进制向量，既然是⼆进制的向量，那么显⽽易见的，存放的不是0，就是1。

图⽂解析布隆过滤器⼤⼩的算法公式⽬录1. 简介2. 应⽤场景2.1 缓存穿透2.2 判断某个数据是否在海量数据中存在3. HashMap的问题4. 理解布隆过滤器5. 根据布隆过滤器查询元素6. 可以删除么7. 如何选择哈希函数个数和布隆过滤器长度更多应⽤场景1. 简介客户端：这个key存在吗？服务器：不存在/不知道本质上，布隆过滤器是⼀种数据结构，是⼀种⽐较巧妙的概率型数据结构。

它的特点是⾼效地插⼊和查询。

但我们要检查⼀个key是否在某个结构中存在时，通过使⽤布隆过滤器，我们可以快速了解到「这个key⼀定不存在或者可能存在」。

相⽐于传统的List、Set、Map这些数据结构，它更加⾼效、占⽤的空间也越少，但是它返回的结果是概率性的，是不确切的。

布隆过滤器仅⽤于测试集合中的成员资格。

使⽤布隆过滤器的经典⽰例是减少对不存在的密钥的昂贵磁盘（或⽹络）查找。

正如我们看到的那样，布隆过滤器可以在O（k）恒定时间内搜索密钥，其中k是哈希函数的数量，测试密钥的不存在将⾮常快。

2. 应⽤场景2.1 缓存穿透为了提⾼访问效率，我们会将⼀些数据放在Redis缓存中。

当进⾏数据查询时，可以先从缓存中获取数据，⽆需读取数据库。

这样可以有效地提升性能。

在数据查询时，⾸先要判断缓存中是否有数据，如果有数据，就直接从缓存中获取数据。

但如果没有数据，就需要从数据库中获取数据，然后放⼊缓存。

如果⼤量访问都⽆法命中缓存，会造成数据库要扛较⼤压⼒，从⽽导致数据库崩溃。

⽽使⽤布隆过滤器，当访问不存在的缓存时，可以迅速返回避免缓存或者DB crash。

2.2 判断某个数据是否在海量数据中存在HBase中存储着⾮常海量数据，要判断某个ROWKEYS、或者某个列是否存在，使⽤布隆过滤器，可以快速获取某个数据是否存在。

但有⼀定的误判率。

但如果某个key不存在，⼀定是准确的。

3. HashMap的问题要判断某个元素是否存在其实⽤HashMap效率是⾮常⾼的。

Redis布隆过滤器1、布隆过滤器内容参考：1、数据结构布隆过滤器是⼀个BIT数组，本质上是⼀个数据，所以可以根据下标快速找数据2、哈希映射1、布隆需要记录见过的数据，这⾥的记录需要通过hash函数对数据进⾏hash操作，得到数组下标并存储在BIT 数组⾥记为1。

这样的记录⼀个数据只占⽤1BIT空间2、判断是否存在时：给布隆过滤器⼀个数据，进⾏hash得到下标，从BIT数组⾥取数据如果是1 则说明数据存在，如果是0 说明不存在3、精确度hash算法存在碰撞的可能，所以不同的数据可能hash为⼀个下标数据，故为了提⾼精确度就需要使⽤多个hash 算法标记⼀个数据，和增⼤BIT数组的⼤⼩也是因为如此，布隆过滤器判断为【数据存在】可能数据并不存在，但是如果判断为【数据不存在】那么数据就⼀定是不存在的。

4、例⼦下图映射 baidu字样到布隆过滤器中，⽤了三个不同的hash函数 3BIT 判断⼀个数据，BIT数组⼤⼩为8哈希函数返回 1、4、7.我们现在再存⼀个值 “tencent”，如果哈希函数返回 3、4、8 的话，图继续变为：以下 4 位置发⽣了hash碰撞5、如何选择哈希函数个数和布隆过滤器长度显然，过⼩的布隆过滤器很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的⽬的了。

布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越⼩。

另外，哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变⾼。

k 为哈希函数个数，m 为布隆过滤器长度，n 为插⼊的元素个数，p 为误报率。

6、不⽀持删除布隆过滤器只能插⼊数据判断是否存在，不能删除，⽽且只能保证【不存在】判断绝对准确以上不难看出如果给数组的每个BIT位上加⼀个计数器，插⼊的时候+1 删除的时候 –1 就可以实现删除。

但是加计数器的实现是有问题的：由于hash碰撞问题，布隆过滤器不能准确判断数据是否存在，就不能随意删除。