下载文档原格式
布隆使用技巧布隆是一种常用的数据结构，用于快速判断一个元素是否存在于一个集合中。
布隆过滤器的核心是一个位数组和一组哈希函数，我们可以根据需要设置位数组的大小和哈希函数的个数。
布隆过滤器的使用技巧主要包括以下几点：1. 设置合适的位数组大小：布隆过滤器的位数组越大，误判的概率越小，但是所占的空间也会增加。
因此，在使用布隆过滤器之前，需要根据数据量和误判的容忍程度来合理设置位数组的大小。
2. 选择合适的哈希函数：哈希函数的设计对布隆过滤器的性能有着重要的影响。
一个好的哈希函数应该具有均匀性，能够将不同的元素散列到位数组中的不同位置。
常用的哈希函数包括MD5、SHA-1、SHA-256等。
根据数据的特点和需求，选择适合的哈希函数可以提高布隆过滤器的效果。
3. 注意冲突问题：布隆过滤器在判断一个元素是否存在时，有可能会产生误判。
这是因为多个元素可能被哈希到位数组中的同一个位置上。
为了减少误判，可以增加位数组的大小和哈希函数的个数，提高布隆过滤器的容量和准确性。
4. 处理哈希冲突：当多个元素被哈希到位数组中的同一个位置上时，需要采取一定的策略来处理哈希冲突。
一种常用的方法是使用链表或者树结构来存储相同位置上的元素，避免数据的丢失和误判。
5. 动态调整位数组大小：由于布隆过滤器是用来判断一个元素是否存在的，而不是用来存储元素的，因此可以根据实际情况动态调整位数组的大小。
当位数组的使用率达到一定的阈值时，可以重新设置位数组的大小，以节省空间和提高性能。
总的来说，布隆过滤器是一种高效的数据结构，用于判断一个元素是否存在于一个集合中。
在使用布隆过滤器时，需要根据实际情况设置合适的位数组大小和哈希函数个数，处理哈希冲突，动态调整位数组大小等，以提高布隆过滤器的性能和准确性。
布隆过滤器的原理与使⽤⼀、算法介绍布隆过滤器是⼀种多哈希函数映射的快速查找算法，通常⽤于在⼤数据量场景下快速判断数据存在性。
该算法通过牺牲正确性从⽽在空间和时间上都有不错的效率。
⼆、算法原理当⼀个元素被加⼊集合时，通过N个散列函数将这个元素映射成⼀个位图中的N个点，将它们置为1。
判断某个元素是否存在时，通过这些点是不是都是1即可：如果这些点有任何⼀个0，则⽬标元素⼀定不在；如果都是1，则⽬标元素很可能在。
例如，⼀个集合中只存在⼀个apple 元素，其经过三个哈希函数计算映射在位图中三个位，此时判断orange是否存在于集合中，同样经过三个哈希函数计算，我们发现有⼀位为0，所以orange⼀定不存在于集合中。
三、算法实现构造⼀个布隆过滤器需要⼀个给定长度的位图和N个哈希函数，那么问题来了，这个位图到底要多⼤？到底要多少个哈希函数呢？这⾥引⼊两个公式：根据预估数据量n以及误判率fpp，位图⼤⼩m的计算⽅式：根据预估数据量n以及位图长度m，哈希函数个数k的计算⽅式：根据公式我们可以明显看出，当数据量越⼤、误判率越低，则位图长度越⼤。
关于m和k的计算，我们可以看⼀下Guava中的实现：/*** 计算hash函数个数* n，预期数据量* m，位图长度*/@VisibleForTestingstatic int optimalNumOfHashFunctions(long n, long m) {return Math.max(1, (int)Math.round((double)m / (double)n * Math.log(2.0D)));}/*** 计算位图长度* n，预估的数据量* p，误判率*/@VisibleForTestingstatic long optimalNumOfBits(long n, double p) {if (p == 0.0D) {p = 4.9E-324D;}return (long)((double)(-n) * Math.log(p) / (Math.log(2.0D) * Math.log(2.0D)));}解决了位图长度和哈希函数个数的计算问题，接下来我们看看哈希函数选取问题，⼀般情况下我们都需要三个甚⾄更多的哈希函数，我们如果真要去准备这些函数那就太⿇烦了，这⾥我们可以参考如下论⽂：https:///home/pete/pub/bloom-filters-verification.pdf这篇论⽂提出了⼀种算法，把原本需要N个哈希函数的计算转化成了两个哈希值的运算，完美地解决了这个问题。
布隆过滤器快速判断元素是否存在的数据结构布隆过滤器（Bloom Filter）是一种快速判断元素是否存在的数据结构，它通过位数组和一系列哈希函数来实现这一目标。
布隆过滤器在大规模数据集中判断元素的存在性能优于传统的查找算法，且具有较低的空间复杂度。
一、布隆过滤器的基本原理布隆过滤器的基本原理包括初始化、插入元素和判断元素存在性三个步骤。
1. 初始化：布隆过滤器使用一个位数组（bit array）为基础数据结构，同时包含多个哈希函数。
位数组的长度通常为m位，初始时全部初始化为0。
2. 插入元素：当需要将一个元素加入到布隆过滤器中时，首先使用哈希函数对元素进行计算，将其映射到位数组中的多个位置上，并将这些位置的值设置为1。
3. 判断元素存在性：当需要判断一个元素是否存在于布隆过滤器中时，同样使用哈希函数对该元素进行计算，然后在位数组中查找对应的位置的值。
若所有位置上的值都为1，则元素可能存在于布隆过滤器中；若存在任一位置的值为0，则元素一定不存在于布隆过滤器中。
二、布隆过滤器的应用场景布隆过滤器适用于需要快速判断元素存在性，但对判断结果的精确性要求不高的场景。
它主要应用于大规模数据的快速查找、缓存击穿和垃圾邮件过滤等领域。
1. 大规模数据的快速查找：在海量数据集中，通过布隆过滤器可以快速判断某个元素是否存在，从而避免了昂贵的磁盘或数据库查询操作。
在搜索引擎、数据库等场景中，布隆过滤器可以用来过滤掉一部分明显不存在的数据，从而提高查询效率。
2. 缓存击穿的防范：当缓存中不存在某个元素时，为了防止大量请求同时查询数据库，可以使用布隆过滤器来判断元素是否一定不存在于缓存中。
如果布隆过滤器判断元素不存在，则可以提前返回给用户“数据不存在”的结果。
3. 垃圾邮件过滤：在垃圾邮件过滤中，布隆过滤器可以用来存储垃圾邮件的特征，比如发件人、邮件主题等信息。
当新的邮件到达时，通过布隆过滤器可以快速判断该邮件是否为垃圾邮件，从而进行相应的处理。
布隆过滤器的误判率布隆过滤器是一种数据结构，用于判断一个元素是否存在于一个集合中。
它可以高效地过滤掉不符合条件的元素，从而减少后续操作的时间复杂度。
然而，布隆过滤器并不是完美的，它存在一定的误判率。
一、布隆过滤器的基本原理布隆过滤器由一个位数组和多个哈希函数构成。
首先，将位数组初始化为0。
当一个元素要被添加到布隆过滤器中时，经过多个哈希函数的计算，得到多个哈希值。
根据这些哈希值，将位数组中对应的位置设置为1。
当判断一个元素是否在布隆过滤器中时，同样经过多个哈希函数的计算得到多个哈希值，如果有任何一个哈希值对应的位数组位置为0，则该元素一定不在布隆过滤器中；如果所有哈希值对应的位数组位置都为1，则有可能该元素在布隆过滤器中。
二、误判率的定义与影响因素误判率也被称为"假阳性率"，即判断一个元素在布隆过滤器中但实际上并不在的概率。
误判率受到以下两个因素的影响：1.哈希函数的个数：哈希函数的个数越多，误判率越低。
因为随着哈希函数个数的增加，每个元素对应的位数组位置被置为1的概率也会增加，从而提高了判断正确的准确性。
2.位数组的大小：位数组的大小越大，误判率越低。
因为随着位数组大小的增加，每个元素对应的位数组位置被置为1的概率也会增加，从而提高了判断正确的准确性。
三、如何降低误判率虽然误判率无法完全避免，但可以通过以下方式来降低误判率：1.增加哈希函数的个数：通过增加哈希函数的个数，可以提高元素对应的位数组位置被置为1的概率，从而降低误判率。
然而，哈希函数的个数不能任意增加，需要权衡时间和空间的开销，选择合适的个数。
2.增大位数组的大小：通过增大位数组的大小，可以提高元素对应的位数组位置被置为1的概率，从而降低误判率。
然而，位数组的大小也需要根据实际情况进行合理选择，避免占用过多的内存空间。
3.合理设计哈希函数：合理设计哈希函数可以减少冲突的概率，从而降低误判率。
常用的哈希函数有MD5、SHA-1等，选择适合的哈希函数可以提高布隆过滤器的准确性。
Redis之布隆过滤器BloomFilter【基本原理】每个布隆过滤器对应到 Redis 底层的数据结构就是⼀个⼤型的位数组和⼀系列的⽆偏哈希函数（所谓⽆偏就是能够把元素的哈希值算得⽐较均匀）：向布隆过滤器中添加键值对时，会使⽤这⼀系列哈希函数分别对键名进⾏哈希运算，然后将得到的整数索引值与位数组长度进⾏取模运算得到最终索引位置，再把位数组的这⼏个索引位都置为 1，这就完成了 bf.add 操作。
向布隆过滤器查询指定键名是否存在时，和 bf.add ⼀样，也会把哈希后的索引位置都算出来，看看位数组中这⼏个索引位的值是否都为 1，只要有⼀个位为 0，则说明布隆过滤器中这个键名不存在。
如果都为 1，也并不能说明这个键名就⼀定存在，只是很有可能存在，因为这些位被置为 1 可能是其它键名哈希运算时出现哈希冲突所致（概率很低，但是存在）。
如果这个位数组⽐较稀疏，判断正确的概率就会很⼤，如果这个位数组⽐较稠密，判断正确的概率就会降低，因为出现哈希冲突的概率会提⾼，但是相对整体⽽⾔依然是很⼩的⽐例。
【空间与误差率】Redis还提供了⾃定义参数的bf.实际使⽤时，如果需要的话，可以通过在 bf.add 之前执⾏ bf.reserve 指令⾃定义布隆过滤器的参数，这个指令⽀持三个参数：key：指定键名；error_rate：错误率，默认是 0.01，即 1%，你可以将其调⼩，但是错误率越低，所需要的集合容量就越⼤，占⽤的存储空间就越⼤；initial_size：初始化的集合容量（集合中存放的元素数量），默认是 100，该值越⼤，错误率越低，但所需的存储空间也就越⼤，反之该值越⼩，所需的存储空间越⼩，但错误率越⾼。
注意：如果key已经存在（Redis默认使⽤的bf中error_rate为0.01，initial_size为100），使⽤bf.reserve时会报错的：2. ⿊名单校验 识别垃圾邮件，只要发送者在⿊名单中的，就识别为垃圾邮件。
布隆过滤器在数据去重中的应用在数据处理中，数据去重是一项非常重要的任务。
因为重复数据会对数据的分析和应用造成很大的影响，尤其当数据量非常大时，去重任务显得格外复杂。
为了解决这一问题，学术界和业界研究并发展了一系列算法技术，其中布隆过滤器是一种比较常见的算法技术。
布隆过滤器是由布隆在1970年提出的一种基于哈希的数据结构。
它可以快速判断一个元素是否在一个集合中，并且具有高效的空间和时间复杂度。
一般来说，布隆过滤器由一个二进制向量和一组哈希函数组成，这组哈希函数可以将元素映射为二进制向量的若干个位置，每个位置上的值为1。
在添加元素时，将元素经过哈希函数的处理后，将对应的位置的值设为1。
在查询元素时，对元素进行哈希处理，然后查看对应的位置上的值是否为1，如果值为1，则表明元素可能在集合中，如果值为0，则表明元素一定不在集合中。
布隆过滤器的优势在于空间占用比较少，尤其是对于大规模的数据集合来说，它只需要占用很少的空间就能够完成去重任务，而且查询速度非常快，因为它并不需要将所有的元素都遍历一遍才能找到目标元素。
但是布隆过滤器也存在一些缺点。
最大的问题在于误判率比较高，也就是说可能会将不属于集合中的元素误判为属于集合中的元素。
这是由于哈希函数本身的性质所决定的，因为哈希函数是一种信息压缩和抽象的过程，所以必然会存在信息损失和映射冲突的问题，这就会导致误判率比较高。
另外，布隆过滤器是一个单向的数据结构，也就是说一旦添加的元素无法删除，因为删除一个元素会影响到其他元素哈希函数的映射位置，所以无法进行删除操作。
针对布隆过滤器的缺点，学术界和业界也提出了一些解决方案。
其中比较常见的一种是使用多个布隆过滤器进行去重任务。
具体的做法是将数据分成若干部分，然后对每一部分分别建立一个布隆过滤器，最终将所有的布隆过滤器的结果合并起来，再进行去重操作。
这样可以有效地降低误判率，并且也可以解决删除问题。
但是相对而言，使用多个布隆过滤器的空间和时间复杂度都会有所增加，还需要进行多次哈希操作，因此需要权衡利弊来选择合适的解决方案。
布隆过滤器（BloomFilter）从入门到出土文章目录•••ooooo问题引入想象一下遇到下面的场景你会如何处理：•手机号是否重复注册•用户是否参与过某秒杀活动•有人恶意伪造请求大量id 查询不存在的记录，此时缓存未命中，如何避免缓存穿透我们如果让这样的数据直接全部去查询数据库，用后台数据库硬扛的话，那好了，缓存穿透等着你，如果压力并不大可以使用此方法，保持简单即可。
我们对“暴力法”进行下一步改进：用list/set/tree 维护一个元素集合，判断元素是否在集合内，时间复杂度或空间复杂度会比较高。
如果是微服务的话可以用 redis 中的 list/set 数据结构, 数据规模非常大此方案的内存容量要求可能会非常高。
这些场景有个共同点，可以将问题抽象为：如何高效判断一个元素不在集合中？那么有没有一种更好方案能达到时间复杂度和空间复杂双优呢？这就引出了布隆过滤器，他要干的就是解决“高效判断一个元素不在集合中”这件事。
布隆过滤器（Bloom Filter）布隆过滤器概念布隆过滤器（英语：Bloom Filter）是 1970 年由布隆提出的。
它实际上是一个很长的二进制向量和一系列随机映射函数。
布隆过滤器可以用于检索一个元素是否在一个集合中，它的优点是空间效率和查询时间都远远超过一般的算法。
划重点！：一种算法（也可以说是一种思想，他不是一个组件、插件，我们可以根据这个思想去实现这种过滤器），实现是一个很长的二进制向量和一系列随机映射函数，用于检索一个元素是否在集合中。
布隆过滤器作用布隆过滤器可以用很低的代价，估算出数据是否真实存在。
例如：给用户推荐新闻时，要去掉重复的新闻，就可以利用布隆过滤器，判断该新闻是否已经推荐过。
有人进行恶意查询时，此时布隆过滤器就能充当拦截器对其进行拦截。
布隆过滤器的核心包括两部分：1.一个大型的位数组；2.若干个不一样的哈希函数，每个哈希函数都能将哈希值算的比较均匀。
布隆过滤器的工作原理：1.添加key时，每个哈希函数都利用这个key计算出一个哈希值，再根据哈希值计算一个位置，并将位数组中这个位置的值设置为1。
字符串转数字的hash函数－布隆过滤器布隆过滤器（Bloom Filter）是1970年由布隆提出的。
它实际上是⼀个很长的向量和⼀系列随机映射函数。
布隆过滤器可以⽤于检索⼀个元素是否在⼀个集合中。
它的优点是空间效率和查询时间都⽐⼀般的算法要好的多，缺点是有⼀定的误识别率和删除困难。
基本概念如果想要判断⼀个元素是不是在⼀个集合⾥，⼀般想到的是将所有元素保存起来，然后通过⽐较确定。
，树等等数据结构都是这种思路. 但是随着集合中元素的增加，我们需要的存储空间越来越⼤，检索速度也越来越慢(O(n),O(logn))。
不过世界上还有⼀种叫作散列表（⼜叫，Hash table）的数据结构。
它可以通过⼀个将⼀个元素映射成⼀个位阵列（Bit array）中的⼀个点。
这样⼀来，我们只要看看这个点是不是1就可以知道集合中有没有它了。
这就是布隆过滤器的基本思想。
优点相⽐于其它的数据结构，布隆过滤器在空间和时间⽅⾯都有巨⼤的优势。
布隆过滤器存储空间和插⼊/查询时间都是。
另外, 相互之间没有关系，⽅便由硬件并⾏实现。
布隆过滤器不需要存储元素本⾝，在某些对保密要求⾮常严格的场合有优势。
布隆过滤器可以表⽰全集，其它任何数据结构都不能。
缺点但是布隆过滤器的缺点和优点⼀样明显。
误算率是其中之⼀。
随着存⼊的元素数量增加，误算率随之增加。
常见的补救办法是建⽴⼀个⼩的⽩名单，存储那些可能被误判的元素。
但是如果元素数量太少，则使⽤散列表⾜矣。
另外，⼀般情况下不能从布隆过滤器中删除元素。
我们很容易想到把位列阵变成整数数组，每插⼊⼀个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。
然⽽要保证安全的删除元素并⾮如此简单。
⾸先我们必须保证删除的元素的确在布隆过滤器⾥⾯. 这⼀点单凭这个过滤器是⽆法保证的。
另外计数器回绕也会造成问题。
在降低误算率⽅⾯，有不少⼯作，使得出现了很多布隆过滤器的变种。
基本的介绍到这，下⾯是介绍字符串转数字的⼀些hash函数，算法⼤概有如下⼏种：BKDRHashAPHashDJBHashJSHashRSHashSDBMHashPJWHashELFHash使⽤⽅法如下var bling = require("bling-hashes");var hash = bling.bkdr("Hello world!"); ///< 501511565。
布隆过滤器公式全文共四篇示例，供读者参考第一篇示例：布隆过滤器（Bloom Filter）是一种用于检索一个元素是否位于一个集合中的数据结构，它具有高效的查询速度和占用空间较小的特点。
布隆过滤器的原理是利用多个哈希函数和一个足够大的位数组来表示一个集合，当一个元素被加入到布隆过滤器时，经过多次哈希后将对应的位设置为1；当查询某个元素是否存在于布隆过滤器时，对该元素进行多次哈希获取对应的位，如果全部对应的位都为1，则说明该元素可能存在于布隆过滤器中，反之则一定不存在。
布隆过滤器的优势在于它可以在有限的空间内实现接近常数时间的元素查询，因此被广泛应用于大规模数据集合的去重、缓存命中判断等方面。
布隆过滤器也存在一定的缺陷，例如不支持元素的删除操作，且存在一定的误判率。
因此在实际应用中需根据具体问题的特点来选择是否使用布隆过滤器。
布隆过滤器的公式主要涉及到三个关键参数：位数组大小m、哈希函数个数k和预期的误判率p。
这三个参数之间存在一定的权衡关系，可以根据具体需求来选择合适的参数取值。
下面将介绍一下关于布隆过滤器公式的相关内容。
一、位数组大小m位数组的大小m决定了布隆过滤器所能表示的集合的大小。
位数组的大小m越大，表示的集合范围越大，同时可以容纳更多的元素；但是也意味着需要更多的存储空间。
通常情况下，可以通过计算公式来确定位数组的大小m，一般取值为m = -n * ln(p) / (ln(2) ^ 2)，其中n为预期插入的元素个数，p为预期的误判率。
二、哈希函数个数k哈希函数的个数k决定了布隆过滤器的性能，一般情况下，哈希函数的个数越多，误判率越低，但是计算的开销也会增加。
通常情况下，可以通过计算公式来确定哈希函数的个数k，一般取值为k = (m / n) * ln(2)。
三、预期的误判率p以上就是关于布隆过滤器公式的相关介绍，通过合理选择位数组大小m、哈希函数个数k和预期的误判率p，可以更好地设计和应用布隆过滤器，提高数据查询的效率和准确性。
通过实例解析布隆过滤器⼯作原理及实例布隆过滤器布隆过滤器是⼀种数据结构，⽐较巧妙的概率型数据结构（probabilistic data structure），特点是⾼效地插⼊和查询，可以⽤来告诉你 “⼀定不存在或者可能存在”。
相⽐于传统的 List、Set、Map 等数据结构，它更⾼效、占⽤空间更少，但是缺点是其返回的结果是概率性的，⽽不是确切的。
布隆过滤器的⼯作原理假设⼀个长度为m的bit类型的数组，即数组中每个位置只占⼀个bit，每个bit只有两种状态：0，1，所有bit的初始状态都为0。
再假设⼀共有k个哈希函数，这些函数的输出域⼤于或者等于m，并且这些哈希函数，彼此之间相互独⽴，每个哈希函数计算出来的结果是独⽴的，可能相同也可能不相同，对每⼀个计算出来的结果都对m取余（%m），然后再将数组下标位置置为1。
我们这⾥假设m为13,k为3的布隆过滤器，来看看布隆过滤器的⼯作原理：当我们要映射⼀个值到布隆过滤器时，⾸先计算三个哈希函数的值，然后对13取余，映射到对应位中，图中映射到2，6，10，这样我们就完成了⼀个值的映射。
那么怎么判断⼀个值是否存在，当⼀个值输⼊时，通过三个哈希函数，然后取余，我们就可以得到对应的三个位置，我们只需要判断这三个位置是否都为1，如果都为1，则该值存储，反之不存在。
但是有⼀个特殊情况，前⾯说了不同的哈希函数可能计算可能相同也可能不相同，⽽且不同的哈希函数对不同的值计算出来的值可能⼀样，这就造成⼀个结果，⼀个值通过哈希和取余得到的位置，早就被其它值给置1了，当我们存储的值过多，⽽这个bit数组过⼩，都会造成这种情况更多的发⽣，⼀个值明明不存在，⽽它的所有位置早就被其它不同值置1，造成了误判，这⾥就对布隆过滤器提出了⼀个指标：失误率p。
在同样数据规模下，不同⼤⼩的bit数组及不同数量k的哈希函数对误判率的结果：如何选取最合适的m（bit数组的⼤⼩）及k（哈希函数的数量），在已知n（需要映射的值得数量）及失误率p的情况下：m的选取：k的选取：给个例⼦：假设n=100亿，p=0.01%通过公式计算出来m=19.19n，向上取整位20n，即2000亿个bit，也就是25gb。
