所谓海量数据处理，是指基于海量数据的存储、处理或操作。因为数据量太大，导致要么无法在较短时间内迅速解决，要么无法一次性装入内存。

事实上，对于时间问题，可以采用巧妙的算法搭配合适的数据结构（如布隆过滤器、散列、位图、堆、数据库、倒排索引、Trie 树）来解决；对于空间问题，可以采取分而治之的方法（如利用散列映射），把规模大的数据转化为规模小的，最终各个击破。

处理海量数据问题有很多种方法，本文介绍5种典型方法：散列分治、多层划分、位图、布隆过滤器、Trie树。

散列分治

方法介绍

对于海量数据而言，由于无法将其一次性装进内存进行处理，不得不将其通过散列映射的方法分割成相应的小块数据，然后再针对各个小块数据通过hash_map进行统计或其他操作。

那么什么是散列映射呢？简单来说，为了方便计算机在有限的内存中处理大量数据，通过映射的方式让数据均匀分布在对应的内存位置上（例如，大数据通过取余的方式映射成小数据存放在内存中，或把大文件映射成多个小文件），而这种映射的方式通常通过散列函数进行映射，好的散列函数能让数据均匀分布而减少冲突。

问题实例

寻找Top IP

从海量日志数据中提取出某日访问百度（www.baidu.com）次数最多的那个IP。

分析： 百度作为国内第一大搜索引擎，每天访问它的IP数量巨大，如果想一次性把所有IP数据装进内存处理，内存容量通常不够，故针对数据量太大、内存受限的情况，可以把大文件转化成（取模映射）小文件，从而大而化小，逐个处理。简言之，先映射，而后统计，最后排序。

解法： 具体分为下述三个步骤。

（1）分而治之/散列映射。先将该日访问百度的所有IP从访问日志中提取出来，然后逐个写入一个大文件中，接着采取散列映射的方法（如hash(IP) % 1000），把整个大文件的数据映射到1000个小文件中2。

（2）hash_map统计。大文件转化成了小文件，便可以采用hash_map(ip, value)分别对1000个小文件的IP进行频率统计，找出每个小文件中出现频率最高的IP，总共1000个IP。

（3）堆/快速排序。统计出1000个频率最高的IP后，依据它们各自频率的大小进行排序（可采取堆排序），找出最终那个出现频率最高的IP，即为所求。

寻找热门查询

搜索引擎会通过日志文件把用户每次检索所使用的所有查询串都记录下来，每个查询串的长度为1～255字节。假设目前有1000万条查询记录（但是，因为这些查询串的重复度比较高，所以虽然总数是 1000 万，但如果除去重复后，查询串query不超过300万个），请统计其中最热门的10个查询串，要求使用的内存不能超过1 GB。

分析： 一个查询串的重复度越高说明查询它的用户越多，也就是越热门。如果是1亿个IP求Top 10，可先%1000将IP分到1000个小文件中去，并保证一个IP只出现在一个文件中，再对每个小文件中的IP进行hash_map统计并按数量排序，最后用归并或者最小堆依次处理每个小文件中的Top 10以得到最后的结果。

但是对于本题，是否也需要先把大文件弄成小文件呢？根据题目描述，虽然有1000万个查询，但是因为重复度比较高，去除重复后，事实上只有300万个查询，每个查询为255字节，所以可以考虑把它们全部放进内存中去（假设300万个字符串没有重复，都是最大长度，那么最多占用内存3000000 × 255 = 765MB=0.765GB，所以可以将所有字符串都存放在内存中进行处理）。

考虑到本题中的数据规模比较小，能一次性装入内存，因而放弃分而治之/散列映射的步骤，直接用hash_map统计，然后排序。事实上，针对此类典型的Top k问题，采取的对策一般都是“分而治之/散列映射（如有必要）+ hash_map+堆”。

解法：

（1）hash_map统计。对这批海量数据进行预处理，用hash_map完成频率统计。具体做法是：维护一个键为query、value为该query出现次数的hash_map，即hash_map(query, value)，每次读取一个query，如果该query不在hash_map中，那么将该query放入hash_map中，并将它的value值设为1；如果该query在hash_map中，那么将该query的计数value加1即可。最终我们用hash_map在O(n)的时间复杂度内完成了所有query的频率统计。

（2）堆排序。借助堆这种数据结构，找出Top k，时间复杂度为O(n'logk)。也就是说，借助堆可以在对数级的时间内查找或调整移动。因此，维护一个k（该题目中是10）大小的最小堆，然后遍历300万个query，分别和根元素进行比较，最终的时间复杂度是O(n) + O(n'logk)，其中n为1000万，n'为300万。

