高级应用篇二

问题：网页爬虫是搜索引擎中非常重要的系统，负责爬取几十亿，上百亿的网页。而同一个网页链接有可能被包含在多个页面中，这就会导致爬虫在爬取的过程中，重复爬取相同的网页。如果你是一名负责爬虫的工程师，你会如何避免这些重复的爬取呢？

解题思路：这个问题要处理的对象是URL，需要支持添加和查询一个URL的操作。除此之外，因为我们处理的是上亿的网页链接，内存消耗会非常大，所以在存储效率上，我们要尽可能地高效。

满足这些条件的数据结构：散列表，红黑树，跳表都支持快速地插入和查找数据，但是对内存消耗方面都比较巨大。如果用散列表，假设一个URL的平均长度是64字节，那单纯存储这10亿个URL，就需要大约60GB的内存空间。并且为了维持较少的散列冲突，散列表必须维持较小的装载因子。即使用链表法解决冲突的散列表，还会存储链表指针。如果将这10亿个URL构建成散列表，那需要的内存空间有可能会超过100GB。

对于存储有没有更好的解决方案？位图。对于我们有1千万个整数，范围在1到1亿之间，如何快速查找某个整数是否在这1千万个整数中呢？我们可以申请一个大小为1亿，数据类型为Boolean型的数组。将这1千万个整数作为数组下标，将对应的数组值设置为true。查询时只需要判断array[k]是否为true。不过，很多语言中提供的布尔类型，大小是1个字节，并不能节省太多内存空间。实际上表示true和false两个值，我们只需要一个二进制位就可以了。

实现代码：

如果刚刚假设的数字所在范围不是1到1亿，而是1到10亿，那位图的内存大小也要成倍增加。为了解决这个问题，布隆过滤器就出现了，它是对位图这种数据结构的一种改进。当数据范围是1到10亿时，依然使用1到1亿的大小的数组，但是每个数值会经过K个哈希函数处理，K个哈希值都相同的概率就非常低了。

布隆过滤器：布隆过滤器用多个哈希函数对同一个网页链接进行处理，CPU只需要将网页链接从内存中读取一次，进行多次哈希计算，理论上讲这组操作是CPU密集型的。而在散列表的处理方式中，需要读取散列冲突拉链的多个网页链接，分别跟待判重的网页链接，进行字符串匹配，这个操作涉及很多内存数据的读取，属于内存密集型的。而CPU计算可能是要比内存访问更快速的，所以理论上讲，布隆过滤器的判重方式，更加快速。