Bloomfilter

2.1. 概念为了缩小遍历汇合中的数据来确定查找的数据在不在该汇合中，能够采纳布隆过滤器来优化。布隆过滤器是一个概率数据结构，它无奈给出要找的数据的地位，只能给出要找的数据是否在外面，并且给出的后果可能会假阳性(false positives)，即通知查找的数据在该汇合外面，理论数据不在外面。布隆过滤器是由一个很长的bit数组和一系列哈希函数组成的。数组的每个元素都只占1bit空间，并且每个元素只能为0或1。布隆过滤器领有K个哈希函数，当一个元素要退出布隆过滤器时，会应用K个哈希函数对其进行K次计算，失去K个哈希值，并且依据失去的哈希值，在一维数组中把对应下标的值置位1。判断某个数是否在布隆过滤器中，就对该元素进行K次哈希计算，失去的值在位数组中判断每个元素是否都为1，如果每个元素都为1，就阐明这个值可能在布隆过滤器中，须要进一步确认。注：Bloom filter只能插入与查找，不能删除。：一个8-bit bloom filter，插入RZA，通过两个hash函数找到两个bit位，如果该bit位是0，则将其变为1；如果曾经是1，则该bit位不变。再插入GZA。 ：查找Raekwon，两个hash失去的bit位有一个0，则示意Raekwon不存在表中。查找ODB，两个hash到的bit为都是1，则示意ODB在表中，但理论不存在(即假阳性)，这其实并不影响，最多到hash表中再查一下。 2.2. 误报率哈希函数越多，那么一个Key就能够用数组中的多个地位来标记，整体抵触的概率越低。然而在这个数组中的各个Bit位，同时也会被其余数据标记位来影响。如果Hash数量给的过多，那么每个Key都会有多个Bit位来标记它是否存在。极其状况下，过多的Hash数量，可能导致整个数组中大量的 bit位被置为1。那么在这种状况下，误报率就会越高。同时，如果在hash个数确定的状况下，数组长度越长，数据量越小也越稠密。假如Hash函数以等概率条件抉择并设置Bit Array中的某一位，m是该位数组的大小(即m个Bit位)，k是Hash函数的个数，那么位数组中某一特定的位在进行元素插入时的Hash操作中没有被置位为"1"的概率是：\( 1-1/m \)。在所有k次 Hash操作后，该位仍没有被置"1"的概率是:\( (1-1/m)^k \)。如果插入了n个元素，那么某一位仍没有被置"1"的概率是:\( (1-1/m)^{kn} \)，因此该位为"1"的概率是:\( 1-(1-1/m)^{kn} \)。当初检测某一元素是否在该汇合中，表明某个元素是否在汇合中所需的k个地位都依照如上的办法设置为"1"，然而该办法可能会使算法谬误的认为某一本来不在汇合中的元素却被检测为在该汇合中(False Positives)，该概率由以下公式确定：\( [1-(1-1/m)^{kn}]^k\approx (1-e^{-kn/m})^k \)。随着m(位数组大小)的减少，假阳性的概率会降落，同时随着插入元素个数n的减少，假阳性的的概率又会回升。对于给定的m和n，Hash函数个数k能够由下推出：令\( a=n/m \)，对\( (1-e^{-kn/m})^k \)求导： $$\begin{aligned}y &=\left(1-e^{-a x}\right)^{x} \\\ln y &=x \ln \left(1-e^{-a x}\right)\end{aligned}$$ $$\begin{array}{c}\frac{1}{y} y^{\prime}=\ln \left(1-e^{-a x}\right)+x \frac{a e^{-a x}}{1-e^{-a x}} \\y^{\prime}=\left[\ln \left(1-e^{-a x}\right)+x \frac{a e^{-a x}}{1-e^{-a x}}\right]\left(1-e^{-a x}\right)^{x}\end{array}$$ 而\( (1-e^{-ax})^x >0\)，因而： $$\begin{array}{l}\ln \left(1-e^{-a x}\right)+x \frac{a e^{-a x}}{1-e^{-a x}}=0 \\\ln \left(1-e^{-a x}\right)=-a x \frac{e^{-a x}}{1-e^{-a x}}\end{array}$$ ...