关于上述过程中的第2步（堆排序），进一步讲，可以维护k个元素的最小堆，即用容量为k的最小堆存储最先遍历到的k个数，并假设它们就是最大的k个数，建堆费时O(k)，有k1 > k2 >…> kmin（设kmin为最小堆中最小元素）。继续遍历整个数列剩下的n−k个元素，每次遍历一个元素x，将其与堆顶元素进行比较，若x > kmin则更新堆（x入堆，每次调整堆费时O(log k)），否则不更新堆。这样下来，总费时O(k + (n−k)log k ) = O(nlogk)。此方法得益于在堆中查找等各项操作的时间复杂度均为O(log k)。

当然，也可以采用Trie树，结点里存该查询串出现的次数，没有出现则为0，最后用10个元素的最小堆来对出现频率进行排序。

寻找出现频率最高的100个词

有一个1 GB大小的文件，里面每一行是一个词，每个词的大小不超过16字节，内存大小限制是1 MB。请返回出现频率最高的100个词。

解法：

（1）分而治之/散列映射。按先后顺序读取文件，对于每个词x，执行hash(x)%5000，然后将该值存到5000个小文件（记为x0, x1,…, x4999）中。此时，每个小文件的大小大概是200 KB。当然，如果其中有的小文件超过了1 MB，则可以按照类似的方法继续往下分，直到分解得到的所有小文件都不超过1MB。

（2）hash_map统计。对每个小文件采用hash_map/Trie树等数据结构，统计每个小文件中出现的词及其相应的出现次数。

（3）堆排序或者归并排序。取出出现次数最多的100个词（可以用含100个结点的最小堆）后，再把100个词及相应的出现次数存入文件中，这样又得到5000个文件。最后对这5000个文件进行归并（可以用归并排序）。

寻找Top 10

有海量数据分布在100台电脑中，请想个办法高效统计出这批数据出现次数最多的Top 10。

解法一： 如果同一个数据元素只出现在某一台机器中，那么可以采取以下步骤统计出现次数为Top 10的数据元素。

（1）堆排序。在每台电脑上求出Top 10，可以采用包含10个元素的堆完成。（求Top 10小用最大堆，求Top 10大用最小堆。比如，求Top 10大，首先取前10个元素调整成最小堆，假设这10个元素就是Top 10大，然后扫描后面的数据，并与堆顶元素进行比较，如果比堆顶元素大，那么用该元素替换堆顶，然后再调整为最小堆，否则不调整。最后堆中的元素就是Top 10大。）

（2）组合归并。求出每台电脑上的Top 10后，把这100台电脑上的Top 10组合起来，共1000个数据，再根据这1000个数据求出Top 10就可以了。

解法二： 但是，如果同一个元素重复出现在不同的电脑中呢？举个例子，给定两台机器，第一台机器的数据及各自出现的次数为a（53）、b（52）、c（49）、d（49）、e（0）、f（0）（括号里的数字代表某个数据出现的次数），第二台机器的数据及各自出现的次数为a（0）、b（0）、c（49）、d（49）、e（51）、f（50），求所有数据中出现次数最多的Top 2。

很明显，如果先求出第一台机器的Top 2——a（53）和b（52），然后再求出第二台机器的Top 2——e（51）和f（50），最后归并a（53）、b（52）、e（51）和f（50），得出最终的Top 2——a（53）和b（52）并非实际的Top 2，因为实际的Top 2是c（49 + 49）和d（49 + 49）。

有两种方法可以解决这个问题。

• 遍历一遍所有数据，重新散列取模，使同一个元素只出现在单独的一台电脑中，然后采取上面所说的方法，统计每台电脑中各个元素的出现次数，找出Top 10，继而组合100台电脑上的Top 10，找出最终的Top 10。

• 蛮力求解，直接统计每台电脑中各个元素的出现次数，然后把同一个元素在不同机器中的出现次数相加，最终从所有数据中找出Top 10。

查询串的重新排列

有10个文件，每个文件的大小是1 GB，每个文件的每一行存放的都是用户的查询串query，每个文件的query都可能重复。请按照query的频度排序。

解法一： 分为以下三个步骤。

（1）散列映射。顺序读取10个文件，按照hash(query)%10的结果将query写入另外10个文件（记为a0, a1,…, a9）中。这样，新生成的每个文件的大小约为1 GB（假设散列函数是随机的）。

（2）hash_map统计。找一台内存在2 GB左右的机器，依次用hash_map(query, query_count)来统计每个query出现的次数。注意，hash_map(query, query_count)是用来统计每个 query 的出现次数的，而不是存储它们的值，query 出现一次则query_count+1。

（3）堆排序、快速排序或者归并排序。利用快速排序、堆排序或者归并排序按照出现次数进行排序，将排好序的query和对应的query_cout输出到文件中。这样就得到了10个排好序的文件（记为b0, b1,…, b9）。最后，对这10个文件进行归并排序（内排序与外排序相结合）。

