海量数据处理算法.pdf

海量数据处理 所谓海量数据处理，是指基于海量数据的存储、处理或操作。因为数据量太大，导致要么 无法在较短时间内迅速解决，要么无法一次性装入内存。 事实上，对于时间问题，可以采用巧妙的算法搭配合适的数据结构（如布隆过滤器、散 列、位图、堆、数据库、倒排索引、Trie 树）来解决；对于空间问题，可以采取分而治之 的方法（如利用散列映射），把规模大的数据转化为规模小的，最终各个击破。 处理海量数据问题有很多种方法，本章介绍 10 种典型方法：散列分治、多层划分、 MapReduce、外排序、位图、布隆过滤器、Trie 树、数据库、倒排索引和 simhash 算 法。 本章将摒弃绝大部分的细节，重点谈方法和模式论，且注重用通俗、直白的语言阐述相关 问题。最后，有一点必须强调的是，本章内容是基于面试题的分析基础进行讲述的，具体 实践过程中要视具体情况具体分析，且各个场景下需要考虑的细节也远比本章所描述的任 何一种解决方案复杂得多。 6.1 基础知识 ：STL 容器 先具体了解一下 STL 容器，它是许多解决方案的基础。 一般来说，STL 容器分两种：序列式容器和关联式容器。序列式容器包括 vector、list、 deque、stack、queue 、heap 等，而关联式容器中，每笔数据或每个元素都有一个键 （key ）和一个值（value ），即所谓的键值对。当元素被插入到关联式容器中时，容器的 内部结构（可能是红黑树，也可能是散列表）便会依照其值大小，以某种特定规则将这个 元素放置于适当的位置。 C++ 11 标准之前，旧标准规定标准的关联式容器分为 set （集合）和map （映射）两 大类，以及这两大类的衍生体 multiset （多键集合）和 multimap （多键映射），这些容 器均基于 red-black tree （红黑树）实现。此外，还有另一类非标准的关联式容器，即 hashtable （散列表），以及以hashtable 为底层实现机制的 hash_set （散列集合）、 hash_map （散列映射）、hash_multiset （散列多重集合）和hash_multimap （散列多 重映射）。也就是说，set、map、multiset 和 multimap 都内含一个红黑树，而 hash_set、hash_map、hash_multiset、和 hash_multimap 都内含一个 hashtable1 ， 具体关系如图 6-1 所示。 图 6-1 set、map、multiset 和 multimap set 同 map 一样，所有元素都会根据元素的键自动排序，因为 set 和 map 两者的所有操 作都只是转而调用红黑树的操作行为。不过，值得注意的是，两者都不允许任意两个元素 有相同的键。 不同的是，set 的元素不像 map 那样可以同时拥有值和键，set 元素的值就是键，键就是 值，而 map 的所有元素都是 pair ，同时拥有值和键，pair 的第一个元素被视为键，第二 个元素被视为值。 至于 multiset 和 multimap ，它们的特性及用法与set 和 map 几乎相同，唯一的差别就 是它们允许键重复，即所有的插入操作基于红黑树的 insert_equal()而非 insert_unique()。 hash_set、hash_map、hash_multiset和 hash_multimap hash_set 和 hash_map 的一切操作都是基于 hashtable 的。不同的是，hash_set 同 set 一样，同时拥有值和键，且值就是键，键就是值，而 hash_map 同 map 一样，每一个元 素同时拥有一个值和一个键，所以其使用方式和 map 基本相同。另外，因为 hash_set 和 hash_map 都是基于 hashtable 的，而 hashtable 没有自动排序功能，所以 hash_set 和 hash_map 都不具备自动排序功能。 至于 hash_multiset 和 hash_multimap ，它们的特性与multiset 和 multimap 几乎完全 相同，唯一的差别就是 hash_multiset 和 hash_multimap 的底层实现机制是 hashtable （区别于multiset 和 multi