如何在海量数据中判断某个数据是否存在？

<section class="xmt-style-block" data-tools="新媒体排版"><section class="RankEditorr"><p><img class="" data-ratio="0.10555555555555556" src="https://img.haomeiwen.com/i11065549/d88c7ee24b94fe8c" data-type="gif" data-w="720" /></p></section></section><p><br /></p><p><br /></p><p >这是一道面试题：<strong>如何在海量数据（如亿级数据）中判断某个数据是否存在？</strong><br /></p><p ><br /></p><p >回想一下，在java中我们可以使用列表、集合等数据结构来存放数据，如hashmap，然后判断某个数据是否存在，但在此问题中显然不适用，因为上亿的数据在内存较小的计算机中无法存放。<br /></p><p ><br /></p><p >通常我们有以下解决思路：<br /></p><ol class=" list-paddingleft-2" ><li><p >将海量数据分散存储到多个文件中去，依次将每个文件载入内存进行判定；<br /></p></li><li><p >使用多台机器进行分布式计算，每台机器完成各自任务；</p></li><li><p >使用布隆过滤器（Bloom Filter）。</p></li></ol><p ><br /></p><p >本篇主要介绍第三种方法：<span >布隆过滤器</span>。</p><section class="xmt-style-block" data-tools="新媒体排版"><section class="" data-mpa-template-id="90" data-mpa-color="#ffffff" data-mpa-category="quote"><section ><section data-preserve-color="t" ><p ><span ><span >我们先熟悉一下</span><span >位图</span><span >的概念。</span></span></p><section ><span >位图也叫</span><span >位数组</span><span >，</span><span >可以看成</span><span >是一个数组，每个</span><span >数组</span><span >单元只</span><span >存储“0</span><span >”或者“1”，每个</span><span >单元</span><span >大小为</span><span >1bit</span><span >。</span></section><p ><img class="rich_pages" data-backh="104" data-backw="472" data-before-oversubscription-url="https://mmbiz.qpic.cn/mmbiz_png/ic1GeMKrCDdT06ZGia6ljQmPL3NpqT92cBxexoZpSzYTrkyuLhUqdJM5QJSHDiagJRPPemZxBxcfgXTPWibMoeWvibA/?wx_fmt=png" data-ratio="0.22033898305084745" data-s="300,640" src="https://img.haomeiwen.com/i11065549/e3d0deee33dd983a" data-type="png" data-w="472" /></p><p >正是因为位图所需内存较小，所以这里可派上用场。<br /></p></section></section></section></section><p >上文说了，位图存放的是0和1，那么怎么和实际数据对应起来呢？很自然能想到使用<span >哈希函数</span>。<br /></p><p ><br /></p><section ><img class="rich_pages" data-backh="374" data-backw="574" data-before-oversubscription-url="https://mmbiz.qlogo.cn/mmbiz_png/ic1GeMKrCDdT06ZGia6ljQmPL3NpqT92cBN4IZZACibaIM1HkoJ0s6r0UxC8e8ycD4CKjCK70wib2qk9k96wcBNdlQ/0?wx_fmt=png" data-ratio="0.6505016722408027" data-s="300,640" src="https://img.haomeiwen.com/i11065549/7d9bc546b195a4e6" data-type="png" data-w="598" /></section><section >如图，将人名存进位图时，可使用hash函数，将人名映射到对应的位图单元中，并将该单元数值置为1，0则代表没有数据映射到该单元，即该单元没有存放数据。<br /></section><section ><br /></section><section >然而<span >hash冲突</span>是不可避免的，图中可看到“潘金莲”和“武松”散列到了同一个数组单元。这就出现了一个问题：<strong>假如我们要存储的数据中有“潘金莲”，没有“武松”，当我们对“武松”进行哈希后发现其对应位置为1，于是认为“武松”存在于该数据集中，显然这个结果是错误的，因为1是潘金莲的映射结果。</strong><br /></section><section ><strong><br /></strong></section><section >那么怎么解决这个问题呢？因为hash冲突不可避免，所以我们只能尽量减少冲突的发生。</section><p >一般有两种思路：<strong><br /></strong></p><ol class=" list-paddingleft-2" ><li><section >对位图扩容，使用容量更大的位图；</section></li><li><p>rehash。</p></li></ol><p><br /></p><p >事实上，大名鼎鼎的<span >布隆过滤器（Bloom Filter）</span>使用的便是这两种思路。看下百度百科给出的定义。<br /></p><section class="xmt-style-block" data-tools="新媒体排版"><p class="" ><br /></p><section class="" data-tools="135编辑器" data-id="4503" ><section ><p><img class="" data-ratio="0.9473684210526315" src="https://img.haomeiwen.com/i11065549/ef0c36a9a70d6cfc" data-type="png" data-w="38" /></p><section class="" data-><p ><span >布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的</span><span >二进制</span><span >向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。</span></p></section><p ><img class="" data-ratio="0.9473684210526315" src="https://img.haomeiwen.com/i11065549/31747722376a2a67" data-type="png" data-w="38" /></p></section></section><p class=""><br /></p></section><section >简单而言，布隆过滤器就是<span >位图+一系列随机映射函数</span><span >。</span><br /></section><section ><img class="rich_pages" data-backh="336" data-backw="574" data-before-oversubscription-url="https://mmbiz.qlogo.cn/mmbiz_png/ic1GeMKrCDdT06ZGia6ljQmPL3NpqT92cBxribnju02YY9ibpqSrxBUNeNI05HAEaLEfbXicX4TFB9u52w6j0wsWuuQ/?wx_fmt=png" data-ratio="0.5850439882697948" data-s="300,640" src="https://img.haomeiwen.com/i11065549/c7e5732a183ddd59" data-type="png" data-w="682" /></section><p >如上图，使用了三个互相独立的hash函数，对每条数据都进行三次哈希，并将对应单元置为1.</p><p >这样能减少hash冲突的发生，当然hash函数的个数以及位图的容量是视情况而定的。<br /></p><p ><br /></p><p >布隆过滤器的优点：</p><p ><span ><span >1.每个单元只占1bit</span></span><span >，</span><span >所用空间小；</span></p><p ><span ><span >2.使用哈希直接查找</span></span><span >，</span><span >查询时间短</span><span >。</span></p><p ><span >布隆过滤器的</span>缺点：</p><p ><span ><span >1.由于hash冲突的存在</span>，有一定的</span><span >误判率</span><span >；</span></p><p ><span >2.由于hash冲突的存在</span><span >，</span><span >删除数据较为困难</span>。</p><p ><br /></p><section >先看误判率。</section><section ><img class="rich_pages" data-backh="320" data-backw="574" data-before-oversubscription-url="https://mmbiz.qlogo.cn/mmbiz_png/ic1GeMKrCDdT06ZGia6ljQmPL3NpqT92cBlrGs5M3DhIibXZoZU1vziadekibJoIglIzTyZa6ibpUfGia70zTTZQdZlgw/0?wx_fmt=png" data-ratio="0.5568685376661743" data-s="300,640" src="https://img.haomeiwen.com/i11065549/f72b4fb9d9a9bb8e" data-type="png" data-w="677" /></section><section ><span >其实与刚才“武松和潘金莲”的问题类似：</span><span >假设“吴用”并不在数据集中，但它的位置已被其它数据置为1，那么判定结果会错误。</span></section><p >但如果“吴用”对应的某个位置为0，那么“吴用”必定不存在，因为如果存在，与其对应的所有位置都为1.<br /></p><p >由此可得下面两条结论：</p><p ><span >布隆过滤器判断数据存在，那么它可能存在也可能不存在</span><span >。</span></p><p ><span ><span >布隆过滤器判断数据不存在，那么它必定不存在。</span></span></p><p ><span ><span ><br /></span></span></p><p ><span >再看删除数据。</span></p><section >这个也好理解，举个栗子。<br /></section><section ><img class="rich_pages" data-backh="336" data-backw="574" data-before-oversubscription-url="https://mmbiz.qlogo.cn/mmbiz_png/ic1GeMKrCDdT06ZGia6ljQmPL3NpqT92cBMYibjH2DNRHWaSOGqj9BhWgJcElL2HiagKclRm5VPF9DGZAlDbLpUevg/0?wx_fmt=png" data-ratio="0.5852941176470589" data-s="300,640" src="https://img.haomeiwen.com/i11065549/16db45072fc59390" data-type="png" data-w="680" /></section><section >“吴用”和“宋江”都映射到④号位置，现在想要删除“吴用”，那么④号位置到底要不要置为0呢？如果置为0，那么“宋江”就不高兴了，如果不变，显然又会增加对“吴用”的误判率（已经被删除，但该位置还是1）。</section><section >在后来的改进中，对位图的每个单元增加了<span >计数器</span>，计数器初始值为0，每映射一个数据，计数器加1，每删除一个数据，计数器减1。这样在删除数据时，只要计数器<span >当前值</span>大于1，该单元就不置为0.<br /></section><section ><br /></section><section >布隆过滤器的应用场景有很多，典型的有Redis的缓存穿透、爬虫时URL去重、垃圾邮件的判别等。</section><section >下篇会介绍布隆过滤器如何应对<span >Redis缓存穿透</span>。</section><section ><br /></section><section class="xmt-style-block" data-tools="新媒体排版"><p class=""><img class="" data-copyright="0" data-ratio="0.0140625" data-s="300,640" src="https://img.haomeiwen.com/i11065549/e35ed95afda08f10" data-type="png" data-w="640" /></p></section><section class="xmt-style-block" data-tools="新媒体排版"><section class="" powered-by="xiumi.us" ><section ><section ><section class="" powered-by="xiumi.us" ><section ><section ><p >后台回复【1】即可无套路领取众多精选学习资源！</p></section></section></section></section></section></section></section><p ><br /></p><p ><img class="rich_pages" data-backh="319" data-backw="574" data-before-oversubscription-url="https://mmbiz.qpic.cn/mmbiz_png/ic1GeMKrCDdSJPtqal7hT7UVE4f1CW3bu8iaS59m8JfZ6wRKrC1r5T41pavadib4TD1JgiadmmMcP6wKUvO7w86kKg/?wx_fmt=png" data-ratio="0.5555555555555556" data-s="300,640" src="https://img.haomeiwen.com/i11065549/0a008e31be53fec2" data-type="png" data-w="900" /></p><p><br /></p>