算法之美3 - 散列表

布满荆棘的人生 2022-03-02 11:48 409阅读 0赞

## 散列表 ##

散列函数、冲突解决、动态扩容、位图

--------------------

### 18 | 散列表（上）：Word文档中的单词拼写检查功能是如何实现的？ ###

> 一、散列表的由来？

1.散列表来源于数组，它借助散列函数对数组这种数据结构进行扩展，利用的是数组支持按照下标随机访问元素的特性。

2.需要存储在散列表中的数据我们称为键，将键转化为数组下标的方法称为散列函数，散列函数的计算结果称为散列值。

3.将数据存储在散列值对应的数组下标位置。

> 二、如何设计散列函数？

总结3点设计散列函数的基本要求

1.散列函数计算得到的散列值是一个非负整数。

2.若key1=key2，则hash(key1)=hash(key2)

3.若key≠key2，则hash(key1)≠hash(key2)

正是由于第3点要求，所以产生了几乎无法避免的散列冲突问题。

> 三、散列冲突的解放方法？

1.常用的散列冲突解决方法有2类：开放寻址法（open addressing）和链表法（chaining）

2.开放寻址法

①核心思想：如果出现散列冲突，就重新探测一个空闲位置，将其插入。

②线性探测法（Linear Probing）：

插入数据：当我们往散列表中插入数据时，如果某个数据经过散列函数之后，存储的位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。

查找数据：我们通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素是否相等，若相等，则说明就是我们要查找的元素；否则，就顺序往后依次查找。如果遍历到数组的空闲位置还未找到，就说明要查找的元素并没有在散列表中。

删除数据：为了不让查找算法失效，可以将删除的元素特殊标记为deleted，当线性探测查找的时候，遇到标记为deleted的空间，并不是停下来，而是继续往下探测。

结论：最坏时间复杂度为O(n)

③二次探测（Quadratic probing）：线性探测每次探测的步长为1，即在数组中一个一个探测，而二次探测的步长变为原来的平方。

④双重散列（Double hashing）：使用一组散列函数，直到找到空闲位置为止。

⑤线性探测法的性能描述：

用“装载因子”来表示空位多少，公式：散列表装载因子=填入表中的个数/散列表的长度。

装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。

3.链表法（更常用）

插入数据：当插入的时候，我们需要通过散列函数计算出对应的散列槽位，将其插入到对应的链表中即可，所以插入的时间复杂度为O(1)。

查找或删除数据：当查找、删除一个元素时，通过散列函数计算对应的槽，然后遍历链表查找或删除。对于散列比较均匀的散列函数，链表的节点个数k=n/m，其中n表示散列表中数据的个数，m表示散列表中槽的个数，所以是时间复杂度为O(k)。

> 四、思考

1.Word文档中单词拼写检查功能是如何实现的？

常用的英文单词有 20 万个左右，假设单词的平均长度是 10 个字母，平均一个单词占用 10 个字节的内存空间，那 20 万英文单词大约占 2MB 的存储空间，就算放大 10 倍也就是 20MB。这个大小完全可以放在内存里面。所以我们可以用散列表来存储整个英文单词词典。

当用户输入某个英文单词时，我们拿用户输入的单词去散列表中查找。如果查到，则说明拼写正确；如果没有查到，则说明拼写可能有误，给予提示。借助散列表这种数据结构，我们就可以轻松实现快速判断是否存在拼写错误。

2.假设我们有10万条URL访问日志，如何按照访问次数给URL排序？

遍历 10 万条数据，以 URL 为 key，访问次数为 value，存入散列表，同时记录下访问次数的最大值 K，时间复杂度 O(N)。

如果 K 不是很大，可以使用桶排序，时间复杂度 O(N)。如果 K 非常大（比如大于 10 万），就使用快速排序，复杂度 O(NlogN)。

3.有两个字符串数组，每个数组大约有10万条字符串，如何快速找出两个数组中相同的字符串？

以第一个字符串数组构建散列表，key 为字符串，value 为出现次数。再遍历第二个字符串数组，以字符串为 key 在散列表中查找，如果 value 大于零，说明存在相同字符串。时间复杂度 O(N)。

--------------------

### 19 | 散列表（中）：如何打造一个工业级水平的散列表？ ###

> 一、如何设计散列函数？