解法二： 一般情况下，query的总量是有限的，只是重复的次数比较多而已，对于所有的query，可能一次性就可以加入内存。这样就可以采用Trie树、hash_map等直接统计每个query出现的次数，然后按出现次数做快速排序、堆排序或者归并排序就可以了。

解法三： 与解法一类似，但在做完散列，分成多个文件后，可以交给多个文件，采用分布式架构来处理（如MapReduce），最后再进行合并。

寻找共同的URL

给定a和b两个文件，各存放50亿个URL，每个URL占64字节，内存限制是4 GB。请找出a和b文件中共同的URL。

解法： 可以估计出每个文件的大小为5000000000×64=320 GB，远远大于内存限制的4 GB，所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

（1）分而治之/散列映射。遍历文件a，对每个URL求取hash(URL)%1000，然后根据所取得的值将URL分别存储到1000个小文件中（记为 a0, a1,…, a999）。这样每个小文件大约为300 MB。遍历文件b，采取和a相同的方式将URL分别存储到1000小文件中（记为b0, b1,…, b999）。这样处理后，所有可能相同的URL都在对应的小文件中（a0对应b0, a1对应b1,…, a999对应b999），不对应的小文件不可能有相同的URL。然后只要求出1000对小文件中相同的URL即可。

（2）hash_set统计。求每对小文件中相同的URL时，可以把其中一个小文件的URL存储到hash_set中，然后遍历另一个小文件的每个URL，看其是否在刚才构建的hash_set中，如果在，就是共同的URL，保存到文件里就可以了。

举一反三

寻找最大的100个数

从100万个数中找出最大的100个数。

提示：

选取前100个元素并排序，记为序列L。然后依次扫描剩余的元素x，与排好序的100个元素中最小的元素比较，如果比这个最小的元素大，就把这个最小的元素删除，利用插入排序的思想将x插入到序列L中。依次循环，直到扫描完所有的元素。复杂度为O(108×100)。也可以利用快速排序的思想，每次分割之后只考虑比主元大的一部分，直到比主元大的一部分比100多的时候，采用传统排序算法排序，取前100个。复杂度为O(108× 100)。此外，还可以用一个含100个元素的最小堆来完成，复杂度为O(108× log100)。

统计10个出现次数最多的词

一个文本文件有上亿行甚至10亿行，每行中存放一个词，要求统计出其中出现次数最多的前10个词。

解法一： 如果文件比较大，无法一次性读入内存，可以采用散列取模的方法，将大文件分解为多个小文件，对单个小文件利用hash_map统计出每个小文件中10个出现次数最多的词，然后再进行归并处理，找出最终的10个出现次数最多的词。

解法二： 通过散列取模将大文件分解为多个小文件后，除了可以用hash_map统计出每个小文件中10个出现次数的词，也可以用Trie树统计每个词出现的次数，最终同样找出出现次数最多的前10个词（可用堆来实现）。

寻找出现次数最多的数

怎样在海量数据中找出重复次数最多的一个？

提示：

先做散列，然后求模，映射为小文件，求出每个小文件中重复次数最多的一个数，并记录重复次数，最后找出上一步求出的数据中重复次数最多的一个，即是所求。

统计出现次数最多的前n个数据

有上千万或上亿个数据（有重复），统计其中出现次数最多的前n个数据。

提示：

上千万或上亿个数据在现在的机器的内存中应该能存下，所以考虑采用hash_map、搜索二叉树、红黑树等来进行次数统计，然后取出前n个出现次数最多的数据，这一步可以用堆完成。

1000万个字符串的去重

有1000万个字符串，其中有些字符串是重复的，请把重复的字符串全部去掉，保留没有重复的字符串。

提示：

本题用Trie树比较合适，hash_map也行。当然，也可以先散列成小文件分开处理再综合。

多层划分

方法介绍

多层划分法本质上还是遵循分而治之的思想。因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后在一个可以接受的范围内进行查找。

问题实例

寻找不重复的数

在2.5亿个整数中找出不重复的整数的个数。注意，内存空间不足以容纳这2.5亿个整数。

分析： 类似于鸽巢原理，因为整数个数为232，所以，可以将这232个数划分为28个区域（比如，用一个文件代表一个区域），然后将数据分到不同的区域，最后不同的区域再利用位图进行统计就可以直接解决了。也就是说，只要有足够的内存空间，就可以很方便地解决。

寻找中位数

找出5亿个int型数的中位数。

