大数据处理

源网址：https://blog.csdn.net/Wantbebetter/article/details/121671219

解题技巧

• 哈希函数可以把数据按照种类均匀分流
• 布隆过滤器用于集合的建立与查询，并可以节省大量空间
• 一致性哈希解决数据服务器的负载管理问题
• 利用并查集结构做岛问题的并行计算
• 位图解决某一范围上数字的出现情况，并可以节省大量空间
• 利用分段统计思想、并进一步节省大量空间
• 利用堆、外排序来做多个处理单元的结果合并

经典问题：

1、设计算法找到每日访问百度出现次数最多的IP地址

• 思路
  数据量肯定非常大，不能全加载到内存里面进行计算，所以需要拆分
  所以设计一个算法，使所有的ip进行处理后，可能有10W条结果，将对应的ip分别存放至这十万个文件中
  根据文件的大小，在最大的那一批文件里进行计算统计即可

2、两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件的交集

• 这题其实很傻逼，限定100亿整数和1G内存了
  其实已经限定了用位图进行处理了，两个位图（二进制），进行异或计算即可
• 但是可以延伸出另外一个问题
  那些树没有出现
  位置为0的数字就是没出现的

3、两个文件，分别有100亿个string，我们只有1G内存，如何找到两文件交集？分别给出精确算法和近似算法

• 近似算法
  首先要想到布隆过滤器，也可以自己写个算法，但是没必要。
  布隆过滤器，不存在的肯定不存在，存在的可能不存在
  所以做判断
• 精确算法
  设计个算法，使每个string 都有10W个结果，相同结果的string 保存在同一个文件内，第一个大文件后缀1，第二个大文件后缀2，然后前缀相同的进行比较，假设超内存了，可以345.

  4、一个词典，包含N个英文单词，现在任意给一个字符串，设计算法找出包含这个字符串的所有英文单词

  非常傻逼的题
  算了
  刚看过树的数据机构，用多叉树来处理
  先将词典全部遍历，生成26颗树（原则上来说，二十六个字母开头的单词都会有），跟节点就是字母，各种子节点就是字符串的后缀，然后用字符串在与26颗树进行匹配