大数据专题
数据规模估计
搜索关键词字符串的平均长度 50 字节 1亿个字符串大约需要 5G 的内存空间 1亿个 int 大约需要 400 M 1亿个 1 字节数据为 1 G
TopK 问题
寻找n个数据中前K大的数据？ time: Nlog(K) 维护一个大小为 K 的小顶堆，满了之后与堆顶元素进行比较，比堆顶元素大，则删除堆顶元素，并将新数放入堆；比堆顶小，则不作处理
搜索 10 亿个日志文件中最热门的10个搜索关键词？ 可能会有大量的重复，使用散列表进行计数，如果数据量太大，为避免散列表扩容引起极高的内存占用，可以先通过哈希取模分片到 10 个小文件中，每个文件用散列表和堆维护得到每个文件中的 Top10 ，然后再将这 100 个关键词用堆再次 top10
排序
- 有100个有序小文件，每个文件大小 100 MB，要求合并到有序大文件？ 维护一个元素为 100 的小顶堆，每次从100个文件中分别读取一行，然后把最小的弹出插入大文件中，然后从含有最小行的文件中继续读取放入堆中，直到所有文件的数据都放入大文件中
实时排名
使用跳跃表查找小于某值的节点个数
我们可以用于一个大小为1,000,000的数组表示积分和排名的对应关系，其中ranks表示积分s所对应的排名。初始化时，rank数组可以由user_score表在O(n)的复杂度内计算而来。用户排名的查询和更新基于这个数组来进行。查询积分s所对应的排名直接返回ranks即可，复杂度为O(1)；当用户积分从s变为s+n，只需要把ranks到ranks+n-1这n个元素的值增加1即可，复杂度为O(n)
实时TopN
维护一个小顶堆，一个散列表维护堆中的用户ID，如果某个用户的分数更改并且在堆中，那么就直接修改堆中的数据；如果不在堆中，比较新用户的分数是否大于堆顶用户分数，如果是，那么将该堆顶弹出，新用户入堆，更新散列表。实时排序可以交给客户端来完成
大数据敏感词过滤
AC自动机 + Trie 树
大数据去重？
10 亿个 url ，每个 URL 大小小于 56 B，要求去重，内存4G ？ 答： 先多机（至少14台）分治排序，然后多机逐批进行合并，最后 O(1) 空间和 O(N) 时间进行去重。
如果是数字去重的话可以使用 bitmap
两个大数据的文件，找出共同的行记录？
- 布隆过滤 错误率小于 0.01，bitmap中位的个数需要为输入个数 n 的13倍
- 哈希分片 共同的行的 hash 值会被分到相同的文件对，比如 A文件的第 1 个小文件和B文件的第1个小文件，然后再依次把 A 的小文件读入建立 hashmap，然后再读入 B 的小文件进行检测