海量数据应用

1.海量数据查重

1亿整数 - > 1 G

1.哈希表 -> 不考虑内存(O(1))

2.分治

eg:有一个大文件有50亿数据，内存限制400M,求重复元素和重复个数。

50亿 -> 40G数据 40G / 400M = 120 个小文件

大文件映射为小文件：

data0.txt data1.txt ...... data127.txt

遍历大文件元素，根据每一个元素进行哈希映射，映射到对应小文件中。

data % 127 = file_index

值相同的，通过一样的哈希函数会分配到相同的小文件。

最后将小文件用哈希表求重复。

3.Bloom Filter：布隆过滤器

4.字符串类型 ：字典树

2.海量数据TopK

1.大根堆/小根堆

2.快排分割函数