提纲：

🔥海量数据处理

• 前缀树Trie

• 分治归并

• Bloom Filter

• Bit Map

一、海量数据处理

1. 前缀树 Trie

• Q：有 xx 个文件存储了 xx 个 query 语句，取出出现次数前 k 高的语句

• A：query 语句，是一种重复率很高的字符串类型，并且不同的 query 语句也可能有相同的前缀，对于这类数据（还有手机号码，英语单词）等，可以采用 Trie 前缀树来进行存储，然后使用大根堆 PriorityQueue，遍历 Trie时取出最多的元素

2.分治归并

• Q：有（多个文件）海量的 xxx 数据，统计出现次数前 k 多的 xxx

• A：可以采用分治归并，将海量数据按 HashCode % 1024 分别存储到 1024 个小文件中，

• 再从每个小文件中选出出现次数前 k 多的数据，最后再归并，从这 1024 * k 个数据中找出前 k 多的数据

  • #不一定是 1024，按实际需求算

  • #计算 HashCode 方法主要有 平方取中/位移叠加（jdk的 String）/全随机，但要保证能够均匀哈希

  • #可以分批归并

• Q：有两个文件，各存储了海量的 xxx 数据，要求取出两个文件中相同的数据

• A：可以采用分支归并，将 A 的数据按 HashCode % 1024 分别存储至 a0...ai...a1024，按同样的哈希算法，将 B 的数据分治，再分别比较 a0 与 b0，ai 与 bi，最后将比较得到