北京哪个医院皮肤科好 http://pf.39.net/bdfyy/bjzkbdfyy/140802/4439528.html前言
一般而言，标题含有“秒杀”，“99%”，“史上最全/最强”等词汇的往往都脱不了哗众取宠之嫌，但进一步来讲，如果读者读罢此文，却无任何收获，那么，我也甘愿背负这样的罪名:-)，同时，此文可以看做是对这篇文章：十道海量数据处理面试题与十个方法大总结的一般抽象性总结。
毕竟受文章和理论之限，本文将摒弃绝大部分的细节，只谈方法/模式论，且注重用最通俗最直白的语言阐述相关问题。最后，有一点必须强调的是，全文行文是基于面试题的分析基础之上的，具体实践过程中，还是得具体情况具体分析，且各个场景下需要考虑的细节也远比本文所描述的任何一种解决方法复杂得多。
OK，若有任何问题，欢迎随时不吝赐教。谢谢。
01
何谓海量数据处理？
所谓海量数据处理，无非就是基于海量数据上的存储、处理、操作。何谓海量，就是数据量太大，所以导致要么是无法在较短时间内迅速解决，要么是数据太大，导致无法一次性装入内存。
那解决办法呢?针对时间，我们可以采用巧妙的算法搭配合适的数据结构，如Bloomfilter/Hash/bit-map/堆/数据库或倒排索引/trie树，针对空间，无非就一个办法：大而化小，分而治之（hash映射），你不是说规模太大嘛，那简单啊，就把规模大化为规模小的，各个击破不就完了嘛。
至于所谓的单机及集群问题，通俗点来讲，单机就是处理装载数据的机器有限(只要考虑cpu，内存，硬盘的数据交互)，而集群，机器有多辆，适合分布式处理，并行计算(更多考虑节点和节点间的数据交互)。
再者，通过本blog内的有关海量数据处理的文章：BigDataProcessing，我们已经大致知道，处理海量数据问题，无非就是：
分而治之/hash映射+hash统计+堆/快速/归并排序；双层桶划分Bloomfilter/Bitmap；Trie树/数据库/倒排索引；外排序；分布式处理之Hadoop/Mapreduce。
下面，本文第一部分、从set/map谈到hashtable/hash_map/hash_set，简要介绍下set/map/multiset/multimap，及hash_set/hash_map/hash_multiset/hash_multimap之区别(万丈高楼平地起，基础最重要)，而本文第二部分，则针对上述那6种方法模式结合对应的海量数据处理面试题分别具体阐述。
02
第一部分、从set/map谈到hashtable/hash_map/hash_set
稍后本文第二部分中将多次提到hash_map/hash_set，下面稍稍介绍下这些容器，以作为基础准备。一般来说，STL容器分两种，
序列式容器(vector/list/deque/stack/queue/heap)，关联式容器。关联式容器又分为set(集合)和map(映射表)两大类，以及这两大类的衍生体multiset(多键集合)和multimap(多键映射表)，这些容器均以RB-tree完成。此外，还有第3类关联式容器，如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等等。
{name:July,
sex:male,
age:23}
set/map/multiset/multimap
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/hash_multiset/hash_multimap
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），所以它们的元素都不会被自动排序，不过也都允许键值重复。
所以，综上，说白了，什么样的结构决定其什么样的性质，因为set/map/multiset/multimap都是基于RB-tree之上，所以有自动排序功能，而hash_set/hash_map/hash_multiset/hash_multimap都是基于hashtable之上，所以不含有自动排序功能，至于加个前缀multi_无非就是允许键值重复而已。如下图所示：
此外，关于什么hash，请看blog内此篇文章；关于红黑树，请参看blog内系列文章，关于hash_map的具体应用：请看这里，关于hash_set：请看此文。
OK，接下来，请看本文第二部分、处理海量数据问题之六把密匙。
03
第二部分、处理海量数据问题之六把密匙
密匙一、分而治之/Hash映射+Hash_map统计+堆/快速/归并排序
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
既然是海量数据处理，那么可想而知，给我们的数据那就一定是海量的。针对这个数据的海量，我们如何着手呢?对的，无非就是分而治之/hash映射+hash统计+堆/快速/归并排序，说白了，就是先映射，而后统计，最后排序：
1、分而治之/hash映射：针对数据太大，内存受限，只能是：把大文件化成(取模映射)小文件，即16字方针：大而化小，各个击破，缩小规模，逐个解决
2、hash_map统计：当大文件转化了小文件，那么我们便可以采用常规的hash_map(ip，value)来进行频率统计。
3、堆/快速排序：统计完了之后，便进行排序(可采取堆排序)，得到次数最多的IP。
具体而论，则是：“首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如%，把整个大文件映射为个小文件，再找出每个小文中出现频率最大的IP（可以采用hash_map对那个文件中的所有IP进行频率统计，然后依次找出各个文件中频率最大的那个IP）及相应的频率。然后再在这个最大的IP中，找出那个频率最大的IP，即为所求。”--十道海量数据处理面试题与十个方法大总结。
关于本题，还有几个问题，如下：
1、Hash取模是一种等价映射，不会存在同一个元素分散到不同小文件中的情况，即这里采用的是mod算法，那么相同的IP在hash取模后，只可能落在同一个文件中，不可能被分散的。因为如果两个IP相等，那么经过Hash(IP)之后的哈希值是相同的，将此哈希值取模（如模），必定仍然相等。
2、那到底什么是hash映射呢？简单来说，就是为了便于计算机在有限的内存中处理big数据，从而通过一种映射散列的方式让数据均匀分布在对应的内存位置(如大数据通过取余的方式映射成小树存放在内存中，或大文件映射成多个小文件)，而这个映射散列方式便是我们通常所说的hash函数，设计的好的hash函数能让数据均匀分布而减少冲突。尽管数据映射到了另外一些不同的位置，但数据还是原来的数据，只是代替和表示这些原始数据的形式发生了变化而已。
OK，有兴趣的，还可以再了解下一致性hash算法，见blog内此文第五部分