1.要尽可能让散列后的值随机且均匀分布，这样会尽可能减少散列冲突，即便冲突之后，分配到每个槽内的数据也比较均匀。

2.除此之外，散列函数的设计也不能太复杂，太复杂就会太耗时间，也会影响到散列表的性能。

3.常见的散列函数设计方法：直接寻址法、平方取中法、折叠法、随机数法等。

> 二、如何根据装载因子动态扩容？

1.如何设置装载因子阈值？

①可以通过设置装载因子的阈值来控制是扩容还是缩容，支持动态扩容的散列表，插入数据的时间复杂度使用摊还分析法。

②装载因子的阈值设置需要权衡时间复杂度和空间复杂度。如何权衡？如果内存空间不紧张，对执行效率要求很高，可以降低装载因子的阈值；相反，如果内存空间紧张，对执行效率要求又不高，可以增加装载因子的阈值。

2.如何避免低效扩容？分批扩容

①分批扩容的插入操作：当有新数据要插入时，我们将数据插入新的散列表，并且从老的散列表中拿出一个数据放入新散列表。每次插入都重复上面的过程。这样插入操作就变得很快了。

②分批扩容的查询操作：先查新散列表，再查老散列表。

③通过分批扩容的方式，任何情况下，插入一个数据的时间复杂度都是O(1)。

> 三、如何选择散列冲突解决方法？

①常见的2中方法：开放寻址法和链表法。

②大部分情况下，链表法更加普适。而且，我们还可以通过将链表法中的链表改造成其他动态查找数据结构，比如红黑树、跳表，来避免散列表时间复杂度退化成O(n)，抵御散列冲突攻击。

③但是，对于小规模数据、装载因子不高的散列表，比较适合用开放寻址法。

> 四、面试题目：如何设计一个工业级的散列函数？

思路：

何为一个工业级的散列表？工业级的散列表应该具有哪些**特性**？结合学过的知识，我觉的应该有这样的要求：

1.支持快速的查询、插入、删除操作；

2.内存占用合理，不能浪费过多空间；

3.性能稳定，在极端情况下，散列表的性能也不会退化到无法接受的情况。

方案：

如何**实现**这样一个散列表呢？根据前面讲到的知识，我会从3个方面来考虑设计思路：

1.设计一个合适的散列函数；

2.定义装载因子阈值，并且设计动态扩容策略；

3.选择合适的散列冲突解决方法。

> 五、思考

在你熟悉的编程语言中，哪些数据类型底层是基于散列表实现的？散列函数是如何设计的？散列冲突是通过哪种方法解决的？是否支持动态扩容呢？

--------------------

### 20 | 散列表（下）：为什么散列表和链表经常会一起使用？ ###

1.为什么散列表和链表经常放在一起使用？

2.散列表和链表如何组合起来使用？

> 一、为什么散列表和链表经常放在一起使用？

1.散列表的优点：支持高效的数据插入、删除和查找操作

2.散列表的缺点：不支持快速顺序遍历散列表中的数据

3.如何按照顺序快速遍历散列表的数据？只能将数据转移到数组，然后排序，最后再遍历数据。

4.我们知道散列表是动态的数据结构，需要频繁的插入和删除数据，那么每次顺序遍历之前都需要先排序，这势必会造成效率非常低下。

5.如何解决上面的问题呢？就是将散列表和链表（或跳表）结合起来使用。

> 二、散列表和链表如何组合起来使用？

1.LRU（Least Recently Used）缓存淘汰算法

1.1.LRU缓存淘汰算法主要操作有哪些？主要包含3个操作：

①往缓存中添加一个数据；

②从缓存中删除一个数据；

③在缓存中查找一个数据；

④总结：上面3个都涉及到查找。

1.2.如何用链表实现LRU缓存淘汰算法？

①需要维护一个按照访问时间从大到小的有序排列的链表结构。

②缓冲空间有限，当空间不足需要淘汰一个数据时直接删除链表头部的节点。

③当要缓存某个数据时，先在链表中查找这个数据。若未找到，则直接将数据放到链表的尾部。若找到，就把它移动到链表尾部。

④前面说了，LRU缓存的3个主要操作都涉及到查找，若单纯由链表实现，查找的时间复杂度很高为O(n)。若将链表和散列表结合使用，查找的时间复杂度会降低到O(1)。

