大佬们,问个 Java 面试题

[perryzou]

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

手机号,name

---

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

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

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

[weijiawj]

字典树行不

[sagaxu]

3M 连 JVM 都启动不了

[wysnylc]

ConcurrentSkipListMap,能存进去就可以
不过你这 3M 启动应该会挂,什么脑残面试题

[perryzou]

@wysnylc 哈哈哈 我也觉得 这个内存要求我就很纳闷

[misaka19000]

B 树

[misaka19000]

数据完整的保存在磁盘上使用 B 树，内存中使用红黑树

[perryzou]

@misaka19000 文件已经固定了,内容格式已经定了,只让实现 java 类,

[aguesuka]

1m 约等于 10^30 => log(2, 1m) 约等于 30 。文件在磁盘里排序对齐，一直打开文件不要关闭，相当于每秒位移 数千*30 次。如果没有写入文件，用 tree 不能减少搜索的复杂度，反而会增加常量时间

[smilenceX]

假设手机号 11 位，不含国家代码，在内存中以 int32 （ 4 字节）存储，中文 name 按三个汉字 ，为了简单每个汉字按照占 3 字节（一共 9 字节）来算，
（ 4+9 ）*100w/1024/1024=12.39m
因此不可能把数据全部读到内存里再查找（超过了题目 3M 的要求）。

[fancy20]

3MB 内存，文件全读到内存不够吧，所以看怎么个并发了，允许 async callback 查询结果的话，那就在内存里存要查询的手机号，另一个线程不停反复从头到尾扫文件，如果扫到就返回

[perryzou]

@smilenceX 是的,就是这个意思

[chendy]

本来想说整个 map<手机号，文件偏移量>，然后发现光是 100 万个手机号就超过 3m 了
文件按手机号排个序，每行长度固定，然后二分查找？建议配合 ssd 食用…

[icexin]

按照 "手机号->记录偏移量" 作为 kv 结构排序成一个一个单独的索引文件，每个索引文件不要太大，可以在内存里面记录下每个索引文件的 range，也可以持久化成一个 manifest 文件，方便启动的时候读取。查询的时候先根据 manifest 获取索引文件，加载到内存，根据手机号找到记录偏移，再根据偏移找到 name，最后加一个手机号->name 的 lru cache 来做 cache 。

[guolaopi]

我不是很理解“并发要求至少每秒数千次”是什么意思。。。
是要求响应时间在 XX 以内吗

[CrazyEight]

建个索引（手机号，name ），不过内存小于 3M 有点难以把握。不知道你说的内存是只指程序处理请求时占用的内存吗，如果索引占用的内存也算进去，那很难也没必要

[ljzxloaf]

这个文件就是一张表 t，有俩字段 tel 和 name，要求就是尽量提高 select name from t where tel = ？的性能，这就是要问关系型数据库的相关实现吧。
但是数据库一般这种情况要建个索引吧，否则性能应该达不到要求，注意这里不需要建 B 树索引，因为并不需要范围查询，可以分成 100 个小索引文件，每个小索引是一棵树，每次查找先取模找到索引文件，将之整个加载到内存，再查找 name 。
可以去搜搜关系数据库的哈希索引实现，这里肯定会有很多细节。
为了防止大量不存在的手机号导致性能问题，还可以搞个布隆过滤器什么的。

[huntcool001]

"并发要求至少每秒数千次"

我开 10 个线程一直查一个 key,那也是并发几十万次...

[zhgg0]

前缀树 存手机号

[binbinyouliiii]

name 做索引，索引也不是说非得在内存里，索引排序到文件里，比如 hash 做索引，索引的头 5 位放到内存里，记下每个索引文件的指针位置，不过机械硬盘性能够呛。
而且又没说查询最小间隔，只要求了吞吐量，剩下的就把一部分数据放到内存里，LRU 算法拿。

[perryzou]

@binbinyouliiii 实验索引的内存就超过了 3M,不然并发达不到要求