什么是数据稀疏(稀疏表示是什么意思)

前言

在计算机世界里，数据计算和处理是精确的，这是大多数人想当然的，也应该是。但在某些场景下，无论是在时间上还是在空上，做到完全准确都意味着高昂的代价。

所以大家都在考虑有没有一些方法可以在错误率很小的前提下，大大提高效率，减少资源消耗。对于误判概率较小的场景，可以通过容错机制来填补漏洞。显然，在这种背景下，我们这篇文章的主角，一个“不靠谱”的傻逼布鲁姆滤镜出现了。与偶像剧的情节不同，二愣子因为自身的“缺点”，两集都没有“吃盒饭”。而是通过自己的机智和勇气，在C位出道，赢得了众多美女的芳心。这个正经的魏老爷还活着。让我们来谈谈韦小宝在大数据处理方面是如何高超的。

今天的图就不介绍了，我想大家都很了解。鹿鼎记是金庸先生的代表作，韦小宝也是金庸先生最喜欢的人物。而我认为陈小春版的韦小宝是原作还原度最高的存在。他的优点和缺点都很明显。他不按套路出牌，经常另辟蹊径，有很多创造性思维，扬长避短，发挥所长，就像我们今天文章的主角——布鲁姆滤镜。

正文What布隆过滤器？

今天来说说主角的诞生:

Bloom Filter是Bloom在1970年提出的一种多哈希函数映射的快速搜索算法。它通常用于需要快速确定一个元素是否属于一个集合，但并不严格要求100%正确的情况。基于概率数据结构，这是一个有趣而强大的算法。

How布隆过滤器?

以人名命名的算法一般都很优秀，这个也不例外。他利用了位图的部分实现(如果不了解位图，可以参考下一篇)，取其所长，避其所短。他站在巨人的肩膀上，成就了自己的辉煌。我们先来看看位图的缺点:

数据密集时效率比较高：当数据分布均匀时，位图的效率很高，占用的空间也很理想；但是如果数据稀疏，比如大部分数据都分三段，1-1000，100000-500000，100000000-200000000，这时候的位图必须按照最大值进行初始化申请空间，这就造成了很多空间的浪费。最大数据量要求已知：因为位图需要根据数据量来初始化位图存储数组，所以要求在设计之初知晓数据量，然后根据最大数据量进行数据初始化，如果后续数据量超出了预先的最大值，则位图很难处理。适用范围有限：位图比较适合处理数值类型的数据，针对于字符串类的数据虽然可以使用hash函数将字符串映射到某一位，但缺点是单一哈希函数发生冲突的概率太高，造成错误率过高。若要降低冲突发生的概率到1%，有种办法就是就要将位图的长度设置为字符串个数的100倍。

时势造英雄，韦小宝如此，布鲁姆过滤器也是如此。针对以上问题，Bloom Filter给出了自己的解决方案:首先，Bloom Filter打算在位图的基础上解决刚才的三个问题，从而“基本”达到目的。这里的基础非常重要。先卖个通行证，大家都能记住。这里有一个解释。

减少哈希冲突概率

如上所述，单个哈希函数的碰撞概率太高，那么单个函数太高，多个函数会更好吗？

答案是肯定的，所以Bloom filter使用多个哈希函数来映射字符串，生成多个位并存储在位图中。如下图所示:

查询时，使用相同的哈希函数处理字符串以生成多个位。如果有一位为0，则表示该字符串肯定不存在。而如果所有的位都是1，就说明这个字符串有很大的概率。下图显示该字符串肯定不存在，因为有一个返回0的哈希函数:

位图中大概率存在？打扰一下。这种答案扔给用户，用户该怎么办？你信不信？唐& # 39；不要担心！路的尽头有一条路。这里有两个问题需要确认:

首先就是正确率的问题，如果正确率过低，那这个算法就没什么存在的意义了，但是如果正确率很高，仅有很少的错误率，那在容错成本很低的前提下总会有办法进行容错。那如何提高正确率呢？其实有两个因素，一个就是位图的位数与数据量的比值，其实就是数据冗余量；第二个就是哈希函数的个数。关系如下图所示：

图中的字母代表以下含义:

m ： BitSet 位数n ： 插入字符串个数k ：hash函数个数

从上图可以看出，数据冗余越大，哈希函数越多，错误率越低。但总体来说误差率控制在1%以内。相比位图需要100倍的数据膨胀率，Bloom filter的开销要小很多，所以现实中使用的场景要多很多。

考虑到实施成本，每个组件或场景在实施时都会根据自身的具体情况选择具体的比例，以达到最佳的性价比。毕竟大数据处理还是一门生意，成本是技术选择的重要因素之一。这也解释了上面的基本意思。

确定了正确率的问题后，接下来就是关键的容错了，怎么容错才算完美，既能解决问题，又能照顾容错成本呢？这个就和具体的使用场景有关了，下面会结合业务场景来具体说明。降低数据稀疏带来的影响

降低哈希碰撞概率后，问题已经解决了一大半，剩下的问题也方便解决了。由于Bloom filter使用多个hash函数进行处理，生成的值呈正态均匀分布，彻底解决了由于数据不均衡导致数据稀疏时开销大的问题。

