算法面试系列： 海量数据处理总结

海量数据处理总结

Table of Contents generated with DocToc

• 1、分而治之/hash映射 + HashMap统计 + 堆/快速/归并排序
• 2、多层划分
• 3、Bloom filter/Bitmap
• 4、Trie树/数据库/倒排索引
  • Trie树
  • 数据库索引
  • 倒排索引
• 5、外排序
• 6、 分布式处理之Hadoop/MapReduce

海量数据处理六种方法：

1. 分而治之/hash映射 + HashMap统计 + 堆/快速/归并排序
2. 多层划分
3. Bloom filter/Bitmap
4. Trie树/数据库/倒排索引
5. 外排序
6. 分布式处理之Hadoop/MapReduce

1、分而治之/hash映射 + HashMap统计 + 堆/快速/归并排序

适用范围：类似"出现次数最多前10"、“热门前10查询”、"频率最高前100"等跟频数排序有关问题

步骤：

1. 分而治之/hash映射：由于数据量过大，内存不足于存储所有数据，所以要需要将大文件（取模映射）化成小文件，逐个解决，最后汇总。
2. HashMap统计：当大文件转化了小文件后，那么便可以统计元素的出现次数，这里除了HasHMap，还可以使用trie树/搜索二叉树/红黑树
3. 堆排序：统计完了之后便进行排序，可先