布隆过滤器(BloomFilter)是一种大家在学校没怎么学过，但在计算机很多畛域十分罕用的数据结构，它能够用来高效判断某个key是否属于一个汇合，有极高的插入和查问效率(O(1))，也十分省存储空间。当然它也不是白璧无瑕，它也有本人的毛病，接下来追随我一起具体理解下BloomFilter的实现原理，以及它优缺点、利用场景，最初再看下Google guava包中BloomFilter的实现，并比照下它和HashSet在不同数据量下内存空间的应用状况。 学过数据结构的人都晓得，在计算机领域咱们常常通过就义空间换工夫，或者就义工夫换空间，BloomFilter给了咱们一种新的思路——就义准确率换空间。是的，BloomFilter不是100%精确的，它是有可能有误判，但相对不会有漏判断，说艰深点就是，BloomFilter有可能错杀坏蛋，但不会放过任何一个好人。BloomFilter最大的长处就是省空间，毛病就是不是100%精确，这点当然和它的实现原理无关。 BloomFilter的原理在解说BloomFilter的实现前，咱们先来理解下什么叫Bitmap(位图)，先给你一道《编程珠玑》上的题目。 给你一个有100w个数的汇合S，每个数的数据大小都是0-100w，有些数据反复呈现，这就意味着有些数据可能都没呈现过，让你以O(n)的工夫复杂度找出0-100w之间没有呈现在S中的数，尽可能减少内存的应用。既然工夫复杂度都限度是O(N)了，意味着咱们不能应用排序了，咱们能够开一个长为100w的int数组来标记下哪些数字呈现过，在就标1，不在标0。但对于每个数来说咱们只须要晓得它在不在，只是0和1的区别，用int(32位)有点太节约空间了，咱们能够按二进制位来用每个int，这样一个int就能够标记32个数，空间占用率一下子缩小到原来的1/32，于是咱们就有了位图，Bitmap就是用n个二进制位来记录0-m之间的某个数有没有呈现过。 Bitmap的局限在于它的存储数据类型无限，只能存0-m之间的数，其余的数据就存不了了。如果咱们想存字符串或者其余数据怎么办？其实也简略，只须要实现一个hash函数，将你要存的数据映射到0-m之间就行了。这里假如你的hash函数产生的映射值是平均的，咱们来计算下一个m位的Bitmap到底能存多少数据? 当你在Bitmap中插入了一个数后，通过hash函数计算它在Bitmap中的地位并将其置为1，这时任意一个地位没有被标为1的概率是： $$1 - \frac{1}{m}$$ 当插入n个数后，这个概率会变成： $$(1 - \frac{1}{m})^n$$ 所以任意一个地位被标记成1的概率就是： $$P_1 = 1 - (1 - \frac{1}{m})^n$$ 这时候你判断某个key是否在这个汇合S中时，只须要看下这个key在hash在Bitmap上对应的地位是否为1就行了，因为两个key对应的hash值可能是一样的，所以有可能会误判，你之前插入了a，然而hash(b)==hash(a)，这时候你判断b是否在汇合S中时，看到的是a的后果，实际上b没有插入过。 从下面公式中能够看出有 $P_1$ 的概率可能会误判，尤其当n比拟大时这个误判概率还是挺大的。 如何缩小这个误判率？咱们最开始是只取了一个hash函数，如果说取k个不同的hash函数呢！咱们每插入一个数据，计算k个hash值，并对k地位为1。在查找时，也是求k个hash值，而后看其是否都为1，如果都为1必定就能够认为这个数是在汇合S中的。 问题来了，用k个hash函数，每次插入都可能会写k位，更耗空间，那在同样的m下，误判率是否会更高呢？咱们来推导下。 在k个hash函数的状况下，插入一个数后任意一个地位仍旧是0的概率是： $$(1 - \frac{1}{m})^k$$ 插入n个数后任意一个地位仍旧是0的概率是： $$(1 - \frac{1}{m})^{kn}$$ 所以可知，插入n个数后任意一个地位是1的概率是 $$1 - (1 - \frac{1}{m})^{kn}$$ 因为咱们用是用k个hash独特来判断是否是在汇合中的，可知当用k个hash函数时其误判率如下。它肯定是比下面1个hash函数时误判率要小（尽管我不会证实） $$\left(1-\left[1-\frac{1}{m}\right]^{k n}\right)^{k} < (1 - \left[1 - \frac{1}{m}\right]^n)$$ 维基百科也给出了这个误判率的近似公式（尽管我不晓得是怎么来的，所以这里就间接援用了） $$\left(1-\left[1-\frac{1}{m}\right]^{k n}\right)^{k} \approx\left(1-e^{-k n / m}\right)^{k}$$ 到这里，咱们从新创造了Bloomfilter，就是这么简略，说白了Bloomfilter就是在Bitmap之上的扩大而已。对于一个key，用k个hash函数映射到Bitmap上，查找时只须要对要查找的内容同样做k次hash映射，通过查看Bitmap上这k个地位是否都被标记了来判断是否之前被插入过，如下图。 通过公式推导和理解原理后，咱们曾经晓得Bloomfilter有个很大的毛病就是不是100%精确，有误判的可能性。然而通过选取适合的bitmap大小和hash函数个数后，咱们能够把误判率降到很低，在大数据流行的时代，适当就义准确率来缩小存储耗费还是很值得的。 除了误判之外，BloomFilter还有另外一个很大的毛病 __只反对插入，无奈做删除__。如果你想在Bloomfilter中删除某个key，你不能间接将其对应的k个位全副置为0，因为这些地位有可能是被其余key共享的。基于这个毛病也有一些反对删除的BloomFilter的变种，适当就义了空间效率，感兴趣能够自行搜寻下。 如何确定最优的m和k？晓得原理后再来理解下怎么去实现，咱们在决定应用Bloomfilter之前，须要晓得两个数据，一个是要存储的数量n和预期的误判率p。bitmap的大小m决定了存储空间的大小，hash函数个数k决定了计算量的大小，咱们当然都心愿m和k都越小越好，如何计算二者的最优值，咱们大略来推导下。（备注：推导过程来自Wikipedia） 由上文可知，误判率p为 $$p \approx \left(1-e^{-k n / m}\right)^{k} \ (1)$$ ...

