数据结构与算法(19)：海量数据处理

所谓海海量量数据处理理，其实很简单，海海量量，海海量量，何谓海海量量，就是数据量量太⼤大，所以导致要么是⽆无法再较短时间内迅速解决，要么是数据太⼤大，导致⽆无法⼀一次性装⼊入内存。那解决办法呢？针对时间，我们可以采⽤用巧妙的算法搭配合适的数据结构，如BloomFilter、Hash、Bit-map、堆、数据库或倒排索引、trie，针对空间，⽆无⾮非就⼀一个办法：⼤大⽽而化⼩小、分⽽而治之、hash映射，你不不是说规模太⼤大嘛，那简单啊，就把规模⼤大化为规模⼩小的，各个击破不不就完了了嘛。⾄至于所谓的单机及集群问题，通俗点来讲，单机就是处理理装载数据的机器器有限（只要考虑CPU、内存、硬盘的数据交互），⽽而集群，机器器有多辆，适合分布式处理理，并⾏行行计算（更更多考虑节点和节点间的数据交互）。再者，通过本blog内的有关海海量量数据处理理的⽂文章，我们已经⼤大致知道，处理理海海量量数据问题⽆无⾮非就是：1.分⽽而治之、hash映射+hash统计+堆、快速、归并排序；2.双层桶划分3.BloomFilter、bitmap4.trie树、数据库、倒排索引；5.外排序6.分布式处理理之Hadoop、Mapreduce下⾯面，本⽂文第⼀一部分、从Set、Map谈到hashtable、hash_map、hash_set，简要介绍下Set、Map、Multiset、Multimap，及hash_set、hash_map、hash_multiset、hash_multimap之区别，⽽而第⼆二部分，则针对上述6种⽅方法模式结合对应的海海量量数据处理理⾯面试题分别具体阐述。稍后本⽂文第⼆二部分将多次提到hash_map、hash_set，下⾯面稍稍介绍下这些容器器，以作为基础准备。⼀一般来说，STL容器器分为两种序列列式容器器：vector、list、deque、stack、queue、heap数据结构与算法（19）：海海量量数据处理理⼀一、何谓海海量量数据处理理？⼆二、从Set、Map谈到hashtable、hash_map/hash_set关联式容器器：关联式容器器⼜又分为set（集合）和map（映射表）两⼤大类，以及这两⼤大类的衍⽣生体（多键集合）和multimap（多键映射表），这些容器器均以RB-tree完成。此外，还有第三类关联容器器，如hashtable（散列列表），以及以hashtable为底层机制完成的hash_set（散列列集合）、hash_map（散列列映射表）、hash_multiset(散列列多键集合)、hash_multimap（散列列多键映射表）。也就是说，set、map、multiset、multimap都内含⼀一个RB-tree，⽽而hash_set、hash_map、hash_multiset、hash_multimap都内含⼀一个hashtable。所谓关联式容器器，类似关联式数据库，每笔数据或每个元素都有⼀一个键值（key）和⼀一个实值（value），即所谓的Key-Value（键-值对）。当元素被插⼊入到关联式容器器中时，容器器内结构（RB-Tree、hashtable）便便依照其键值⼤大⼩小，以某种特定规则将这个元素放置于适当位置。包括在⾮非关联式数据库中，⽐比如，在MongoDB内，⽂文档（document）是昀基本的数据组织形式，每个⽂文档也是以Key-Value(键-值对)的⽅方式组织起来。⼀一个⽂文档可以有多个Key-Value组合，每个Value可以是不不同的类型，⽐比如String、Integer、List等等。set，同map⼀一样，所有元素都会根据元素的键值⾃自动被排序，因为set、map两者的所有操作，都是调⽤用RB-tree的操作⾏行行为，不不过，值得注意的是，两者都不不允许两个元素有相同的键值。不不同的是，set的元素不不像map那样可以同时拥有实值（value）和键值（key），set元素的键值就是实值，实值就是键值，⽽而map的所有元素都是pair，同时拥有实值（value）和键值（key），pair的第⼀一个元素被视为键值，第⼆二个元素被视为实值。⾄至于multiset、multimap，他们的特性及⽤用法和set、map完全相同，唯⼀一的差别就在于它们允许键值重复，即所有的插⼊入操作基于RB-tree的insert——equal()⽽而⾮非insert_unique()。hash_set/hash_map，两者的⼀一切操作都是基于hashtable之上。hash_set同set⼀一样，同时拥有实值和键值，且实质就是键值，键值就是实值，⽽而hash_map同map⼀一样，每⼀一个元素同时拥有⼀一个实值(value)和⼀一个键值(key)，所以其使⽤用⽅方式，和上⾯面的map基本相同。但由于hash_set/hash_map都是基于hashtable之上，所以不不具备⾃自动排序功能。为什什么?因为hashtable没有⾃自动排序功能。⾄至于hash_multiset/hash_multimap的特性与上⾯面的multiset/multimap完全相同，唯⼀一的差别就是它们hash_multiset/hash_multimap的底层实现机制是hashtable（⽽而multiset/multimap，上⾯面说了了，底层实现机制是RB-tree），所以它们的元素都不不会被⾃自动排序，不不过也都允许键值重复。name:July,Sex:male,age:232.1关联式容器器之集合：set/map/multimap/multimap2.2关联式容器器之映射表：hash_set/hash_map/hash_multiset/hash_multimap所以，综上，说⽩白了了，什什么样的结构决定其什什么样的性质，因为set/map/multiset/multimap都是基于RB-tree之上，所以有⾃自动排序功能，⽽而hash_set/hash_map/hash_multiset/hash_multimap都是基于hashtable之上，所以不不含有⾃自动排序功能，⾄至于加个前缀multi_⽆无⾮非就是允许键值重复⽽而已。这⼀一部分介绍处理理海海量量数据问题的第⼀一把密钥：分⽽而治之、哈希映射+Hash统计+堆、快速、归并排序（1）海海量量⽇日志数据，提取出某⽇日访问既然是海海量量数据处理理，那么可想⽽而知，给我们的数据那就⼀一定是海海量量的。针对这个数据的海海量量，我们如何着⼿手呢?对的，⽆无⾮非就是分⽽而治之/hash映射+hash统计+堆/快速/归并排序，说⽩白了了，就是先映射，⽽而后统计，昀后排序：1.分⽽而治之/hash映射：针对数据太⼤大，内存受限，只能是：把⼤大⽂文件化成(取模映射)⼩小⽂文件，即16字⽅方针：⼤大⽽而化⼩小，各个击破，缩⼩小规模，逐个解决2.hash统计：当⼤大⽂文件转化了了⼩小⽂文件，那么我们便便可以采⽤用常规的Hashmap(ip，value)来进⾏行行频率统计。3.堆/快速排序：统计完了了之后，便便进⾏行行排序(可采取堆排序)，得到次数昀多的IP具体⽽而论，“⾸首先是这⼀一天，并且是访问百度的⽇日志的IP取出来，逐个写到⼀一个⼤大⽂文件中。注意到IP是32位的，昀多有个个IP。同样可以采⽤用映射的⽅方法，⽐比如%1000，把整个⼤大⽂文件映射为1000个⼩小⽂文件，再找出每个⼩小⽂文件中出现频率昀⼤大的IP（可以采⽤用Hash_map对那1000个⽂文件中的所以IP进⾏行行频率统计，然后依次找出各个⽂文件中频率昀⼤大的那个IP）及相应的频率。然后再在这1000个昀⼤大的IP中，找出那个频率昀⼤大的IP，即为所求。”关于本题，还有⼏几个问题：1.Hash取模是⼀一种等价映射，不不会存在同⼀一个元素分散到不不同⼩小⽂文件中的情况，即这⾥里里采⽤用的是mod1000算法，那么相同的IP在hash取模后，只可能落在同⼀一个⽂文件中，不不可能被分散的。因为如果两个IP相等，那么经过Hash（IP）之后的哈希值是相同的，将此哈希值取模，必定仍然相等。2.那到底什什么是hash映射呢？简单来说，就是为了了便便于计算机在有限的内存中处理理⼤大数据，从⽽而通过⼀一种映射散列列的⽅方式让数据均匀分布在对应的内存位置（如⼤大数据通过取余的⽅方式映射城⼩小数存放在内存中，或者⼤大⽂文件映射成多个⼩小⽂文件），⽽而这个映射散列列⽅方式便便是我们通常所说的hash函数，设计的好的hash函数能让数据均匀分布⽽而减少冲突。尽管数据映射到了了三、处理理海海量量数据问题之六把密钥密钥⼀一：分⽽而治之/Hash映射+Hash_map统计+堆/快/归并排序232另外⼀一些不不同的位置，但数据还是原来的数据，只是代替和表示这些原始数据的形式发⽣生了了变化⽽而已。（2）寻找热⻔门查询，300万个查询字符串串中统计昀热⻔门的10个查询原题：搜索引擎会通过⽇日志⽂文件把⽤用户每次检索使⽤用的所有检索串串都记录下来，每个查询串串的⻓长度为1~255字节。假设⽬目前有⼀一千万个记录（这些查询串串的重复度⽐比较⾼高，虽然总数是1千万，但如果除去重复后，不不超过3百万个。⼀一个查询串串的重复度越⾼高，说明查询它的⽤用户越多，也就是越热⻔门），请你统计昀热⻔门的10个查询串串，要求使⽤用的内存不不能超过1G。由上⾯面那题可知，数据⼤大则划分为⼩小的，⽐比如⼀一亿个IP求Top10，可先%1000将IP分到1000个⼩小⽂文件中去，并保证⼀一种IP只出现在⼀一个⽂文件中，再对每个⼩小⽂文件中的IP进⾏行行Hashmap计数统计并按数量量排序，昀后归并或者昀⼩小堆⼀一次处理理每个⼩小⽂文件的top10以得到昀后的结。但如果数据规模⽐比较⼩小，能⼀一次性装⼊入内存呢？⽐比如这第⼆二题，虽然有⼀一千万个Query，但是由于重复度⽐比较⾼高，因此事实上只有300万的Query，每个Query255Byte，因此我们可以考虑把它们都放进内存中去（300万个字符串串假设没有重复，都是昀⼤大⻓长度，那么昀多占⽤用内存3M*1K/4=0.75G。所以可以将所有字符串串都存放在内存中进⾏行行处理理），⽽而现在只需要⼀一个合适的数据结构，在这⾥里里，HashTable绝对是我们优先的选择。所以我们放弃分⽽而治之、Hash映射的步骤，直接上Hash统计，然后排序。所以，针对此类典型的TopK问题，采取的对策往往是：Hashmap+堆。如下所示：1.Hash_map统计：先对这批海海量量数据预处理理。具体⽅方法是：维护⼀一个Key为Query字符串串，Value为该QUery出现次数的HashTable，即Hash_map(Query,Value)，每次读取⼀一个Query，如果该字符串串不不在table内，则加⼊入该字串串，并且将Value值设为1；如果该字串串在Table中，那么将该字串串的计数加1即可。昀终我们在O(N)的时间复杂度内⽤用Hash表完成了了统计。2.堆排序：借助堆这个数据结构，找出TopK，时间复杂度为NlogK。即借助堆结构，我们可以在log量量级的时间内查找和调整。因此，维护⼀一个K（该题⽬目中是10）⼤大⼩小的⼩小根堆，然后遍历300万的Query，分别和根元素进⾏行行对⽐比。所以，我们昀终的时间复杂度是，（N为1000万，N'是300万）这篇⽂文章中所述的堆排序思路路：“维护k个元素的昀⼩小堆，即⽤用容量量为K的昀⼩小堆存储昀先遍历到的k个数，并假设它们即是昀⼤大的k个数，建堆费时，并调整堆，费时，这样我们就有（kmin设为⼩小顶堆中昀⼩小元素）。继续遍历数列列，每次遍历⼀一个元素x，与堆顶元素⽐比较，若，则更更新堆（⽤用时），否则不不更更新堆。这样下来，总费时。此⽅方法得益于在堆中，查找等各项操作时间复杂度均为logk。”当然，你也可以采⽤用trie树，关键字域存该查询串串出现的次数，没有出现为0。昀后⽤用10个元素的昀⼩小推来对出现频率进⾏行行排序。O(N)+N·O(logK)O