1.3.如何使用散列表和链表实现LRU缓存淘汰算法？

①使用双向链表存储数据，链表中每个节点存储数据（data）、前驱指针（prev）、后继指针（next）和hnext指针（解决散列冲突的链表指针）。

②散列表通过链表法解决散列冲突，所以每个节点都会在两条链中。一条链是双向链表，另一条链是散列表中的拉链。前驱和后继指针是为了将节点串在双向链表中，hnext指针是为了将节点串在散列表的拉链中。

③LRU缓存淘汰算法的3个主要操作如何做到时间复杂度为O(1)呢？

首先，我们明确一点就是链表本身插入和删除一个节点的时间复杂度为O(1)，因为只需更改几个指针指向即可。

接着，来分析查找操作的时间复杂度。当要查找一个数据时，通过散列表可实现在O(1)时间复杂度找到该数据，再加上前面说的插入或删除的时间复杂度是O(1)，所以我们总操作的时间复杂度就是O(1)。

2.Redis有序集合

2.1.什么是有序集合？

①在有序集合中，每个成员对象有2个重要的属性，即key（键值）和score（分值）。

②不仅会通过score来查找数据，还会通过key来查找数据。

2.2.有序集合的操作有哪些？

举个例子，比如用户积分排行榜有这样一个功能：可以通过用户ID来查找积分信息，也可以通过积分区间来查找用户ID。这里用户ID就是key，积分就是score。所以，有序集合的操作如下：

①添加一个对象；

②根据键值删除一个对象；

③根据键值查找一个成员对象；

④根据分值区间查找数据，比如查找积分在\[100.356\]之间的成员对象；

⑤按照分值从小到大排序成员变量。

这时可以按照分值将成员对象组织成跳表结构，按照键值构建一个散列表。那么上面的所有操作都非常高效。

3.Java LinkedHashMap

和LRU缓存淘汰策略实现一模一样。支持按照插入顺序遍历数据，也支持按照访问顺序遍历数据。

> 三、课后思考

1.上面所讲的几个散列表和链表组合的例子里，我们都是使用双向链表。如果把双向链表改成单链表，还能否正常工作？为什么呢？

2.假设猎聘网有10万名猎头，每个猎头可以通过做任务（比如发布职位）来积累积分，然后通过积分来下载简历。假设你是猎聘网的一名工程师，如何在内存中存储这10万个猎头的ID和积分信息，让它能够支持这样几个操作：

1）根据猎头ID查收查找、删除、更新这个猎头的积分信息；

2）查找积分在某个区间的猎头ID列表；

3）查找按照积分从小到大排名在第x位到第y位之间的猎头ID列表。

--------------------

### 21 | 哈希算法（上）：如何防止数据库中的用户信息被脱库？ ###

> 哈希算法

从哈希值不能反向推导出原始数据（所以哈希算法也叫**单向**哈希算法）;

对输入数据非常**敏感**，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同；

散列冲突的**概率**要很小，对于不同的原始数据，哈希值相同的概率非常小；

哈希算法的执行**效率**要尽量高效，针对较长的文本，也能快速地计算出哈希值。

> 四个应用

第一个应用是安全加密，我们讲到任何哈希算法都会出现散列冲突，但是这个冲突概率非常小。越是复杂哈希算法越难破解，但同样计算时间也就越长。所以，选择哈希算法的时候，要权衡安全性和计算时间来决定用哪种哈希算法。

*  为什么哈希算法无法做到零冲突?
    
     *  鸽巢原理（也叫抽屉原理）

第二个应用是唯一标识，哈希算法可以对大数据做信息摘要，通过一个较短的二进制编码来表示很大的数据。

*  如何快速判断图片是否在图库中？
    
     *  每个图片取唯一标识（或者信息摘要），然后构建散列表。

第三个应用是用于校验数据的完整性和正确性。

*  电驴这样的 BT 下载软件

我们通过哈希算法，对 100 个文件块分别取哈希值，并且保存在种子文件中。我们在前面讲过，哈希算法有一个特点，对数据很敏感。只要文件块的内容有一丁点儿的改变，最后计算出的哈希值就会完全不同。所以，当文件块下载完成之后，我们可以通过相同的哈希算法，对下载好的文件块逐一求哈希值，然后跟种子文件中保存的哈希值比对。如果不同，说明这个文件块不完整或者被篡改了，需要再重新从其他宿主机器上下载这个文件块。