前言最近在研究布隆过滤器（如果不了解什么是布隆过滤器的，推荐看如何判断一个元素在亿级数据中是否存在？），发现Guava提供了封装好的类，但是只能单机使用，一般现在的应用都是部署在分布式系统的，所以想找个可以在分布式系统下使用的布隆过滤器，找了半天只找到一个基于redis开发的模块项目ReBloom，但是这个是需要额外安装的，而且文档里只说了怎么在docker下运行，没研究过docker所以放弃了。后来找到一篇博客讲怎么利用布隆过滤器统计消息未读数的（博客地址不记得了，是一位淘宝同学写的），博客最后放了一份整合redis和bloomFilter的代码demo，详见BloomFilter.java，看了下实现比较简单，但是使用方式不是我想要的，所以参考着自己整理了一份。BloomFilterHelperpackage com.doodl6.springmvc.service.cache.redis;import com.google.common.base.Preconditions;import com.google.common.hash.Funnel;import com.google.common.hash.Hashing;public class BloomFilterHelper<T> { private int numHashFunctions; private int bitSize; private Funnel<T> funnel; public BloomFilterHelper(Funnel<T> funnel, int expectedInsertions, double fpp) { Preconditions.checkArgument(funnel != null, “funnel不能为空”); this.funnel = funnel; bitSize = optimalNumOfBits(expectedInsertions, fpp); numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize); } int[] murmurHashOffset(T value) { int[] offset = new int[numHashFunctions]; long hash64 = Hashing.murmur3_128().hashObject(value, funnel).asLong(); int hash1 = (int) hash64; int hash2 = (int) (hash64 >>> 32); for (int i = 1; i <= numHashFunctions; i++) { int nextHash = hash1 + i * hash2; if (nextHash < 0) { nextHash = ~nextHash; } offset[i - 1] = nextHash % bitSize; } return offset; } /** * 计算bit数组长度 / private int optimalNumOfBits(long n, double p) { if (p == 0) { p = Double.MIN_VALUE; } return (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2))); } /* * 计算hash方法执行次数 */ private int optimalNumOfHashFunctions(long n, long m) { return Math.max(1, (int) Math.round((double) m / n * Math.log(2))); }}BloomFilterHelper做的事情很简单，其实大部分代码都是来源于Guava库里面的 ...

