怎么在海量数据中找出重复次数最多的一个

发布网友发布时间：2022-04-23 14:49

共1个回答

热心网友时间：2023-09-08 22:48

假设我们可以用的内存是64M，总的数据量是1024*64M即64G。
1、首先预设1024个文件作为“桶”，依次读取原始数据的记录，每读到一条记录就进行哈希计算，获得的哈希值余上1024，把这条记录放到那个桶里，即：
bucket_num = hash(record) % 1024
2、由于相同的记录哈希值一定相同，所以重复数据一定落入同一个桶内，对于落入同一个桶内的数据，直接为该数据的数量加一，即桶内的条目都是唯一的，各自记录自己的总重复数量。
3、当一个桶的体积达到64M的时候（应该非常罕见），为该桶增加一个子桶，新的数据进来的时候先在父桶内找相同记录，没有的话在放入子桶，重复数设置为1。
4、当全部数据读取完之后，依次对1024个桶（及其子桶）进行内部排序，可以一次性把64M的数据读入内存快速排序即可，然后再归并父桶及其子桶，最终得到1024个桶内的最大重复记录。
5、对这1024个桶的最大值进行比较，获得一个最终的最大值。