对数据量已知的要求降低

虽然说增加数据量超过预先设计的最大值也会影响Bloom filter，但是除非差别太大，否则影响不是很严重。因为实际数据量增加，只会影响上图中m/n的值，影响也只是轻微影响Bloom filter的精度，并不是像位图一样几乎无法处理。

就这样，一个大数据世界的韦小宝已经呼之欲出，剩下的就是找到属于他的舞台，然后找到七个漂亮的老婆。

Where布隆过滤器

说完了Bloom filter的特点和实现原理，我们再来看看Bloom filter的使用场景。

通过在不同场景下的使用，我们可以看到Bloom filter是如何发挥重要作用的，以及如何扬长避短进行容错。同时也知道了Bloom Filter是如何赢得“美人”的芳心，从而赢得美人的回归。

URL或者Email去重

其实这是Bloom Filter出道的场景。Bloom Filter在这个场景中应运而生，并很快得到了大家的认可。

场景

假设我们想写一个爬虫程序。由于网络间错综复杂的联系，蜘蛛在网络间爬行时可能会形成一个“环”，爬虫会进入一个无限循环，找不到出路，程序就会崩溃。所以为了避免形成“环”，你需要知道蜘蛛访问过哪些URL，也就是如何判断权重。

同样，如果我们需要给很多人发邮件通知或确认某件事，为了不重复多次给同一个人发邮件，引起大规模的不满，我们如何知道那些已经发了的邮件，以及如何判断权重呢？

实现

这时候，Bloom filter登场了。将抓取的URL和发送的电子邮件放入Bloom过滤器。下次你发现一个新的网址或电子邮件，在Bloom filter中询问它，你就会知道它是否被处理过。

防止缓存穿透

Bloom Filter对上述场景稍加尝试后，决定再接再厉，扩大知名度。

场景

在数据库访问中，通常有一个缓存层来减少对数据库的直接访问。第一，提高查询效率；它还可以保护数据库在高并发情况下不会崩溃。

所以正常的查询流程是客户端先访问缓存层，命中就直接返回；如果没有命中，则认为缓存可能与数据库不一致或者不是热数据，会查询数据库。

本来这是正常的业务逻辑，在缓存命中率很高的情况下，效果很好，效率高。但是有一种恶意攻击，用一个密钥频繁访问查询接口，这是完全不可能的。因为键不存在，缓存根本发挥不了作用，正常的业务逻辑直接频繁访问数据库，直到数据库瘫痪或者一直处于高负载状态。

实现

这时候，Bloom filter又登场了。将数据库中相应缓存中的所有键放入Bloom filter。下次去Bloom filter问问数据库里有没有这个值。如果有，去数据库查一下。如果没有，直接返回结果，避免无效的数据库查询。从而达到保护数据库，英雄救美的效果。

NOSQL数据库的索引过滤器

经过以上两场战役，Bloom filter已经名满全球，但真正让Bloom filter走向人生巅峰的，是NOSQL数据库在大数据时代的应用。在这种场景下，Bloom filter真的做到了超神之路。HBase，Cassandra，RocksDB，LevelDB都是Bloom filter的粉丝。

场景

在NOSQL数据库中，虽然经过无数次的分片和索引，数据查询的效率有了显著的提高，但是在定位到粒度最小的索引文件后，仍然需要遍历才能知道数据是否存在，如果存在，就查询相应的数据。这对于NOSQL数据库来说是不可接受的。这时候我们的Bloom滤镜又出现了。

实现

布隆过滤器存储对应于目标索引的密钥。查询时，先用键查询Bloom filter，然后在索引文件中遍历查询(如果存在的话)。这样可以直接判断索引是否包含要查询的数据，从而避免无用的遍历操作。达到提高效率的目的。

容错

最后，根据上面的场景，我们来说说容错，一个听起来很有技术含量，很高大上的操作。相信现在的朋友可能已经猜到了Bloom filter是如何容错的。是的，Bloom filter的容错操作是不容错的！！！

纳尼？容错？你在开玩笑吗？我没听错吧？是的，不容错。为什么不呢？因为容错的目的是消除错误带来的严重影响，但是我们回过头来看看如果Bloom filter不容错会怎么样？无非是多爬几个网页；发几封邮件；检查数据库几次，遍历文件几次。

后果严重吗？显然不是！！！由于Bloom filter的正确率是可控的，与绝大多数的正确过滤器相比，几次误判造成的消耗不值一提，所以不容错也就理所当然了。这种懒惰是可以偷的。例如，韦小宝不时的作弊是无害的。

总结

以上，我们总结了Bloom filter的不平凡之路。与常规处理方法相比，布隆过滤器可视为另一种方式。在尽可能保证准确性的前提下，加快了大数据处理和查询的速度，容错处理也很“经典”...它在许多情况下创造了奇迹。

就像韦小宝一样，在小说中的环境里，他如鱼得水，取得了巨大的成就。获得了巨额的财宝；实现了终极梦想。

这就是所谓的造英雄的时候。技术如此，人也如此。

最后，笔者长期关注大数据的一般技术和原理，以及NOSQL数据库的技术架构和使用。如果觉得作者文笔不错，请点赞分享。也许你的朋友也喜欢它。