bloompygithub:bloompyAn implementation of 4 kinds of Bloom Filter in Python3.bloompy includes the standard BloomFilter,CountingBloomFilter,ScalableBloomFilter,ScalableCountingBloomFilter.It’s Updated from pybloom.Installationpip install bloompyUseThere’s 4 kinds of BloomFilter you can use by bloompy.standard bloom filterthe standard one can only query or add elements in it.>>> import bloompy>>> bf = bloompy.BloomFilter(error_rate=0.001,element_num=103)# query the status of the element inside the bf immediately # and add it into the bf.False returned indicates the element# does not inside the filter.>>> bf.add(1) False>>> bf.add(1)True>>> 1 in bfTrue>>> bf.exists(1)True>>> bf.add([1,2,3])False>>> bf.add([1,2,3])True>>> [1,2,3] in bfTrue>>> bf.exists([1,2,3])True# store the bf into a file.>>> bf.tofile(‘filename.suffix’)# recover a bf from a file.Auto recognize which kind of filters it is.>>> recovered_bf = bloompy.get_filter_fromfile(‘filename.suffix’)# or you can use a classmethod ‘fromfile’ of the BloomFilter Class to get# a BloomFilter instance from a file.Same as other kind of filter Classes .>>> recovered_bf = bloompy.BloomFilter.fromfile(‘filename.suffix’)# return the total number of the elements inside the bf.>>> bf.count2# the capacity of the current filter.>>> bf.capacity1000# the bits array of the current filter. >>> bf.bit_arraybitarray(‘00….’)# the total length of the bitarray.>>> bf.bit_num14400# the hash seeds inside the filter.# they are prime numbers by default.It’s modifiable.>>> bf.seeds[2, 3, 5, 7, 11,…]# the amount of hash functions >>> bf.hash_num10counting bloom filterThe counting bloom filter is a subclass of the standard bloom filter.But it supports the delete operation.It is set inside that 4bits represent a bit of the standard bf. So it costs more momery than the standard bf,it’s 4 times the standard one.>>> import bloompy>>> cbf = bloompy.CountingBloomFilter(error_rate=0.001,element_num=103)# same as the standard bf at add operation.>>> cbf.add(12)False>>> cbf.add(12)True>>> 12 in cbfTrue>>> cbf.count1# query the status of the element inside the cbf immediately # if the element inside the cbf,delete it.>>> cbf.delete(12)True>>> cbf.delete(12)False>>> 12 in cbfFalse>>> cbf.count0# recover a cbf from a file.Same as the bf.>>> recovered_cbf = bloompy.CountingBloomFilter.fromfile(‘filename.suffix’)You can do any operations of the BloomFilter on it as well.scalable bloom filterAuto increase the capacity of the filter if the current amount of inserted elements is up to the limits.It’s set 2times the pre capacity inside by default.>>> import bloompy>>> sbf = bloompy.ScalableBloomFilter(error_rate=0.001,initial_capacity=103)# at first, the sbf is at 1000 capacity limits.>>> len(sbf)0>>> 12 in sbfFalse>>> sbf.add(12)False>>> 12 in sbf True>>> len(sbf)1>>> sbf.filters[<bloompy.BloomFilter object at 0x000000000B6F5860>]>>> sbf.capacity1000# when the amount of inserting elements surpass the limits 1000.# the sbf appends a new filter inside it which capacity 2times 1000.>>> for i in range(1000): sbf.add(i)>>> 600 in sbfTrue>>> len(sbf)2>>> sbf.filters[<bloompy.BloomFilter object at 0x000000000B6F5860>, <bloompy.BloomFilter object at 0x000000000B32F748>]>>> sbf.capacity3000# recover a sbf from a file.Same as bf.>>> recovered_sbf = bloompy.ScalableBloomFilter.fromfile(‘filename.suffix’)You can do any operations of the BloomFilter on it as well.scalable counting bloom filterIt’s a subclass of the ScalableBloomFilter.But it supports the delete operation.You can do any operations of the ScalableBloomFilter on it as well.>>> import bloompy>>> scbf = bloompy.SCBloomFilter(error_rate=0.001,initial_capacity=103)>>> scbf.add(1)False>>> 1 in scbfTrue>>> scbf.delete(1)True>>> 1 in scbfFalse>>> len(scbf)1>>> scbf.filters[<bloompy.CountingBloomFilter object at 0x000000000B6F5828>]# add elements in sbf to make it at a capacity limits>>> for i in range(1100): scbf.add(i)>>> len(scbf)2>>> scbf.filters[<bloompy.CountingBloomFilter object at 0x000000000B6F5828>, <bloompy.CountingBloomFilter object at 0x000000000B6F5898>]# recover a scbf from a file.Same as bf.>>> recovered_scbf = bloompy.SCBloomFilter.fromfile(‘filename.suffix’)Store and recoverAs shown in the standard bloom filter.You can store a filter in 2 ways:classmethod ‘fromfile’get_filter_fromfile() if you do clearly know that there is a BloomFilter stored in a file.you can recover it with: bloompy.BloomeFilter.fromfile(‘filename.suffix) or it’s a CountingBloomFilter inside it:bloompy.CountingBloomFilter.fromfile(‘filename.suffix)Same as others. But if you don’t know what kind of filter it is stored in the file.Use:bloompy.get_filter_fromfile(‘filename.suffix’) It will auto recognize the filter stored inside a file.Then you can do something with it. ...

