大佬们,问个 Java 面试题

[perryzou]

有一个百万级数据文件,格式如下:

手机号,name

---

用 JAVA 实现功能,通过手机号查找 name,要求:

1.并发要求至少每秒数千次,不能使用 redis,mysql,es 等

2.内存要求,不能超过 3M

[gejun123456]

用 sqlite

[ujued]

@perryzou RandomAccess 访问文件数据很快的老弟！你只需要知道你要访问的数据大致在哪个地方就行。这点数据量，这点并发，一般硬件足矣。

[johnniang]

先外部排序，然后二分法查找。毕竟手机号是有序的。

[liprais]

手机号前七位都是有很多重复的,压缩压缩没准 3m 内存能都放下

[helloworld000]

tire tree 啊，省不少内存。

每个数字作为节点 node，最后树的叶子节点记录个名字就行了

[exch4nge]

提个不新建文件，用原文件格式的方法，核心就是哈希表
把 3M 分成每个桶大小为 3 字节的，1024*1024 个桶；每个桶里用 3 字节保存此电话号码开头在文件中的偏移位置，不过直接存偏移三个字节肯定不够，可以除一个系数存，三个字节够表示 100w+的位置
哈希碰撞问题，首先是选用好的哈希函数，不过 95.37%的密度碰撞出现可能性还是蛮高，具体策略可以再评估各种后再决定，可参考 folly F14 的解决方式，约 12/13=92%来着？

[xupefei]

简单，用若干前缀树，每棵树尺寸限制到 3MB 。如果一个节点的后代是另一棵树，那么在此节点记录下一个编号 a 。包含跟节点的树定为编号 0 。

查询的时候，首先把 0 号树读进来，然后跟着去找下一个编号的树。直到最后找到对应人名。

存储方面：编号为 n 的树存储在 3MB*n 偏移处。

如果有 ssd 的话，上面这方案每秒千次查询根本不是问题。

另外还有一些可以聊的方向：树是横着切还是竖着切？在文件里怎么序列化？ LRU 缓存？这方案和数据库的 page 有什么区别？

[yousabuk]

将文件转换为二进制文件存储，在创建索引文件（肯定小于 3M ），将索引文件全部加载到内存，根据 TDMS 格式规范使用 JAVA 进行解析。

现成的二进制文件结构：TDMS

TDMS 是 NI 专门用于快速存储和读取大数据量波形文件的方案，速度绝对足够快，索引文件也绝对够小。

[yousabuk]

对了，TDMS 会自动创建索引文件。

[ebony0319]

如果真的是面试题，那解法大概是这样的：一行行读取文件，对每一行文件 hash(value)%1000，这样就把对应的文件分散到对应的小文件中。每次查询的时候先对手机号码 hash(手机号)%1000 求出区间，然后将小文件加载到内存查询。

[776491381]

可以使用稀疏索引+顺序读，手机号作为索引文件，对应文件的相应位置指针

[mizzle]

文件按手机号排序，取手机号前 7 位(万号段)第一次出现的偏移量，放入数组。
行数小于 1000w （ 2^20),一行字节数小于 4k(2^12)，4 字节可以存一个偏移量；手机号前两位固定为 13/17/18，所以前 7 位 30 万排列组合，使用 1.2M 内存。
查询时先取该万号段和下一万号段偏移量，然后在文件中二分查找。

还可以优化：
1 、将 name 用空格补齐到固定长度，可以直接用行数乘以每行长度得到偏移量，这样 3 字节就可以存一个行数，更省内存。(虽然不知道抠这点内存有啥意思)
2 、既然对响应时间没有要求，剩下内存可以对请求做一个队列，按请求的手机号做排序然后批处理查询，保证每次批处理时文件扫描从头到尾或从尾到头，增加随机访问效率。

[walnsrully]

@ljzxloaf 不是说禁止使用数据库吗

[BlackwithBrown]

用树的内存应该不够，如果叶存偏移量还不如直接就把原文件先进行分段存好了，代码判断一下还方便

[alittlehj]

我等菜鸟会直接说不会 你解答给我看看 涨涨见识

[ljzxloaf]

@walnsrully
不是使用数据库，是实现数据库

[zliea]

让我想起了，ipip 的 ip 数据库。

[hugedata]

@ztechstack 老哥跟我想一块儿去了。。。。

[lianglianglee]

文件按照手机号的 hash 分割成 200 个文件，如果是 ssd 就文件就再多点(1000)，用 RandomAccess 访问小文件遍历，速度还是非常快的

[lhy0dyx]

一棵 11 层的十叉树行吗