BloomFilte布隆过滤器简介
一、简介
布隆过滤器(BloomFilter)是一种比较巧妙的概率型数据结构(probabilistic data structure),它是1970年由布隆提出的一种空间空间效率很高的随机数据结构。它利用位数组很简洁地表示一个集合,并判断一个元素是否属于这个集合。一个空的布隆过滤器有长度为M比特的bit数组构成,且所有位都初始化0。一个元素通过K个不同的hash函数随机散列到bit数组的K个位置上,K必须远小于M。K和M的大小由错误率(falsepositiverate)决定。布隆过滤器能够准确判断一个元素不在集合内,但只能判断一个元素可能在集合内。
布隆过滤器存储空间和插入/查询时间都是常数,可以高效地插入和查询。另外, Hash 函数相互之间没有关系,方便由硬件并行实现。布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势。布隆过滤器特点是,可以用来确认“某样东西一定不存在或者可能存在”。相比于传统的 List、Set、Map 等数据结构,它更高效、占用空间更少,但是缺点是其返回的结果是概率性的,而不是确切的。
Google 著名的分布式数据库 Bigtable 使用了布隆过滤器来查找不存在的行或列,以减少磁盘查找的IO次数。Squid 网页代理缓存服务器在 cache digests 中使用了也布隆过滤器。在很多Key-Value系统中也使用了布隆过滤器来加快查询过程,如 Hbase,Accumulo,Leveldb,一般而言,Value 保存在磁盘中,访问磁盘需要花费大量时间,然而使用布隆过滤器可以快速判断某个Key对应的Value是否存在,因此可以避免很多不必要的磁盘IO操作,只是引入布隆过滤器会带来一定的内存消耗。
二、布隆过滤器相关要素的关系
当向一个集合S中添加元素x使用布隆过滤器进行过滤时,x经过k个散列函数后,在M中得到k个位置,然后,将这k个位置的值设置为1。如果要判断x元素是否在集合S中:x经过k个散列函数后得到k个位置的值,如果这k个值中间存在为0的,说明元素x不在集合中。如果M中的k个位置全为1,则有可能这个元素在这个集合中,也有可能是其他一个或多个元素插入的时候将这k个位置的值置为1了。
如果要在应用中使用布隆过滤器,则要考虑如下要素:
布隆过滤器的长度该设置为多少;
该设计多少个散列函数,每个散列函数怎么设计;
允许的散列结果完全重复率是多少。
假设要处理的数据集合的个数是n,散列函数的个数是k,散列结果重复率为p,布隆过滤器数组的位数为m。则最优位数m和最优函数个数k的计算公式如下:
上述公式的推导过程请参考《详解布隆过滤器的原理,使用场景和注意事项》。
从上述公式可知,只要处理数据的集合数量确认和重复率确认,即可以获得过滤器的数组位数和散列函数的个数。除了设置合适的k和m值外,每个散列函数也必须仔细设计。首先是所有散列函数必须相互独立,没有任何关系,其次是函数输出的值范围足够宽,要尽可能降低输出值的冲突。
跟老猿学Python、学5G!
最新文章
- 记一次proc_open没有开启心得感悟
- Android联系人数据库
- 经典的javascript函数实例,css的. #区别
- 在代码中设置IE9的默认文档模式
- 史上最全系列Android开发环境搭建
- 能产生粒子效果的CAEmitterLayer
- stage划分
- VS2012窗口及编辑文本框背景颜色变黑
- js控制TR的显示隐藏
- ios开发小技巧之提示音播放与震动
- 【LeetCode 99】Recover Binary Search Tree
- linux 查看当前所在目录的全路径
- Android开发 侧边滑动菜单栏SlidingMenu结合Fragment
- httpmime-session 会话保持
- 【产品体验】eyepetizer开眼
- CentOS7 定时检测进程占用内存大小,执行重启进程操作(xjl456852原创)
- jsbin本地部署
- template.helper()方法
- 简述ADO.NET命名空间
- 工作小结:xml文件导入到oracle
热门文章
- XML转换成TXT行数据的Java程序
- 使用 c++ 模板显示实例化解决模板函数声明与实现分离的问题
- Pycharm激活码亲测有效,2020Pycharm最新激活码免费分享~
- tp3.2关闭debug save方法执行失败
- hive 下载和导入数据 hive -e
- 使用jQuery简单实现返回顶部的一个小案例
- Effective Modern C++ ——条款2 条款3 理解auto型别推导与理解decltype
- linux nf_conntrack 连接跟踪机制 3-hook
- linux文件增删拷(touch/mkdir/cp/mv/rm)
- Bad magic number ImportError in python