前言最近有朋友问我这么一个面试题目：现在有一个非常庞大的数据，假设全是 int 类型。现在我给你一个数，你需要告诉我它是否存在其中(尽量高效)。需求其实很清晰，只是要判断一个数据是否存在即可。但这里有一个比较重要的前提：非常庞大的数据。常规实现先不考虑这个条件，我们脑海中出现的第一种方案是什么？我想大多数想到的都是用 HashMap 来存放数据，因为它的写入查询的效率都比较高。写入和判断元素是否存在都有对应的 API，所以实现起来也比较简单。为此我写了一个单测，利用 HashSet 来存数据（底层也是 HashMap ）；同时为了后面的对比将堆内存写死：-Xms64m -Xmx64m -XX:+PrintHeapAtGC -XX:+HeapDumpOnOutOfMemoryError 为了方便调试加入了 GC 日志的打印，以及内存溢出后 Dump 内存。 @Test public void hashMapTest(){ long star = System.currentTimeMillis(); Set<Integer> hashset = new HashSet<>(100) ; for (int i = 0; i < 100; i++) { hashset.add(i) ; } Assert.assertTrue(hashset.contains(1)); Assert.assertTrue(hashset.contains(2)); Assert.assertTrue(hashset.contains(3)); long end = System.currentTimeMillis(); System.out.println(“执行时间：” + (end - star)); }当我只写入 100 条数据时自然是没有问题的。还是在这个基础上，写入 1000W 数据试试：执行后马上就内存溢出。可见在内存有限的情况下我们不能使用这种方式。实际情况也是如此；既然要判断一个数据是否存在于集合中，考虑的算法的效率以及准确性肯定是要把数据全部 load 到内存中的。Bloom Filter基于上面分析的条件，要实现这个需求最需要解决的是如何将庞大的数据 load 到内存中。而我们是否可以换种思路，因为只是需要判断数据是否存在，也不是需要把数据查询出来，所以完全没有必要将真正的数据存放进去。伟大的科学家们已经帮我们想到了这样的需求。Burton Howard Bloom 在 1970 年提出了一个叫做 Bloom Filter（中文翻译：布隆过滤）的算法。它主要就是用于解决判断一个元素是否在一个集合中，但它的优势是只需要占用很小的内存空间以及有着高效的查询效率。所以在这个场景下在合适不过了。Bloom Filter 原理下面来分析下它的实现原理。官方的说法是：它是一个保存了很长的二级制向量，同时结合 Hash 函数实现的。听起来比较绕，但是通过一个图就比较容易理解了。如图所示：首先需要初始化一个二进制的数组，长度设为 L（图中为 8），同时初始值全为 0 。当写入一个 A1=1000 的数据时，需要进行 H 次 hash 函数的运算（这里为 2 次）；与 HashMap 有点类似，通过算出的 HashCode 与 L 取模后定位到 0、2 处，将该处的值设为 1。A2=2000 也是同理计算后将 4、7 位置设为 1。当有一个 B1=1000 需要判断是否存在时，也是做两次 Hash 运算，定位到 0、2 处，此时他们的值都为 1 ，所以认为 B1=1000 存在于集合中。当有一个 B2=3000 时，也是同理。第一次 Hash 定位到 index=4 时，数组中的值为 1，所以再进行第二次 Hash 运算，结果定位到 index=5 的值为 0，所以认为 B2=3000 不存在于集合中。整个的写入、查询的流程就是这样，汇总起来就是：对写入的数据做 H 次 hash 运算定位到数组中的位置，同时将数据改为 1 。当有数据查询时也是同样的方式定位到数组中。一旦其中的有一位为 0 则认为数据肯定不存在于集合，否则数据可能存在于集合中。所以布隆过滤有以下几个特点：只要返回数据不存在，则肯定不存在。返回数据存在，但只能是大概率存在。同时不能清除其中的数据。第一点应该都能理解，重点解释下 2、3 点。为什么返回存在的数据却是可能存在呢，这其实也和 HashMap 类似。在有限的数组长度中存放大量的数据，即便是再完美的 Hash 算法也会有冲突，所以有可能两个完全不同的 A、B 两个数据最后定位到的位置是一模一样的。这时拿 B 进行查询时那自然就是误报了。删除数据也是同理，当我把 B 的数据删除时，其实也相当于是把 A 的数据删掉了，这样也会造成后续的误报。基于以上的 Hash 冲突的前提，所以 Bloom Filter 有一定的误报率，这个误报率和 Hash 算法的次数 H，以及数组长度 L 都是有关的。自己实现一个布隆过滤算法其实很简单不难理解，于是利用 Java 实现了一个简单的雏形。public class BloomFilters { /** * 数组长度 / private int arraySize; /* * 数组 / private int[] array; public BloomFilters(int arraySize) { this.arraySize = arraySize; array = new int[arraySize]; } /* * 写入数据 * @param key / public void add(String key) { int first = hashcode_1(key); int second = hashcode_2(key); int third = hashcode_3(key); array[first % arraySize] = 1; array[second % arraySize] = 1; array[third % arraySize] = 1; } /* * 判断数据是否存在 * @param key * @return / public boolean check(String key) { int first = hashcode_1(key); int second = hashcode_2(key); int third = hashcode_3(key); int firstIndex = array[first % arraySize]; if (firstIndex == 0) { return false; } int secondIndex = array[second % arraySize]; if (secondIndex == 0) { return false; } int thirdIndex = array[third % arraySize]; if (thirdIndex == 0) { return false; } return true; } /* * hash 算法1 * @param key * @return / private int hashcode_1(String key) { int hash = 0; int i; for (i = 0; i < key.length(); ++i) { hash = 33 * hash + key.charAt(i); } return Math.abs(hash); } /* * hash 算法2 * @param data * @return / private int hashcode_2(String data) { final int p = 16777619; int hash = (int) 2166136261L; for (int i = 0; i < data.length(); i++) { hash = (hash ^ data.charAt(i)) * p; } hash += hash << 13; hash ^= hash >> 7; hash += hash << 3; hash ^= hash >> 17; hash += hash << 5; return Math.abs(hash); } /* * hash 算法3 * @param key * @return */ private int hashcode_3(String key) { int hash, i; for (hash = 0, i = 0; i < key.length(); ++i) { hash += key.charAt(i); hash += (hash << 10); hash ^= (hash >> 6); } hash += (hash << 3); hash ^= (hash >> 11); hash += (hash << 15); return Math.abs(hash); }}首先初始化了一个 int 数组。写入数据的时候进行三次 hash 运算，同时把对应的位置置为 1。查询时同样的三次 hash 运算，取到对应的值，一旦值为 0 ，则认为数据不存在。实现逻辑其实就和上文描述的一样。下面来测试一下，同样的参数：-Xms64m -Xmx64m -XX:+PrintHeapAtGC @Test public void bloomFilterTest(){ long star = System.currentTimeMillis(); BloomFilters bloomFilters = new BloomFilters(10000000) ; for (int i = 0; i < 10000000; i++) { bloomFilters.add(i + “”) ; } Assert.assertTrue(bloomFilters.check(1+"")); Assert.assertTrue(bloomFilters.check(2+"")); Assert.assertTrue(bloomFilters.check(3+"")); Assert.assertTrue(bloomFilters.check(999999+"")); Assert.assertFalse(bloomFilters.check(400230340+"")); long end = System.currentTimeMillis(); System.out.println(“执行时间：” + (end - star)); }执行结果如下：只花了 3 秒钟就写入了 1000W 的数据同时做出来准确的判断。当让我把数组长度缩小到了 100W 时就出现了一个误报，400230340 这个数明明没在集合里，却返回了存在。这也体现了 Bloom Filter 的误报率。我们提高数组长度以及 hash 计算次数可以降低误报率，但相应的 CPU、内存的消耗就会提高；这就需要根据业务需要自行权衡。Guava 实现刚才的方式虽然实现了功能，也满足了大量数据。但其实观察 GC 日志非常频繁，同时老年代也使用了 90%，接近崩溃的边缘。总的来说就是内存利用率做的不好。其实 Google Guava 库中也实现了该算法，下面来看看业界权威的实现。-Xms64m -Xmx64m -XX:+PrintHeapAtGC @Test public void guavaTest() { long star = System.currentTimeMillis(); BloomFilter<Integer> filter = BloomFilter.create( Funnels.integerFunnel(), 10000000, 0.01); for (int i = 0; i < 10000000; i++) { filter.put(i); } Assert.assertTrue(filter.mightContain(1)); Assert.assertTrue(filter.mightContain(2)); Assert.assertTrue(filter.mightContain(3)); Assert.assertFalse(filter.mightContain(10000000)); long end = System.currentTimeMillis(); System.out.println(“执行时间：” + (end - star)); }也是同样写入了 1000W 的数据，执行没有问题。观察 GC 日志会发现没有一次 fullGC，同时老年代的使用率很低。和刚才的一对比这里明显的要好上很多，也可以写入更多的数据。源码分析那就来看看 Guava 它是如何实现的。构造方法中有两个比较重要的参数，一个是预计存放多少数据，一个是可以接受的误报率。我这里的测试 demo 分别是 1000W 以及 0.01。Guava 会通过你预计的数量以及误报率帮你计算出你应当会使用的数组大小 numBits 以及需要计算几次 Hash 函数 numHashFunctions 。这个算法计算规则可以参考维基百科。put 写入函数真正存放数据的 put 函数如下：根据 murmur3_128 方法的到一个 128 位长度的 byte[]。分别取高低 8 位的到两个 hash 值。再根据初始化时的到的执行 hash 的次数进行 hash 运算。bitsChanged |= bits.set((combinedHash & Long.MAX_VALUE) % bitSize);其实也是 hash取模拿到 index 后去赋值 1.重点是 bits.set() 方法。其实 set 方法是 BitArray 中的一个函数，BitArray 就是真正存放数据的底层数据结构。利用了一个 long[] data 来存放数据。所以 set() 时候也是对这个 data 做处理。在 set 之前先通过 get() 判断这个数据是否存在于集合中，如果已经存在则直接返回告知客户端写入失败。接下来就是通过位运算进行位或赋值。get() 方法的计算逻辑和 set 类似，只要判断为 0 就直接返回存在该值。mightContain 是否存在函数前面几步的逻辑都是类似的，只是调用了刚才的 get() 方法判断元素是否存在而已。总结布隆过滤的应用还是蛮多的，比如数据库、爬虫、防缓存击穿等。特别是需要精确知道某个数据不存在时做点什么事情就非常适合布隆过滤。这段时间的研究发现算法也挺有意思的，后续应该会继续分享一些类似的内容。如果对你有帮助那就分享一下吧。本问的示例代码参考这里：https://github.com/crossoverJie/JCSprout你的点赞与分享是对我最大的支持 ...