第四个应用是散列函数，这个我们前面讲散列表的时候已经详细地讲过，它对哈希算法的要求非常特别，更加看重的是散列的平均性和哈希算法的执行效率。

*  散列函数对于散列算法冲突的要求要低很多
 *  散列函数中用到的散列算法，更加关注散列后的值是否能**平均分布**，也就是，一组数据是否能均匀地散列在各个槽中。

> 思考

1.现在，区块链是一个很火的领域，它被很多人神秘化，不过其底层的实现原理并不复杂。其中，哈希算法就是它的一个非常重要的理论基础。你能讲一讲区块链使用的是哪种哈希算法吗？是为了解决什么问题而使用的呢？

区块链是一块块区块组成的，每个区块分为两部分：区块头和区块体。

区块头保存着 自己区块体 和 上一个区块头 的哈希值。

因为这种链式关系和哈希值的唯一性，只要区块链上任意一个区块被修改过，后面所有区块保存的哈希值就不对了。

区块链使用的是 SHA256 哈希算法，计算哈希值非常耗时，如果要篡改一个区块，就必须重新计算该区块后面所有的区块的哈希值，短时间内几乎不可能做到。

2.如何防止数据库中的用户信息被脱库？

SHA

针对字典攻击，我们可以引入一个盐（salt），跟用户的密码组合在一起，增加密码的复杂度。

--------------------

### 22 | 哈希算法（下）：哈希算法在分布式系统中有哪些应用？ ###

> 1.负载均衡

1.1.需求

如何实现一个会话粘滞（session sticky）的负载均衡算法？也就是说，在一次会话中的所有请求都路由到同一个服务器上。

1.2.解决方案

通过哈希算法对客户端IP或会话ID计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。这样，就可以把同一个IP过来的请求都路由到同一个后端服务器上。

> 2.数据分片

2.1.如何统计“搜索关键词”出现的次数？

①需求描述

假如我们有1T的日志文件，这里面记录了用户的搜索关键词，我们想要快速统计出每个关键词被搜索的次数，该怎么做呢？

②问题分析

这个问题有两个难点，第一个是搜索的日子很大，没办法放到一台机器的内存中。第二个是只用一台机器来处理这么巨大的数据，处理时间会很长。

③解决方案

先对数据进行分片，然后采用多台（比如n台）机器进行处理。具体做法：从搜索记录的日志文件中依次读取每个关键词，并通过哈希函数计算该关键词的哈希值，然后跟机器的台数n取模，最终得到值就是该关键词应该被分到的机器编号，这样相同的关键词一定会被分配到同一台机器上，数据分配完成后，由多台机器并行进行统计，最后合并起来就是最终结果。

实际上，这里的处理过程也是 MapReduce 的基本设计思想。

2.2.如何快速判断图片是否存在图库中？

①需求描述

假设现在我们的图库中有1亿张图片，如何快速判断图片是否在图库中？基本方式是给每个图片去唯一表示（或者信息摘要），然后构建散列表。

②问题分析

很显然，在单台机器上构建散列表示行不通的，因为单台机器的内存有限，而1亿张图片构建散列表远远超过了单台机器的内存上限。

②解决方案

准备n台机器，让每台机器只维护一部分图片对应的散列表。我们每次从图库中读取一个图片，计算唯一标识，然后与机器个数n求余取模，得到的值就对应要分配的机器编号，然后将这个图片的唯一表示和图片路径发往对应的机器构建散列表。

当我们要判断一个图片是否在图库中时，我们通过同样的哈希算法，计算这个图片的唯一表示，然后与机器个数n求余取模。假设得到的值是k，那就去编号为k的机器构建的散列表中查找。

如何估算给1亿张图片构建散列表大约需要多少台机器？

散列表中每个数据单元包含两个信息，哈希值和图片文件的路径。假设我们通过 MD5 来计算哈希值，那长度就是 128 比特，也就是 16 字节。文件路径长度的上限是 256 字节，我们可以假设平均长度是 128 字节。如果我们用链表法来解决冲突，那还需要存储指针，指针只占用 8 字节。所以，散列表中每个数据单元就占用 152 字节（这里只是估算，并不准确）。

