引言
学习完布隆过滤器,相当于是入门了海量数据处理.然后我们再来看看这一道题.
有一个包含20亿全是32位整数的大文件,在其中找到出现次数最多的数
内存大小为2GB
分析
如果不是海量处理的话,我们会使用一个哈希函数,来记录词(key)和它出现的频率(value),因为这是32位的数,所以key的大小是4B,value的大小也设置为4B这样的话一条hash记录就是8B,所以当哈希表的记录数为2亿个时,这个时候就需要1.6GB的内存大小.
但是如果是20亿个不同的数那,一条记录时8GB,那么20亿条记录就是16GB.这样使用一个hash是可能的,那么这个时候该如何处理那?
我们把包含20亿个数分解成小文件,那分解成几个那,我们想象以下,一块2GB的内存,存着key和value,那么其中能存的记录就是1GB(1GB存key,1GB存value)key那就是文件中的数,所以一次能够查1GB的记录,20亿条数据,20亿条数据对应着16GB的存储空间,一次能查1GB,所有要分成16分小文件,一份小文件就是1GB,装入到2GB中1GB是key,1GB是value,具体操作我们截取书中的内容
图片.png
注意到我们分成16个小文件是通过hash函数分的,因为hash函数的性质,同一种数就绝对不可能分在同一个文件上.
这样就完成了.....
