哈希表的使用场景--大数据中的前k大
今年看到学长面试的时候,还是会问到一下基本的算法问题,在这之前对于这些还是有一定的理解,只是不能很透彻的清楚其中的原理、奥妙,在这之前也转载过关于hash表使用的文章,成这个星期天,想从头到尾把一个问题搞清楚,现在觉得这个越来越重要了,抓住一段时间,搞清楚一个问题,比泛泛的知道很多更加实在,尤其是在读书的时候更是这样,在这段时间里,自己也看了不少书,但是回头一想,还是什么都没明白,到不如在某一块上非常清楚,逐个击破!!!下面就以一个网上很常见的面试题作为分析对象:
一个10G的关键词的log,找出词频最高的前K个词,设可用内存为2G左右
分析:
本题的难点主要有两处,一是如何在有限内存下对大文件进行词频统计;二是如何在有限内存的下找出词频的前K大个词。
1)词频统计
词频统计,我们很自然的会想到使用hash。但是直接hash内存是放不下的啊…怎么办?其实对于有限内存下的大文件处理,都可总结为归并的思想,不过要注意归并时的分段亦是有学问的。请比较归并a与归并b方法
- 归并a:将数据分为5段,分别对每段在内存中hash统计并将统计结果写入文件,然后合并分段的hash。
问题:表面看来不错的主意,实则有很大问题,稍微想一下,a方法存在一个主要的困难就是,hash合并的时候相当于同时在5个文件中判断是否有相同的词,要这样做会非常繁琐。
怎么解决呢?我当时是受编程珠玑中第一题(排序一千万个32位整数)启发的,它在归并分段的时候,不是直接的简单分段,而是每段取一个范围比如第一段取0~249000之间的数,这样有什么好处?将来的各段数彼此间是没有交集(重复)的。所以我们的思想就是要让这10G的关键词分段后各小段没有交集,这样hash合并就没有问题了。请看归并b
- 归并b:将数据分为5段,分段时 对每个词hash,hash值在一个范围中的词语分到一个段中,然后对于每个分段统计的hash结果直接都写入一个文件即可。
分析:使用hash分段,保证各小段没有重复的词。我当时想的方法是将词语的首字拼音打头一样的分在一段中,例如“五谷丰登”、“万箭齐发”分到一起,都是w打头的拼音,其实这仅仅只是hash的一种。