分析： 首先将这5亿个int型数划分为216个区域，然后读取数据统计落到各个区域里的数的个数，根据统计结果就可以判断中位数落到哪个区域，并知道这个区域中的第几大数刚好是中位数。然后，第二次扫描只统计落在这个区域中的那些数就可以了。

实际上，如果不是int型而是int64型，经过3次这样的划分即可降低到能够接受的程度。也就是说，可以先将5亿个int64型数划分为224个区域，确定每个数是其所在区域的第几大数，然后再将该区域分成220个子区域，确定是子区域的第几大数，最后当子区域里的数的个数只有220个时，就可以利用直接寻址表进行统计。

6.4　MapReduce

方法介绍

MapReduce是一种计算模型，简单地说就是将大批量的工作或数据分解执行（称之为Map），然后再将结果合并成最终结果（称之为Reduce）。这样做的好处是，可以在任务被分解后通过大量机器进行分布式并行计算，减少整个操作的时间。可以说，MapReduce的原理就是一个归并排序，它的适用范围为数据量大而数据种类少以致可以放入内存的场景。MapReduce模式的主要思想是将要执行的问题（如程序）自动拆分成Map和Reduce的方式，其流程如图6-2所示。

在数据被分割后，通过Map函数将数据映射到不同的区块，分配给计算机集群处理，以达到分布式计算的效果，再通过Reduce函数的程序将结果汇总，从而输出需要的结果。

MapReduce 借鉴了函数式程序设计语言的设计思想，其软件实现是指定一个Map函数，把键值对映射成新的键值对，形成一系列中间结果构成的键值对，然后把它们传给 Reduce 函数，把具有相同中间形式的键值对合并在一起。Map 函数和Reduce函数具有一定的关联性。

问题实例

寻找n2个数的中数

一共有n台机器，每台机器上有n个数，每台机器最多存O(n)个数并对它们进行操作。如何找到n2个数的中数（median）？

6.5　外排序

方法介绍

顾名思义，所谓外排序就是在内存外面的排序。当要处理的数据量很大而不能一次性装入内存时，只能将数据放在读写较慢的外存储器（通常是硬盘）上。

外排序通常采用的是一种“排序-归并”的策略。在排序阶段，先读入能放在内存中的数据，将其排序后输出到一个临时文件，依次进行，将待排序数据组织为多个有序的临时文件，而后在归并阶段将这些临时文件组合为一个大的有序文件，即为排序结果。

举个例子。假定现在有一个含有20个数据{5, 11, 0, 18, 4, 14, 9, 7, 6, 8, 12, 17, 16, 13, 19, 10, 2, 1, 3, 15}的文件A，但使用的是一次只能装4个数据的内存，所以可以每趟对4个数据进行排序，即5路归并，具体方法如下述步骤所示。

首先把“大”文件A分割为a1、a2、a3、a4、a5这5个小文件，每个小文件包含4个数据：

• a1文件的内容为{5, 11, 0, 18}；

• a2文件的内容为{4, 14, 9, 7}；

• a3文件的内容为{6, 8, 12, 17}；

• a4文件的内容为{16, 13, 19, 10}；

• a5文件的内容为{2, 1, 3, 15}。

然后依次对5个小文件进行排序：

• a1文件完成排序后的内容为{0, 5, 11, 18}；

• a2文件完成排序后的内容为{4, 7, 9, 14}；

• a3文件完成排序后的内容为{6, 8, 12, 17}；

• a4文件完成排序后的内容为{10, 13, 16, 19}；

• a5文件完成排序后的内容为{1, 2, 3, 15}。

最终进行多路归并，完成整个排序。最后，整个大文件A文件完成排序后变为{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19}。

问题实例

给107个数据的磁盘文件排序

给定一个文件，里面最多含有n个不重复的正整数（也就是说可能含有少于n个不重复的正整数），且其中每个数都小于等于n（n = 107）。请输出一个按从小到大升序排列的包含所有输入整数的列表。假设最多有大约1 MB的内存空间可用，但磁盘空间足够。要求运行时间在5分钟以内，10秒为最佳结果。

解法一：位图方案

你可能会想到把磁盘文件进行归并排序，但题目假设只有1 MB的内存空间可用，所以归并排序这种方法不行。

熟悉位图的人可能会想到用位图来表示这个文件集合3。比如，用一个20位长的字符串来表示一个所有元素都小于20的简单的非负整数集合，如集合{1, 2, 3, 5, 8, 13}，在字符串中将集合中各个数对应的位置置为1，没有对应的数的位置置为0，用字符串表示为01110100100001000000。

针对本题的107个数据的磁盘文件排序问题，可以这么考虑：由于每个7位十进制整数表示一个小于1000万的整数，所以可以使用一个具有1000万个位的字符串来表示这个文件，当且仅当整数i在文件中存在时，字符串中的第i位置为1。

