10月11日，腾讯web前端面试

　　一个数组 var arr = ['abc'，'ddadbc'，'adbdcd'，'abcqew'.......] 长度一万， 用有效率的方法计算出包含被元素出现多的。

　　单机5G内存，磁盘200T的数据，分别为字符串，然后给定一个字符串，判断这200T数据里面有没有这个字符串，怎么做?

　　如果查询次数会非常的多， 怎么预处理?

　　点评：如果数据是200g且允许少许误差的话，可以考虑用布隆过滤器Bloom Filter：http://blog.csdn.net/v_july_v/article/details/6685894。但本题是200T，得另寻良策。

　　OK，以下是@cy 提供的题解(暴露出的一个问题是题意不是特别明确，因为题解中有不少自己的假设，所以日后各位面试时一定要跟面试官彻底弄清题意再作答，包括各种使用条件)：

　　“①. 内存和数据比是 5GB / 200TB， 约为 1 比 4w， 所以trie啥的不用想了， 的是hash.

　　②. 简单的假设每个字符串是相对短的(只要不会超过5GB)

　　1. 几MB， 甚至百MB的字符串也能处理， 但是确实对终的效果有很大影响， 如果只是部分case特别大，可以特殊处理下.

　　③. 一个字符串块 在内存中需要一个 条目 来标识

　　1. value 需要 8 字节， key约为4字节

　　1. 200TB总共有 200 * 2^40 位， 地址空间至少为48个bit， 存储长度用16bit则一个条目的value 需要8个字节

　　1. 这里的长度是用来存一个 字符串块 的长度， 单位可以优化为KB， 甚至MB， 16bit肯定是够的

　　1. key用4个字节有些紧张， 可以考虑占用部分长度的位

　　1. 长度也可以不在条目中出现， 而是在块头出现， 但这样取块的时候有可能浪费， 也有可能要取多次.

　　2. 所谓一个 字符串块 是hash值相同的字符串挨个存在一起， 从而得到的字符串块.

　　④. 这样的话， 5GB 可以存放多 5GB / 8 约为 4亿个条目.

　　⑤. 把原来的200TB字符串挨个的hash， 并按hash排序后， 存起来， 建立索引.

　　1. hash值可以用md5之类的散列到足够开， 然后 mod 4亿值来求

　　⑥. 根据重排后的文件， 建立索引， key为hash值， value为前面说到的， 该hash对应字符串块在文件中的偏移， 和 块的长度.

　　⑦查询时， 根据hash值， 找到该字符串可能在的字符串， 然后将整个字符串读出来， 用kmp比较即可.

　　200TB的数据， 被划到 4亿 个字符块当中， 平均一块应该在 800KB 附近， 考虑到hash不均衡， 一般也是几MB的样子，

　　比较起来应该还OK.

　　⑧其他的小优化点:

　　1. 不是一个文件， 而是若干个文件， 但是不影响偏移的编号

　　1. 为什么做hash再分块? 避免通用前缀过多，导致分块极不均匀

　　1. 大长的字符串容易导致 字符串块 暴大， 可以考虑分为若干小串， 同时记录原来的位置， 知道是否是一个整串

　　1. 压缩...留一些空间做常用查询串的缓存...

　　⑨再说怎么优化这个预处理的排序过程. 每次读5GB的数据进来， 算好hash分好桶， 这种OK吧， 然后按桶回写到下去， 这里也是批量写的. 处理完继续处理下一个5GB， 全部处理完后， 再做归并， 搞几轮后， OK了嘛. 当然， 为了把内存中排序时浪费的IO补回来， 可以 并行做， 一个在算的时候，另一个在读....”。