GO·NOTE

一份 Go 开发工程师的学习笔记

0%

只用2GB内存在20亿个整数中找到次数最多的数

【题目】

有一个包含了 20 亿个全是 32 位整数的大文件,在其中找到出现次数最多的数

【要求】

内存限制 2GB

【难度】

★☆☆☆

【解答】

想要在很多整数中找到次数最多的数,通常的做法是使用哈希表对出现的每一个数做此统计,
哈希表的 key 是某一个整数, value 是这个数出现的次数。就本题来说,一共有20亿个
数,哪怕只是一个数出现 20 亿次,用 32 位的整数也可以表示其出现的次数而不产生溢出,
所以哈希表的 key 需要占用 4B,value 也是 4B。那么哈希表的一条记录(key,value)需要
占用 8B, 当哈希表记录数为 2亿个时,需要至少 1.6GB的内存。

如果 20 亿个数中不同的数超过2亿种,最极端的情况是 20 亿个数都不同,那么哈希表中
可能需要产生 20 亿条记录,这样内存会不够用,所以一致性哈希表统计 20 亿个数的方法
时有很大风险的。

解决方案是把包含 20 亿个数的大文件用哈希函数分成 16个小文件,根据哈希函数的性质,
同一种数不可能被散列到不同的小文件上,同时每个小文件中不同的数一定不会大于2亿种,
假设哈希函数足够优秀。然后对每一个小文件用哈希表统计其中每种出现的次数,这样我们就
得到了16个小文件种各自出现次数最多的数,还有各自的次数统计。接下来只要选出这 16 个
小文件各自的第一名种谁出现的次数最多即可。

把一个大的集合通过哈希函数分配到多台机器中,活着分配到多个文件里,这种技巧是处理
大数据面试题时最常用的技巧之一。但是到底分配多少个机器、分配多少个文件,在解题时
一定要确定下来。