采取这个位图的方案是因为考虑到本问题的特殊性：

• 输入数据限制在相对较小的范围内；

• 数据没有重复；

• 其中的每条记录都是单一的整数，没有任何其他与之关联的数据。

所以，此问题用位图的方案可以分为以下三步进行解决。

（1）将所有的位都初始化为0。

（2）通过读入文件中的每个整数来建立集合，将每个整数对应的位都置为1。

（3）检验每一位，如果该位为1，就输出对应的整数。

经过以上三步后，就产生了一个有序的输出文件。令n为位图向量中的位数（本例中为10 000 000），伪代码表示如下：

// 磁盘文件排序位图方案的伪代码 // 第一步：将所有的位都初始化为0  for i ={0,....n}　　  
　　 bit[i]=0;  
// 第二步：通过读入文件中的每个整数来建立集合，将每个整数对应的位都置为1for each i in the input file　　 
　　 bit[i]=1;  
// 第三步：检验每一位，如果该位为1，就输出对应的整数  for i={0...n}　　  
　　 if bit[i]==1　　　　
　　　　 write i on the output file

上述的位图方案共需要扫描输入数据两次，具体执行步骤如下。

（1）第一次只处理1～5 000 000的数据，这些数都是小于5 000 000的。对这些数进行位图排序，只需要约5 000 000/8=625 000字节，即0.625 MB，排序后输出。

（2）第二次扫描输入文件时，只处理5 000 001～10 000 000的数据，也只需要0.625 MB（可以使用第一次处理申请的内存）。因此，这种位图的方法总共只需要0.625 MB。

但是，很快我们就意识到，用位图方案的话，需要约1.2 MB（若每条记录是8位的正整数，则空间消耗约等于107/(102410248)≈ 192 MB）的空间，而现在只有1 MB的可用存储空间，所以严格来说，用位图方法还是不行4。那么究竟该如何处理呢？

解法二：多路归并

诚然，在面对本题时，通过计算分析出可以用上述解法一这样的位图法解决。但实际上，很多时候我们都面临着这样一个问题：文件太大，无法一次性放入内存中计算处理。这时候应该怎么办呢？分而治之，大而化小，也就是把整个大文件分为若干大小的几块，然后分别对每一块进行排序，最后完成整个过程的排序。k趟算法可以在O(kn)的时间开销内和O(n/k)的空间开销内完成对最多n个小于n的无重复正整数的排序。比如，可分为2块（k=2时，一趟反正占用的内存只有1.25/2 MB），即1～5 000 000和5 000 001～10 000 000。先遍历一趟，排序处理1～5 000 000的整数（用5 000 000/8=625 000字节的存储空间来排序1～5 000 000的整数），然后再第二趟，对5 000 001～1 000 000的整数进行排序处理。

解法总结

本节中位图和多路归并两种方案的时间复杂度及空间复杂度的比较如表6-1所示。

表6-1

多路归并的时间复杂度为O(k × n/k × log n/k) = O(nlogn)5。但严格来说，还要加上读写磁盘的时间，而此算法的绝大部分时间也正是浪费在读写磁盘的步骤上。

位图

方法介绍

什么是位图

所谓位图，就是用一个位（bit）来标记某个元素对应的值，而键就是该元素。由于采用了位为单位来存储数据，因此可以大大节省存储空间。

位图通过使用位数组来表示某些元素是否存在，可进行数据的快速查找、判重、删除。

来看一个具体的例子。假设我们要对0～7中的5个元素（4, 7, 2, 5, 3）进行排序（假设这些元素没有重复），此时就可以采用位图的方法来达到排序的目的。因为要表示8个数，所以只需要8位，由于8位等于1字节，所以开辟1字节的空间，并将这个空间的所有位都置为0，如图6-3所示。

然后遍历这5个元素。因为待排序序列的第一个元素是4，所以把4对应的位重置为1（可以这样操作：p + (i/8) | (001 << (i % 8)) 。当然，这里的操作涉及big-endian和little-endian6的情况，这里默认为big-endian），又由于是从0开始计数的，所以把第5位重置为1，如图6-4所示。

然后再处理待排序序列的第二个元素7，将第8个位重置为1。接着再处理待排序序列的第三个元素2，一直到处理完所有的元素。将相应的位置为1后，这时候内存的位的状态如图6-5所示。

现在遍历一遍这个位区域，将某位是1的位的编号（2, 3, 4, 5, 7）输出，这样就达到了排序的目的。

问题实例

电话号码的统计

已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。8位数字最多组成99 999 999个号码，大概需要99兆位，大概十几兆字节的内存即可。

2.5亿个整数的去重

在2.5亿个整数中找出不重复的整数。注意，内存不足以容纳这2.5亿个整数。

