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)$$ ...