假设一台机器的内存大小为 2GB，散列表的装载因子为 0.75，那一台机器可以给大约 1000 万（2GB\*0.75/152）张图片构建散列表。所以，如果要对 1 亿张图片构建索引，需要大约十几台机器。在工程中，这种估算还是很重要的，能让我们事先对需要投入的资源、资金有个大概的了解，能更好地评估解决方案的可行性。

实际上，针对这种海量数据的处理问题，我们都可以采用多机分布式处理。借助这种分片的思路，可以突破单机内存、CPU 等资源的限制。

> 3.分布式存储

3.1.什么是分布式存储？

分布式存储就是将数据存储在多台机器上并提供高效的读取、写入支持。那如何决定将哪个数据放到哪个机器上呢？可以利用数据分片的思想，即通过哈希算法对数据取哈希值，然后对机器个数取模，这个最终值就是应该存储的缓存机器编号。

3.2.遇到的问题是什么？

如果数据持续增多，原来的机器数量已经不能满足需求，就需要增加机器，这时就麻烦了，因为所有的数据都需要重新哈希值进行再次分配。这就相当于，缓存中的数据一下子都失效了，所有的数据请求都会穿透缓存，直接去请求数据库。这样就可能发生**雪崩效应**，压垮数据库。

3.3.解决方案是什么？

①这时，需要一种方法，使得新加入一个机器后，并不需要做大量的数据搬移。那就是在分布式系统中应用非常广泛的**一致性哈希算法**。

②一致性哈希算法的基本思想是什么呢？为了说清楚这个问题，我们假设有k个机器，数据的哈希值范围是\[0-MAX\]，我们将整个范围划分成m个小区间（m远大于k），每个机器复杂m/k个小区间。当有新机器加入的时候，我们就将某几个小区间的数据，从原来的机器中搬移到新的机器中。这样，既不用全部重新哈希、搬移数据，也保持了各个机器上数据量的均衡。

--------------------

### 45 | 位图：如何实现网页爬虫中的URL去重功能？ ###

布隆过滤器（Bloom Filter）：节省内存

bloom filter: False is always false. True is maybe true.

> 分治加散列表的思路

假设我们要爬取 10 亿个网页（像 Google、百度这样的通用搜索引擎，爬取的网页可能会更多），为了判重，我们把这 10 亿网页链接存储在散列表中。你来估算下，大约需要多少内存？

假设一个 URL 的平均长度是 64 字节，那单纯存储这 10 亿个 URL，需要大约 60GB 的内存空间。因为散列表必须维持较小的装载因子，才能保证不会出现过多的散列冲突，导致操作的性能下降。而且，用链表法解决冲突的散列表，还会存储链表指针。所以，如果将这 10 亿个 URL 构建成散列表，那需要的内存空间会远大于 60GB，有可能会超过 100GB。

> 位图（BitMap）

例子：我们有 1 千万个整数，整数的范围在 1 到 1 亿之间。如何快速查找某个整数是否在这 1 千万个整数中呢？

当然，这个问题还是可以用散列表来解决。不过，我们可以使用一种比较“特殊”的散列表，那就是位图。我们申请一个大小为 1 亿、数据类型为布尔类型（true 或者 false）的数组。我们将这 1 千万个整数作为数组下标，将对应的数组值设置成 true。比如，整数 5 对应下标为 5 的数组值设置为 true，也就是 array\[5\]=true。

当我们查询某个整数 K 是否在这 1 千万个整数中的时候，我们只需要将对应的数组值 array\[K\] 取出来，看是否等于 true。如果等于 true，那说明 1 千万整数中包含这个整数 K；相反，就表示不包含这个整数 K。

从刚刚位图结构的讲解中，你应该可以发现，**位图通过数组下标来定位数据**，所以，访问效率非常高。而且，每个数字用一个二进制位来表示，在数字范围不大的情况下，所需要的内存空间非常节省。

比如刚刚那个例子，如果用散列表存储这 1 千万的数据，数据是 32 位的整型数，也就是需要 4 个字节的存储空间，那总共至少需要 40MB 的存储空间。如果我们通过位图的话，数字范围在 1 到 1 亿之间，只需要 1 亿个二进制位，也就是 12MB 左右的存储空间就够了。

> 布隆过滤器（Bloom Filter）