分析： 采用2位图（每个数分配2位，00表示不存在，01表示出现一次，10表示出现多次，11无意义），共需内存232 × 2=1 GB内存，可以接受。然后扫描这2.5亿个整数，查看位图中相对应的位，如果是00就变为01，如果是01就变为10，如果是10就保持不变。扫描完之后，查看位图，把对应位是01的整数输出即可。也可以先划分成小文件，然后在小文件中找出不重复的整数，并排序，最后归并，归并的同时去除重复的数。

整数的快速查询

给定40亿个不重复的没排过序的unsigned int型整数，然后再给定一个数，如何快速判断这个数是否在这40亿个整数当中？

分析： 可以用位图的方法，申请512 MB的内存，一个位代表一个unsigned int型的值。读入40亿个数，设置相应的位，读入要查询的数，查看相应位是否为1，如果为1表示存在，如果为0表示不存在。

布隆过滤器

方法介绍

我们经常会遇到这样的问题：判断一个元素是否在一个集合中。常见的做法是用散列表实现集合，然后遇到一个新的元素时，在散列表中查找：如果能找到则意味着存在于集合中，反之不存在。但是散列表有一个弊端，它耗费的空间太大。本节来看一种新的方法，即布隆过滤器（Bloom filter）。

布隆过滤器是一种空间效率很高的随机数据结构，它可以看成是对位图的扩展。其结构是长度为n（如何计算最优n，后面会给出）的位数组，初始化为全0。当一个元素被加入集合中时，通过k个散列函数将这个元素映射成一个位数组中的k个点，并将这k个点全部置为1。

在检索一个元素是否在一个集合中时，我们只要看看这个元素被映射成位阵列的k个点是不是都是1，就能大致判断出集合中有没有那个元素：如果这k个点中有任何一个点为0，则被检索元素在集合中一定不存在；如果这k个点都是1，则被检索元素很可能在集合中。

但是，布隆过滤器也有它的缺点或不足，即它有一定的误判率——在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误判为属于这个集合。因此，它不适合那些“零误判”的应用场合。而在能容忍低误判率的应用场合下，布隆过滤器通过极少的误判换取了存储空间的极大节省。

集合表示和元素查询

下面我们来具体看看布隆过滤器是如何用位数组表示集合的。如图6-6所示，初始状态时，布隆过滤器是一个包含m位的位数组，每一位都置为0。

对于S={x1, x2,…, xn}这样一个n个元素的集合，布隆过滤器使用k个互相独立的散列函数分别将集合S={x1, x2,…, xn}中的每个元素映射到{1,…, m}的范围中。对于任意一个元素x，第i个散列函数映射的位置hi(x)就会被置为1（1≤i≤k）。

注意，如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在图6-7中，k=3且有两个散列函数选中同一个位置（从左边数第五位，即第二个1处）。

于此，在判断y是否属于图6-6所示的集合S={x1, x2, …, xn}时，对y应用k次散列函数，如果所有hi(y)的位置都是1（1≤i≤k），那么就认为y是集合S={x1, x2, …, xn}中的元素，否则就认为y不是集合中的元素。

例如，图6-8中的y1可以确定不是集合S={x1, x2, …, xn}中的元素，因为y1有两处指向了0位，而y2可能属于这个集合，也可能刚好是一个误判。

误判率估计

前面已经提到，布隆过滤器在判断一个元素是否属于它表示的集合时会有一定的误判率（false positive rate），下面就来估计一下这个误判率的大小。

为了简化模型，假设kn < m且各个散列函数是完全随机的。每插入一个新元素第一个散列函数就会把过滤器中的某个位置为1，因此任意一个位被置成1的概率为1/m，反之，它没被置为1（依然是0）的概率为1−1/m。如果这个元素的k个散列函数都没有把某个位置为1，即在做完k次散列后，某个位还是0（意味着k次散列都没有选中它）的概率就是(1−1/m)k。如果插入第二个元素，某个位依然没有被置为1的概率为(1−1/m)2k，所以如果插入n个元素都还没有把某个位置为1的概率为(1−1/m)kn。

也就是说，当集合S = {x1, x2, …, xn}中的所有元素都被k个散列函数映射到m位的位数组中时，这个位数组中某一位还是0的概率是

为了简化运算，可以令

，则有

如果令

为位数组中0的比例，则

的数学期望

。

在

已知的情况下，误判率为

为位数组中1的比例，

表示k次散列都刚好选中1的区域，即误判率。上式中的第二步近似在前面已经提到了，现在来看第一步近似。p'只是

的数学期望，在实际中

的值有可能偏离它的数学期望值。M. Mitzenmacher已经证明，位数组中0的比例非常集中地分布在它的数学期望值的附近。因此，第一步近似得以成立。分别将p和p'代入上式中，得

