引子

有一个1G大小文件，每一行是一个词，词的大小不超过16byte， 内存限制是1M，返回频数最高的100个词。

  • 读取每个词，计算hashCode 按hashCode 取模 5000， 将该值存到 5000个小文件，每个文件是200KB （1G/ 5000) 。
  • 如果某个文件超过1MB（内存大小），进行二次哈希，直到每个文件大小不超过1MB。
  • 对每个小文件，统计每个词的出现频率。 使用Trie 字典树 + 最小堆。

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

100万个数中找出最大的100个数。（变形： 10亿个Long整数，怎样找到其中最大的10个）。

  • N log N ?

1000万个数中找出出现频率最高的100个数。

解决大数据问题的思路

裁剪问题，将大问题转为小问题。

数据剪裁的套路：

  • Maping， 最常见的是Hashing，通过散列函数 bitmap通过位数据的特殊实现Partition
  • Filtering， bloom-fiter
  • Tree, 原数据入树， 例如字符串前缀查询

堆， 跳表