关于位图，我们就讲完了，是不是挺简单的？不过，这里我们有个假设，就是数字所在的范围不是很大。**如果数字的范围很大**，比如刚刚那个问题，数字范围不是 1 到 1 亿，而是 1 到 10 亿，那位图的大小就是 10 亿个二进制位，也就是 120MB 的大小，消耗的内存空间，不降反增。

这个时候，布隆过滤器就要出场了。**布隆过滤器**就是为了解决刚刚这个问题，对位图这种数据结构的一种改进。

还是刚刚那个例子，数据个数是 1 千万，数据的范围是 1 到 10 亿。布隆过滤器的做法是，我们仍然使用一个 1 亿个二进制大小的位图，然后通过哈希函数，对数字进行处理，让它落在这 1 到 1 亿范围内。比如我们把哈希函数设计成 f(x)=x%n。其中，x 表示数字，n 表示位图的大小（1 亿），也就是，对数字跟位图的大小进行取模求余。

不过，你肯定会说，哈希函数会存在冲突的问题啊，一亿零一和 1 两个数字，经过你刚刚那个取模求余的哈希函数处理之后，最后的结果都是 1。这样我就无法区分，位图存储的是 1 还是一亿零一了。

我们使用 **K 个哈希函数**，对同一个数字进行求哈希值，那会得到 K 个不同的哈希值，我们分别记作 X1，X2，X3，…，Xk。我们把这 K 个数字作为位图中的下标，将对应的 BitMap\[X1\]，BitMap\[X2\]，BitMap\[X3\]，…，BitMap\[Xk\] 都设置成 true，也就是说，我们用 K 个二进制位，来表示一个数字的存在。

当我们要**查询**某个数字是否存在的时候，我们用同样的 K 个哈希函数，对这个数字求哈希值，分别得到 Y1，Y2，Y3，…，Yk。我们看这 K 个哈希值，对应位图中的数值是否都为 true，如果都是 true，则说明，这个数字存在，如果有其中任意一个不为 true，那就说明这个数字不存在。

布隆过滤器的**误判**有一个特点，那就是，它只会对存在的情况有误判。如果某个数字经过布隆过滤器判断不存在，那说明这个数字真的不存在，不会发生误判；如果某个数字经过布隆过滤器判断存在，这个时候才会有可能误判，有可能并不存在。不过，只要我们调整哈希函数的个数、位图大小跟要存储数字的个数之间的比例，那就可以将这种误判的概率降到非常低。

弄懂了布隆过滤器，我们今天的爬虫网页去重的问题，就很简单了。

我们用布隆过滤器来记录已经爬取过的网页链接，假设需要判重的网页有 10 亿，那我们可以用一个 10 倍大小的位图来存储，也就是 100 亿个二进制位，换算成字节，那就是大约 1.2GB。之前我们用散列表判重，需要至少 100GB 的空间。相比来讲，布隆过滤器在存储空间的消耗上，降低了非常多。

> 那我们再来看下，利用布隆过滤器，在执行效率方面，是否比散列表更加高效呢？

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

> 总结引申

今天，关于**搜索引擎爬虫网页去重问题**的解决，我们从散列表讲到位图，再讲到布隆过滤器。布隆过滤器非常适合这种不需要 100% 准确的、允许存在小概率误判的大规模判重场景。除了爬虫网页去重这个例子，还有比如**统计一个大型网站的每天的 UV 数**，也就是每天有多少用户访问了网站，我们就可以使用布隆过滤器，对重复访问的用户，进行去重。

> 课后思考

问：假设我们有 1 亿个整数，数据范围是从 1 到 10 亿，如何快速并且省内存地给这 1 亿个数据从小到大排序？

答：

传统的做法：1亿个整数，存储需要400M空间，排序时间复杂度最优 N×log(N)

使用位图算法：数字范围是1到10亿，用位图存储125M就够了，然后将1亿个数字依次添加到位图中，然后再将位图按下标从小到大输出值为1的下标，排序就完成了，时间复杂度为 N

问：还记得我们在哈希函数（下）讲过的利用分治思想，用散列表以及哈希函数，实现海量图库中的判重功能吗？如果我们允许小概率的误判，那是否可以用今天的布隆过滤器来解决呢？你可以参照我们当时的估算方法，重新估算下，用布隆过滤器需要多少台机器？