- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章布隆过滤器(bloom filter)及php和redis实现布隆过滤器的方法由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.
引言 。
在介绍布隆过滤器之前我们首先引入几个场景.
场景一 。
在一个高并发的计数系统中,如果一个key没有计数,此时我们应该返回0,但是访问的key不存在,相当于每次访问缓存都不起作用了。那么如何避免频繁访问数量为0的key而导致的缓存被击穿?
有人说, 将这个key的值置为0存入缓存不就行了吗?确实,这是一个好的方案。大部分情况我们都是这样做的,当访问一个不存在的key的时候,设置一个带有过期时间的标志,然后放入缓存。不过这样做的缺点也很明显,浪费内存和无法抵御随机key攻击.
场景二 。
在一个黑名单系统中,我们需要设置很多黑名单内容。比如一个邮件系统,我们需要设置黑名单用户,当判断垃圾邮件的时候,要怎么去做。比如爬虫系统,我们要记录下来已经访问过的链接避免下次访问重复的链接.
在邮件很少或者用户很少的情况下,我们用普通数据库自带的查询就能完成。在数据量太多的时候,为了保证速度,通常情况下我们会将结果缓存到内存中,数据结构用hash表。这种查找的速度是O(1),但是内存消耗也是惊人的。打个比方,假如我们要存10亿条数据,每条数据平均占据32个字节,那么需要的内存是64G,这已经是一个惊人的大小了.
一种解决思路 。
能不能有一种思路,查询的速度是O(1),消耗内存特别小呢?前辈门早就想出了一个很好的解决方案。由于上面说的场景判断的结果只有两种状态(是或者不是,存在或者不存在),那么对于所存的数据完全可以用位来表示!数据本身则可以通过一个hash函数计算出一个key,这个key是一个位置,而这个key所对的值就是0或者1(因为只有两种状态),如下图:
布隆过滤器原理 。
上面的思路其实就是布隆过滤器的思想,只不过因为hash函数的限制,多个字符串很可能会hash成一个值。为了解决这个问题,布隆过滤器引入多个hash函数来降低误判率.
下图表示有三个hash函数,比如一个集合中有x,y,z三个元素,分别用三个hash函数映射到二进制序列的某些位上,假设我们判断w是否在集合中,同样用三个hash函数来映射,结果发现取得的结果不全为1,则表示w不在集合里面.
布隆过滤器处理流程 。
布隆过滤器应用很广泛,比如垃圾邮件过滤,爬虫的url过滤,防止缓存击穿等等。下面就来说说布隆过滤器的一个完整流程,相信读者看到这里应该能明白布隆过滤器是怎样工作的.
第一步:开辟空间 。
开辟一个长度为m的位数组(或者称二进制向量),这个不同的语言有不同的实现方式,甚至你可以用文件来实现.
第二步:寻找hash函数 。
获取几个hash函数,前辈们已经发明了很多运行良好的hash函数,比如BKDRHash,JSHash,RSHash等等。这些hash函数我们直接获取就可以了.
第三步:写入数据 。
将所需要判断的内容经过这些hash函数计算,得到几个值,比如用3个hash函数,得到值分别是1000,2000,3000。之后设置m位数组的第1000,2000,3000位的值位二进制1.
第四步:判断 。
接下来就可以判断一个新的内容是不是在我们的集合中。判断的流程和写入的流程是一致的.
误判问题 。
布隆过滤器虽然很高效(写入和判断都是O(1),所需要的存储空间极小),但是缺点也非常明显,那就是会误判。当集合中的元素越来越多,二进制序列中的1的个数越来越多的时候,判断一个字符串是否在集合中就很容易误判,原本不在集合里面的字符串会被判断在集合里面.
数学推导 。
布隆过滤器原理十分简单,但是hash函数个数怎么去判断,误判率有多少?
假设二进制序列有m位,那么经过当一个字符串hash到某一位的概率为:
1m 。
也就是说当前位被反转为1的概率:
p(1)=1m 。
那么这一位没有被反转的概率为:
p(0)=1−1m 。
假设我们存入n各元素,使用k个hash函数,此时没有被翻转的概率为:
p(0)=(1−1m)nk 。
那什么情况下我们会误判呢,就是原本不应该被翻转的位,结果翻转了,也就是 。
p(误判)=1−(1−1m)nk 。
由于只有k个hash函数同时误判了,整体才会被误判,最后误判的概率为 。
p(误判)=(1−(1−1m)nk)k 。
要使得误判率最低,那么我们需要求误判与m、n、k之间的关系,现在假设m和n固定,我们计算一下k。可以首先看看这个式子:
(1−1m)nk 。
由于我们的m很大,通常情况下我们会用2^32来作为m的值。上面的式子中含有一个重要极限 。
limx→∞(1+1x)x=e 。
因此误判率的式子可以写成 。
p(误判)=(1−(e)−nk/m)k 。
接下来令t=−n/m,两边同时取对数,求导,得到:
p′1p=ln(1−etk)+klnet(−etk)1−etk 。
让p′=0,则等式后面的为0,最后整理出来的结果是 。
(1−etk)ln(1−etk)=etklnetk 。
计算出来的k为ln2mn,约等于0.693mn,将k代入p(误判),我们可以得到概率和m、n之间的关系,最后的结果 。
(1/2)ln2mn,约等于0.6185m/n 。
以上我们就得出了最佳hash函数个数以及误判率与mn之前的关系了.
下表是m与n比值在k个hash函数下面的误判率 。
m/n k k=1 k=2 k=3 k=4 k=5 k=6 k=7 k=8 2 1.39 0.393 0.400 3 2.08 0.283 0.237 0.253 4 2.77 0.221 0.155 0.147 0.160 5 3.46 0.181 0.109 0.092 0.092 0.101 6 4.16 0.154 0.0804 0.0609 0.0561 0.0578 0.0638 7 4.85 0.133 0.0618 0.0423 0.0359 0.0347 0.0364 8 5.55 0.118 0.0489 0.0306 0.024 0.0217 0.0216 0.0229 9 6.24 0.105 0.0397 0.0228 0.0166 0.0141 0.0133 0.0135 0.0145 10 6.93 0.0952 0.0329 0.0174 0.0118 0.00943 0.00844 0.00819 0.00846 11 7.62 0.0869 0.0276 0.0136 0.00864 0.0065 0.00552 0.00513 0.00509 12 8.32 0.08 0.0236 0.0108 0.00646 0.00459 0.00371 0.00329 0.00314 13 9.01 0.074 0.0203 0.00875 0.00492 0.00332 0.00255 0.00217 0.00199 14 9.7 0.0689 0.0177 0.00718 0.00381 0.00244 0.00179 0.00146 0.00129 15 10.4 0.0645 0.0156 0.00596 0.003 0.00183 0.00128 0.001 0.000852 16 11.1 0.0606 0.0138 0.005 0.00239 0.00139 0.000935 0.000702 0.000574 17 11.8 0.0571 0.0123 0.00423 0.00193 0.00107 0.000692 0.000499 0.000394 18 12.5 0.054 0.0111 0.00362 0.00158 0.000839 0.000519 0.00036 0.000275 19 13.2 0.0513 0.00998 0.00312 0.0013 0.000663 0.000394 0.000264 0.000194 20 13.9 0.0488 0.00906 0.0027 0.00108 0.00053 0.000303 0.000196 0.00014 21 14.6 0.0465 0.00825 0.00236 0.000905 0.000427 0.000236 0.000147 0.000101 22 15.2 0.0444 0.00755 0.00207 0.000764 0.000347 0.000185 0.000112 7.46e-05 23 15.9 0.0425 0.00694 0.00183 0.000649 0.000285 0.000147 8.56e-05 5.55e-05 24 16.6 0.0408 0.00639 0.00162 0.000555 0.000235 0.000117 6.63e-05 4.17e-05 25 17.3 0.0392 0.00591 0.00145 0.000478 0.000196 9.44e-05 5.18e-05 3.16e-05 26 18 0.0377 0.00548 0.00129 0.000413 0.000164 7.66e-05 4.08e-05 2.42e-05 27 18.7 0.0364 0.0051 0.00116 0.000359 0.000138 6.26e-05 3.24e-05 1.87e-05 28 19.4 0.0351 0.00475 0.00105 0.000314 0.000117 5.15e-05 2.59e-05 1.46e-05 29 20.1 0.0339 0.00444 0.000949 0.000276 9.96e-05 4.26e-05 2.09e-05 1.14e-05 30 20.8 0.0328 0.00416 0.000862 0.000243 8.53e-05 3.55e-05 1.69e-05 9.01e-06 31 21.5 0.0317 0.0039 0.000785 0.000215 7.33e-05 2.97e-05 1.38e-05 7.16e-06 32 22.2 0.0308 0.00367 0.000717 0.000191 6.33e-05 2.5e-05 1.13e-05 5.73e-06 。
php+Redis实现的布隆过滤器 。
由于Redis实现了setbit和getbit操作,天然适合实现布隆过滤器,redis也有布隆过滤器插件。这里使用php+redis实现布隆过滤器.
首先定义一个hash函数集合类,这些hash函数不一定都用到,实际上32位hash值的用3个就可以了,具体的数量可以根据你的位序列总量和你需要存入的量决定,上面已经给出最佳值.
接着就是连接redis来进行操作 。
上面定义的是一个抽象类,如果要使用,可以根据具体的业务来使用。比如下面是一个过滤重复内容的过滤器.
总结 。
以上所述是小编给大家介绍的布隆过滤器(bloom filter)及php和redis实现布隆过滤器的方法,希望对大家有所帮助! 。
原文链接:http://imhuchao.com/1271.html 。
最后此篇关于布隆过滤器(bloom filter)及php和redis实现布隆过滤器的方法的文章就讲到这里了,如果你想了解更多关于布隆过滤器(bloom filter)及php和redis实现布隆过滤器的方法的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
一. 简介 1.什么是bloom filter? Bloom filter 是由 Howard Bloom 在 1970 年提出的二进制向量数据结构,它具有很好的空间和时间效率,被用来检测一个元素是
如果我实现了只使用一种散列算法的布隆过滤器(例如 murmur),这是否仍被视为布隆过滤器? 例如,如果 a散列到 5 ,然后将设置过滤器的第 5 位。如 b散列到 1 ,然后将设置过滤器的第 1 位
上下文:我正在阅读有关 RocksDB 和 LSM 树的信息,根据我的理解,Bloom 过滤器用于避免所有存储级别中的项目检索的多个 I/O。我对此没有意见。 显然,挑战之一是布隆过滤器不能用于范围查
您好,在我的系统中将有一个主节点和 n 个从节点,其中主节点会将传入请求分发到其从节点之一。为了利用缓存内存内容,我想跟踪从属节点已经服务的最后 50 个请求(传入请求的哈希值)(假设最后 50 个请
我在 Guava v.11.0.1 中使用了 BloomFilter,当我的插入很大时,我似乎遇到了异常。我用 0.001 fpp 尝试了 1000 万,但失败了。 java.lang.Illegal
我一直在尝试实现我自己的(简单的)Bloom Filter,但一直坚持哈希,我理解多次对项目进行哈希并用索引填充位数组的概念。 但是,我在我的散列中看到了大量的冲突,我正在使用一种散列算法(我已经尝试
引言 在介绍布隆过滤器之前我们首先引入几个场景。 场景一 在一个高并发的计数系统中,如果一个key没有计数,此时我们应该返回0,但是访问的key不存在,相当于每次访问缓存都不起作用了。那么如何
布隆过滤器原理很简单:就是把一个字符串哈希成一个整数key,然后选取一个很长的比特序列,开始都是0,在key把此位置的0变为1;下次进来一个字符串,哈希之后的值key,如果在此比特位上的值也是1,那
使用 Guava 库创建布隆过滤器时,您需要提供一个漏斗和预期的插入次数(以及可选的所需误报率)。有没有办法设置布隆过滤器应该使用哪些哈希函数?如果无法设置哈希函数,默认使用什么? 布隆过滤器是 co
18.0 中的 Guava 布隆过滤器线程安全吗?换句话说,我可以让多个线程共享一个 Bloom Filter 实例并同时使用 myBloomInstance.mightContain 和 myBlo
我有一个使用 Reach 图形设置在 C# XNA 4.0 中编码的 Windows 平台游戏。我的项目基于 GameStateManagement 示例,但后来我向其中添加了 Bloom 和 spr
如何在iOS平台的应用中安装其他应用? 例如,在“Bloom”应用中,拉至底部,点击“PEAK”,会出现“Peek”店铺详情 View ,您可以在该 View 中下载“PEAK”应用。无需打开应用商店
我需要在 C# 中存储 4000 个固定大小(8 个字符)的字符串,但我不知道关于添加和检索项目的空间和时间最好使用什么:布隆过滤器、哈希表或字典?如果有人可以帮助我,请帮助我 最佳答案 在这个问题中
这个问题以前有人问过,但当时没有答案,所以我决定再问一次。 我需要用 C(不是 C++)高效地实现布隆过滤器。如果没有这样的东西可用,我不介意实现一个,如果提供一些很好的引用,这样它就不会占用我太多时
最近几天我阅读了很多关于使用 bloom 等进行后处理的文章,并且我能够通过一个单独的着色器运行这个纹理来实现渲染到纹理的功能。现在我对整个事情有一些疑问。 我必须同时渲染两者吗?场景和纹理放在全屏四
我又遇到了一个我自己似乎无法解决的僵局。我真的希望有人能帮助我。 我一直在尝试使用 GLSL 创建一个漂亮的小光晕效果,效果非常好。当我尝试在我的场景中加入一些移动的东西时,我注意到我忘记在渲染到它们
我有一个 Spark 作业,其最终输出是一个 Algebird 布隆过滤器,我需要在另一个 Spark 作业中重用这个布隆过滤器。有没有办法使用 Twitter Storehaus 将此布隆过滤器存储
我已经使用 OpenGL 和 GLSL 集成了bloom HDR 渲染......至少我认为!我不太确定结果。 我遵循了英特尔网站上的教程: https://software.intel.com/en
我正在关注这个 tutorial用于绽放效果。 我正在使用 Qt,我尝试渲染的场景由五个立方体和五个随机放置的灯组成,类似于这样。 不幸的是,当我尝试使用帧缓冲区时,渲染的场景完全是空的(只有背景颜色
Hadoop 新手...我有一系列 HDFS 目录,命名约定为 filename.seq。每个目录包含一个索引、数据和 bloom 文件。这些具有二进制内容并且似乎是 SequenceFiles(SE
我是一名优秀的程序员,十分优秀!