与p'和f ' 相比，使用p 和f 通常在分析中更为方便。

最优的散列函数个数

既然布隆过滤器要靠多个散列函数将集合映射到位数组中，那么应该选择几个散列函数才能使元素查询时的误判率降到最低呢？这里有两个互斥的理由：如果散列函数的个数多，那么在对一个不属于集合的元素进行查询时得到0的概率就大；但是，如果散列函数的个数少，那么位数组中的0就多。为了得到最优的散列函数个数，我们需要根据上一节中的误判率公式进行计算。

先用p 和f 进行计算。注意到f = exp(k ln(1−ekn/m))，我们令g = k ln(1−ekn/m)，只要让g取到最小，f 自然也取到最小。由于p = e−kn/m，可以将g写成

根据对称性法则可以很容易看出：当p = 1/2，也就是k = (m/n)ln2≈0.693m/n时，g取得最小值。在这种情况下，最小误判率f等于(1/2)k≈(0.6185)m/n。另外，注意到p是位数组中某一位仍是0的概率，所以p = 1/2对应着位数组中0和1各一半。换句话说，要想保持误判率低，最好让位数组有一半还空着。

需要强调的一点是，p = 1/2时误判率最小这个结果并不依赖于近似值p和f。同样，对于f' = exp(k ln(1−(1−1/m)kn))，g' = k ln(1−(1−1/m)kn)，p' = (1−1/m)kn，可以将g'写成

同样，根据对称性法则可以得到当p' = 1/2时，g'取得最小值。

位数组的大小

下面来看看在不超过一定误判率的情况下，布隆过滤器至少需要多少位才能表示全集中任意n个元素的集合。假设全集中共有u个元素，允许的最大误判率为є，下面来求位数组的位数m。

假设X为全集中任取n个元素的集合，F(X)是表示X的位数组。那么，对于集合X中任意一个元素x，在s = F(X)中查询x都能得到肯定的结果，即s能够接受x。显然，由于布隆过滤器引入了误判，s能够接受的不仅仅是X中的元素，它还能够接受є(u−n)个误判。因此，对于一个确定的位数组来说，它能够接受总共n +є (u−n)个元素。在n +є (u−n)个元素中，s真正表示的只有其中n个，所以一个确定的位数组可以表示

个集合。m位的位数组共有2m个不同的组合，进而可以推出，m位的位数组可以表示

个集合。全集中n个元素的集合总共有

个，因此要让m位的位数组能够表示所有n个元素的集合，必须有

即

上式中的近似前提是n和єu相比很小，这也是实际情况中常常发生的。根据上式，我们得出结论：在误判率不大于є的情况下，m至少要等于n log2(1/є)才能表示任意n个元素的集合。

上一节中我们曾算出当k = m/n ln2时误判率f最小，这时f = (1/2)k= (1/2)mln2 / n。现在令f ≤є，可以推出

这个结果比前面算得的下界n log2(1/)大了log2≈1.44倍。这说明，在散列函数的个数取到最优时，要让误判率不超过є，m至少需要取到最小值的1.44倍。

布隆过滤器可以用来实现数据字典，进行数据的判重或者集合求交集。

问题实例

寻找通过URL

给定A和B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4 GB，请找出A和B两个文件中共同的URL。

分析： 如果允许有一定的误判率，可以使用布隆过滤器，4 GB内存大概可以表示340亿位。将其中一个文件中的URL使用布隆过滤器映射到这340亿位，然后挨个读取另外一个文件中的URL，检查这两个URL是否相同，如果是，那么该URL应该是共同的URL。如果是3个乃至n个文件呢？读者可以继续独立思考。

垃圾邮件过滤

用过电子邮箱的朋友都知道，经常会收到各种垃圾邮件，可能是广告，可能是病毒，所以邮件提供商每天都需要过滤数以几十亿计的垃圾邮件，请想一个办法过滤这些垃圾邮件。

分析： 比较直观的想法是把常见的垃圾邮件地址存到一个巨大的集合中，然后遇到某个新邮件就将它的地址和集合中的全部垃圾邮件地址一一进行比较，如果有元素与之匹配，则判定新邮件为垃圾邮件。

虽然本节开始部分提到集合可以用散列表实现，但它太占空间。例如，存储1亿个电子邮件地址就需要1.6 GB内存，存储几十亿个电子邮件地址就需要上百GB的内存，虽然现在有的机器内存达到了上百GB，但终究是少数。

事实上，如果允许一定的误判率的话，可以使用布隆过滤器。解决了存储的问题后，可以利用贝叶斯分类鉴别一份邮件是否为垃圾邮件，减少误判率。

Trie树

方法介绍

