5.7 布隆过滤器 - 数据结构 - 机器学习
#daohang ul li t,.reed .riqi,a.shangg,a.xiatt,a.shangg:hover,a.xiatt:hover,a.shang,a.xiat,a.shang:hover,a.xiat:hover,.reed-pinglun-anniu,span.now-page,#daohangs-around,#caidan-tubiao,#daohangs,#daohangs li,#btnPost{background-color:#D10B04;}
.dinglanyou1 h3{border-bottom:3px solid #D10B04;}
#dibuer{border-top:2px solid #D10B04;}.cebianlan .rongqi h3{border-bottom:1px solid #D10B04;}
#edtSearch{border:1px solid #D10B04;}
#daohang .zuo ul li{border-right:1px solid #;}
#daohang ul li t a{border-top:1px solid #;border-right:1px solid #D10B04;}
#daohang ul li t a:hover{border-right:1px solid #;}
#daohang .you ul li a:hover,#daohang .zuo ul li a:hover,.reed-pinglun-anniu:hover{background-color:#;}
a:hover,.reed h6 a:hover,#dibuer a:hover,.reed .riqiding,.cebianlan .rongqi li a:hover,#pinglun-liebiao ul.fubens li.depth-1 dl dd span.shu a,#pinglun-liebiao ul.fubens li.depth-1 dl dd span.huifuliuyan a:hover,.reed-biaoti h6 span{color:#D10B04;}
.reed .kan a{color:#0A0AF5;}.reed .kan a:hover{color:#D10101;}
@media screen and (max-width:1492px){a.shang,a.xiat{background:none;}
a.xiat:hover,a.shang:hover{background-color:#f9f9f9;background-image:none;text-decoration:none;}}
var _hmt = _hmt || [];(function() { var hm = document.createElement("script"); hm.src = "https://hm.baidu.com/hm.js?b19db5ba3b437a9e8698d2bc8fc64334"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(hm, s);})();
var _hmt = _hmt || [];
(function() {
var hm = document.createElement("script");
hm.src = "https://hm.baidu.com/hm.js?b19db5ba3b437a9e8698d2bc8fc64334";
var s = document.getElementsByTagName("script")[0];
s.parentNode.insertBefore(hm, s);
})();
var _hmt = _hmt || [];
(function() {
var hm = document.createElement("script");
hm.src = "https://hm.baidu.com/hm.js?2d748c9763cfc72fb7d1ccab29f0770d";
var s = document.getElementsByTagName("script")[0];
s.parentNode.insertBefore(hm, s);
})();
var _hmt = _hmt || [];
(function() {
var hm = document.createElement("script");
hm.src = "https://hm.baidu.com/hm.js?f6d451f3f1be23f3abf240c64c469c1b";
var s = document.getElementsByTagName("script")[0];
s.parentNode.insertBefore(hm, s);
})();
(function() {
var s = "_" + Math.random().toString(36).slice(2);
document.write('
');
(window.slotbydup = window.slotbydup || []).push({
id: "u3646201",
container: s
});
})();
(function() {
var s = "_" + Math.random().toString(36).slice(2);
document.write('
');
(window.slotbydup = window.slotbydup || []).push({
id: "u3646162",
container: s
});
})();
5.7 布隆过滤器
1326 人参与 2018年09月30日 10:01 分类 : 区块链精品文章 评论
布隆过滤器
（Bloom Filter）于1970年由Burton Howard Bloom在论文《Space/Time Trade-offs in
Hash Coding with Allowable
Errors》中提出。布隆过滤器是一种基于Hash的高效查找结构，能够快速（常数时间内）回答“某个元素是否在一个集合内”的问题。
布隆过滤器因为其高效性大量应用于网络和安全领域，例如信息检索（BigTable和HBase）、垃圾邮件规则、注册管理等。
1.基于Hash的快速查找
在布隆过滤器之前，先来看基于Hash的快速查找算法。在前面的讲解中我们提到，Hash可以将任意内容映射到一个固定长度的字符串，而且不同内容映射到相同串的概率很低。因此，这就构成了一个很好的“内容→索引”的生成关系。
试想，如果给定一个内容和存储数组，通过构造Hash函数，让映射后的Hash值总不超过数组的大小，则可以实现快速的
基于内容的查找。例如，内容“hello
world”的Hash值如果是“100”，则存放到数组的第100个单元上去。如果需要快速查找任意内容，如“hello
world”字符串是否在存储系统中，只需要将其在常数时间内计算Hash值，并用Hash值查看系统中对应元素即可。该系统“完美地”实现了常数时间内
的查找。
然而，令人遗憾的是，当映射后的值限制在一定范围（如总数组的大小）内时，会发现Hash冲突的概率会变高，而且范围越
小，冲突概率越大。很多时候，存储系统的大小又不能无限扩展，这就造成算法效率的下降。为了提高空间利用率，后来人们基于Hash算法的思想设计出了布隆
过滤器结构。
2.更高效的布隆过滤器
布隆过滤器采用了多个Hash函数来提高空间利用率。对同一个给定输入来说，多个Hash函数计算出多个地址，分别在位串的这些地址上标记为1。进行查找时，进行同样的计算过程，并查看对应元素，如果都为1，则说明较大概率是存在该输入。如图5-4所示。
布隆过滤器相对单个Hash算法查找，大大提高了空间利用率，可以使用较少的空间来表示较大集合的存在关系。
实际上，无论是Hash算法，还是布隆过滤器，基本思想是一致的，都是基于内容的编址。Hash函数存在冲突，布隆过滤器也存在冲突。这就造成了两种方法都存在着误报（false positive）的情况，但绝对不会漏报（false negative）。
布隆过滤器在应用中误报率往往很低，例如，在使用7个不同Hash函数的情况下，记录100万个数据，采用2 MB大小的位串，整体的误判率将低于1%。而传统的Hash查找算法的误报率将接近10%。
来源：我是码农 ，转载请保留出处和链接！
本文链接：http://www.54manong.com/?id=958
(function() {
var s = "_" + Math.random().toString(36).slice(2);
document.write('
');
(window.slotbydup = window.slotbydup || []).push({
id: "u3646208",
container: s
});
})();
(function() {
var s = "_" + Math.random().toString(36).slice(2);
document.write('
');
(window.slotbydup = window.slotbydup || []).push({
id: "u3646147",
container: s
});
})();
window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdPic":"","bdStyle":"0","bdSize":"16"},"share":{},"image":{"viewList":["qzone","tsina","tqq","renren","weixin"],"viewText":"分享到：","viewSize":"16"},"selectShare":{"bdContainerClass":null,"bdSelectMiniList":["qzone","tsina","tqq","renren","weixin"]}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];
区块链是什么 微信号：qq444848023 QQ号：444848023
加入【我是码农】QQ群：864689844（加群验证：我是码农）
<< 上一篇 下一篇 >>
(function() {
var s = "_" + Math.random().toString(36).slice(2);
document.write('
');
(window.slotbydup = window.slotbydup || []).push({
id: "u3646186",
container: s
});
})();
(function() {
var s = "_" + Math.random().toString(36).slice(2);
document.write('
');
(window.slotbydup = window.slotbydup || []).push({
id: "u3646175",
container: s
});
})();
搜索
网站分类
标签列表
最近发表
(function(){
var bp = document.createElement('script');
var curProtocol = window.location.protocol.split(':')[0];
if (curProtocol === 'https'){
bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';
}
else{
bp.src = 'http://push.zhanzhang.baidu.com/push.js';
}
var s = document.getElementsByTagName("script")[0];
s.parentNode.insertBefore(bp, s);
})();
全站首页 |
数据结构 |
区块链 |
大数据 |
机器学习 |
物联网和云计算 |
面试笔试
var cnzz_protocol = (("https:" == document.location.protocol) ? "https://" : "http://");document.write(unescape("%3Cspan id='cnzz_stat_icon_1276413723'%3E%3C/span%3E%3Cscript src='" + cnzz_protocol + "s23.cnzz.com/z_stat.php%3Fid%3D1276413723%26show%3Dpic1' type='text/javascript'%3E%3C/script%3E"));本站资源大部分来自互联网，版权归原作者所有！
jQuery(document).ready(function($){
/* prepend menu icon */
$('#daohangs-around').prepend('
');
/* toggle nav */
$("#caidan-tubiao").on("click", function(){
$("#daohangs").slideToggle();
$(this).toggleClass("active");
});
});
收藏 | 0 点赞 | 0
评论专区