大数据排序或取重或去重相关问题解决方案

Q：TC群里有人发消息说在10亿个数据中找出所有的重复数，内存限制10M。貌似百度面试题。

“笨一休”大牛的初步提出了个方法：

1，利用hash对所有数进行取模（比如%1M），利用余数进行分1K组；

2，再对1K组，内部进行hash查重复数。

 

晚上上自习时候想了想，觉得不需要设计hash函数来进行操作，一来很难设计出无冲突的hash函数，二来每次进行hash时候涉及取模操作，比较费时。想了个方法如下：

1，将10亿=10^9个数划分为N（N=1K或500）个区间段，即使用N个文件存储。每个文件代表一个区间（1《x《1M放在f1中，1M<x《2M放在f2中之类......自己设定）。

2，扫描所有数，通过比较将数划分到N个区间中；（可以采取判定树方式比较）

3，分别对N个文件，进行操作（取去重或排序之类），（此时可以对每个文件中的数据，进行内存操作。数组便可完成。因为数据随机，平均每个文件的数据个数为2M/1M个，2M/1M*4=8M/4M <10M；这里也可以用bit操作更省内存）。