什么是Trie树

Trie树，即字典树，又称单词查找树或键树，是一种树形结构，常用于统计和排序大量字符串等场景中（但不仅限于字符串），且经常被搜索引擎用于文本词频统计。它的优点是最大限度地减少无谓的字符串比较，查询效率比较高。

Trie树的核心思想是以空间换时间，利用字符串的公共前缀来降低查询时间的开销，以达到提高效率的目的。

它有以下三个基本性质。

（1）根结点不包含字符，除根结点外每一个结点都只包含一个字符。

（2）从根结点到某一结点的路径上经过的字符连接起来，即为该结点对应的字符串。

（3）每个结点的所有子结点包含的字符都不相同。

Trie树的构建

先来看一个问题：假如现在给定10万个长度不超过10个字母的单词，对于每一个单词，要判断它出没出现过，如果出现了，求第一次出现在第几个位置。这个问题该怎么解决呢？

如果采取最笨拙的方法，对每一个单词都去查找它前面的单词中是否有它，那么这个算法的复杂度就是O(n2)。显然对于10万的范围难以接受。

换个思路想：假设要查询的单词是abcd，那么在它前面的单词中，以b，c，d，f之类开头的显然就不必考虑了，而只要找以a开头的单词中是否存在abcd就可以了。同样，在以a开头的单词中，只要考虑以b作为第二个字母的，一次次缩小范围和提高针对性，这样一个树的模型就渐渐清晰了。

因此，如果现在有b、abc、abd、bcd、abcd、efg和hii这6个单词，可以构建一棵图6-9所示的Trie树。

如图6-9所示，从根结点遍历到每一个结点的路径就是一个单词，如果某个结点被标记为红色（如图中加黑点的节点），就表示这个单词存在，否则不存在。那么，对于一个单词，只要顺着它从根结点走到对应的结点，再看这个结点是否被标记为红色就可以知道它是否出现过了。把这个结点标记为红色，就相当于插入了这个单词。这样一来，查询和插入可以一起完成，所用时间仅仅为单词长度（在这个例子中，便是10）。这就是一棵Trie树。

我们可以看到，Trie树每一层的结点数是26i级别的。所以，为了节省空间，还可以用动态链表，或者用数组来模拟动态，而空间的花费不会超过单词数乘以单词长度。

查询

Trie 树是简单且实用的数据结构，通常用于实现字典查询。我们做即时响应用户输入的Ajax搜索框时，就是以Trie树为基础数据结构的。本质上，Trie树是一棵存储多个字符串的树。相邻结点间的边代表一个字符，这样树的每条分支代表一个子串，而树的叶结点则代表完整的字符串。和普通树不同的地方是，相同的字符串前缀共享同一条分支。

下面再举一个例子。给出一组单词inn、int、ate、age、adv、ant，可以得到图6-10所示的Trie树。

可以看出以下几条。

• 每条边对应一个字母。

• 每个结点对应一项前缀。叶结点对应最长前缀，即单词本身。

• 单词inn与单词int有共同的前缀'in'，所以它们共享左边的一条分支（根结点→i→in）。同理，ate、age、adv和ant共享前缀'a'，所以它们共享从根结点到结点a的边。

查询操纵非常简单。例如，要查找int，顺着路径i→ in→int就找到了。

搭建Trie的基本算法也很简单，无非是逐一把每个单词的每个字母插入Trie树。插入前先看前缀是否存在：如果存在，就共享，否则创建对应的结点和边。例如，要插入单词add，就有下面几步。

（1）考察前缀'a'，发现边a已经存在。于是顺着边a走到结点a。

（2）考察剩下的字符串'dd'的前缀'd'，发现从结点a出发，已经有边d存在。于是顺着边d走到结点ad。

（3）考察最后一个字符'd'，这次从结点ad出发没有边d了，于是创建结点ad的子结点add，并把边ad→add标记为d。

问题实例

10个频繁出现的词

在一个文本文件中大约有1万行，每行1个词，要求统计出其中出现次数最频繁的10个词。

分析： 用Trie树统计每个词出现的次数，时间复杂度是O(nl)（l表示单词的平均长度），最终找出出现最频繁的前10个词（可用堆来实现，时间复杂度是O(nlog10)。

寻找热门查询

搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来，每个查询串的长度为1～255字节。假设目前有1000万条记录（因为查询串的重复度比较高，虽然总数是1000万，但是如果去除重复，不超过300万个）。请统计最热门的10个查询串，要求使用的内存不能超过1 GB。（一个查询串的重复度越高，说明查询它的用户越多，也就越热门。）

分析： 可以利用Trie树，观察关键字在该查询串出现的次数，若没有出现则为0。最后用10个元素的最小堆来对出现频率进行排序。