V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
perryzou
V2EX  ›  Java

大佬们,问个 Java 面试题

  •  
  •   perryzou · 2020-06-28 18:23:15 +08:00 · 5945 次点击
    这是一个创建于 1607 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    手机号,name


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

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

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

    42 条回复    2020-06-30 11:31:58 +08:00
    weijiawj
        1
    weijiawj  
       2020-06-28 18:28:08 +08:00
    字典树行不
    sagaxu
        2
    sagaxu  
       2020-06-28 18:32:35 +08:00 via Android
    3M 连 JVM 都启动不了
    wysnylc
        3
    wysnylc  
       2020-06-28 18:34:15 +08:00
    ConcurrentSkipListMap,能存进去就可以
    不过你这 3M 启动应该会挂,什么脑残面试题
    perryzou
        4
    perryzou  
    OP
       2020-06-28 18:36:42 +08:00
    @wysnylc 哈哈哈 我也觉得 这个内存要求我就很纳闷
    misaka19000
        5
    misaka19000  
       2020-06-28 18:38:09 +08:00
    B 树
    misaka19000
        6
    misaka19000  
       2020-06-28 18:38:55 +08:00
    数据完整的保存在磁盘上使用 B 树,内存中使用红黑树
    perryzou
        7
    perryzou  
    OP
       2020-06-28 18:42:19 +08:00
    @misaka19000 文件已经固定了,内容格式已经定了,只让实现 java 类,
    aguesuka
        8
    aguesuka  
       2020-06-28 18:50:58 +08:00
    1m 约等于 10^30 => log(2, 1m) 约等于 30 。文件在磁盘里排序对齐,一直打开文件不要关闭,相当于每秒位移 数千*30 次。如果没有写入文件,用 tree 不能减少搜索的复杂度,反而会增加常量时间
    smilenceX
        9
    smilenceX  
       2020-06-28 18:55:20 +08:00
    假设手机号 11 位,不含国家代码,在内存中以 int32 ( 4 字节)存储,中文 name 按三个汉字 ,为了简单每个汉字按照占 3 字节(一共 9 字节)来算,
    ( 4+9 )*100w/1024/1024=12.39m
    因此不可能把数据全部读到内存里再查找(超过了题目 3M 的要求)。
    fancy20
        10
    fancy20  
       2020-06-28 18:57:55 +08:00
    3MB 内存,文件全读到内存不够吧,所以看怎么个并发了,允许 async callback 查询结果的话,那就在内存里存要查询的手机号,另一个线程不停反复从头到尾扫文件,如果扫到就返回
    perryzou
        11
    perryzou  
    OP
       2020-06-28 19:00:22 +08:00
    @smilenceX 是的,就是这个意思
    chendy
        12
    chendy  
       2020-06-28 19:17:56 +08:00
    本来想说整个 map<手机号,文件偏移量>,然后发现光是 100 万个手机号就超过 3m 了
    文件按手机号排个序,每行长度固定,然后二分查找?建议配合 ssd 食用…
    icexin
        13
    icexin  
       2020-06-28 19:56:54 +08:00
    按照 "手机号->记录偏移量" 作为 kv 结构排序成一个一个单独的索引文件,每个索引文件不要太大,可以在内存里面记录下每个索引文件的 range,也可以持久化成一个 manifest 文件,方便启动的时候读取。查询的时候先根据 manifest 获取索引文件,加载到内存,根据手机号找到记录偏移,再根据偏移找到 name,最后加一个手机号->name 的 lru cache 来做 cache 。
    guolaopi
        14
    guolaopi  
       2020-06-28 20:17:23 +08:00
    我不是很理解“并发要求至少每秒数千次”是什么意思。。。
    是要求响应时间在 XX 以内吗
    CrazyEight
        15
    CrazyEight  
       2020-06-28 21:09:31 +08:00
    建个索引(手机号,name ),不过内存小于 3M 有点难以把握。不知道你说的内存是只指程序处理请求时占用的内存吗,如果索引占用的内存也算进去,那很难也没必要
    ljzxloaf
        16
    ljzxloaf  
       2020-06-28 21:11:25 +08:00
    这个文件就是一张表 t,有俩字段 tel 和 name,要求就是尽量提高 select name from t where tel = ?的性能,这就是要问关系型数据库的相关实现吧。
    但是数据库一般这种情况要建个索引吧,否则性能应该达不到要求,注意这里不需要建 B 树索引,因为并不需要范围查询,可以分成 100 个小索引文件,每个小索引是一棵树,每次查找先取模找到索引文件,将之整个加载到内存,再查找 name 。
    可以去搜搜关系数据库的哈希索引实现,这里肯定会有很多细节。
    为了防止大量不存在的手机号导致性能问题,还可以搞个布隆过滤器什么的。
    huntcool001
        17
    huntcool001  
       2020-06-28 21:30:04 +08:00
    "并发要求至少每秒数千次"

    我开 10 个线程一直查一个 key,那也是并发几十万次...
    zhgg0
        18
    zhgg0  
       2020-06-28 21:40:10 +08:00
    前缀树 存手机号
    binbinyouliiii
        19
    binbinyouliiii  
       2020-06-28 21:42:46 +08:00
    name 做索引,索引也不是说非得在内存里,索引排序到文件里,比如 hash 做索引,索引的头 5 位放到内存里,记下每个索引文件的指针位置,不过机械硬盘性能够呛。
    而且又没说查询最小间隔,只要求了吞吐量,剩下的就把一部分数据放到内存里,LRU 算法拿。
    perryzou
        20
    perryzou  
    OP
       2020-06-28 21:58:15 +08:00
    @binbinyouliiii 实验索引的内存就超过了 3M,不然并发达不到要求
    gejun123456
        21
    gejun123456  
       2020-06-28 22:02:27 +08:00
    用 sqlite
    ujued
        22
    ujued  
       2020-06-28 22:31:40 +08:00 via iPhone
    @perryzou RandomAccess 访问文件数据很快的老弟!你只需要知道你要访问的数据大致在哪个地方就行。这点数据量,这点并发,一般硬件足矣。
    johnniang
        23
    johnniang  
       2020-06-28 22:56:11 +08:00 via Android
    先外部排序,然后二分法查找。毕竟手机号是有序的。
    liprais
        24
    liprais  
       2020-06-28 23:26:21 +08:00 via iPhone
    手机号前七位都是有很多重复的,压缩压缩没准 3m 内存能都放下
    helloworld000
        25
    helloworld000  
       2020-06-28 23:54:58 +08:00
    tire tree 啊,省不少内存。

    每个数字作为节点 node,最后树的叶子节点记录个名字就行了
    exch4nge
        26
    exch4nge  
       2020-06-29 01:22:59 +08:00 via iPhone
    提个不新建文件,用原文件格式的方法,核心就是哈希表
    把 3M 分成每个桶大小为 3 字节的,1024*1024 个桶;每个桶里用 3 字节保存此电话号码开头在文件中的偏移位置,不过直接存偏移三个字节肯定不够,可以除一个系数存,三个字节够表示 100w+的位置
    哈希碰撞问题,首先是选用好的哈希函数,不过 95.37%的密度碰撞出现可能性还是蛮高,具体策略可以再评估各种后再决定,可参考 folly F14 的解决方式,约 12/13=92%来着?
    xupefei
        27
    xupefei  
       2020-06-29 02:42:59 +08:00 via iPhone
    简单,用若干前缀树,每棵树尺寸限制到 3MB 。如果一个节点的后代是另一棵树,那么在此节点记录下一个编号 a 。包含跟节点的树定为编号 0 。

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

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

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

    另外还有一些可以聊的方向:树是横着切还是竖着切?在文件里怎么序列化? LRU 缓存?这方案和数据库的 page 有什么区别?
    yousabuk
        28
    yousabuk  
       2020-06-29 07:24:18 +08:00 via iPhone
    将文件转换为二进制文件存储,在创建索引文件(肯定小于 3M ),将索引文件全部加载到内存,根据 TDMS 格式规范使用 JAVA 进行解析。

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

    TDMS 是 NI 专门用于快速存储和读取大数据量波形文件的方案,速度绝对足够快,索引文件也绝对够小。
    yousabuk
        29
    yousabuk  
       2020-06-29 07:49:58 +08:00 via iPhone
    对了,TDMS 会自动创建索引文件。
    ebony0319
        30
    ebony0319  
       2020-06-29 08:27:15 +08:00 via Android   ❤️ 1
    如果真的是面试题,那解法大概是这样的:一行行读取文件,对每一行文件 hash(value)%1000,这样就把对应的文件分散到对应的小文件中。每次查询的时候先对手机号码 hash(手机号)%1000 求出区间,然后将小文件加载到内存查询。
    776491381
        31
    776491381  
       2020-06-29 08:54:51 +08:00 via iPhone
    可以使用稀疏索引+顺序读,手机号作为索引文件,对应文件的相应位置指针
    mizzle
        32
    mizzle  
       2020-06-29 09:39:33 +08:00
    文件按手机号排序,取手机号前 7 位(万号段)第一次出现的偏移量,放入数组。
    行数小于 1000w ( 2^20),一行字节数小于 4k(2^12),4 字节可以存一个偏移量;手机号前两位固定为 13/17/18,所以前 7 位 30 万排列组合,使用 1.2M 内存。
    查询时先取该万号段和下一万号段偏移量,然后在文件中二分查找。

    还可以优化:
    1 、将 name 用空格补齐到固定长度,可以直接用行数乘以每行长度得到偏移量,这样 3 字节就可以存一个行数,更省内存。(虽然不知道抠这点内存有啥意思)
    2 、既然对响应时间没有要求,剩下内存可以对请求做一个队列,按请求的手机号做排序然后批处理查询,保证每次批处理时文件扫描从头到尾或从尾到头,增加随机访问效率。
    walnsrully
        33
    walnsrully  
       2020-06-29 10:22:43 +08:00 via Android
    @ljzxloaf 不是说禁止使用数据库吗
    BlackwithBrown
        34
    BlackwithBrown  
       2020-06-29 11:55:29 +08:00
    用树的内存应该不够,如果叶存偏移量还不如直接就把原文件先进行分段存好了,代码判断一下还方便
    alittlehj
        35
    alittlehj  
       2020-06-29 12:23:35 +08:00
    我等菜鸟会直接说不会 你解答给我看看 涨涨见识
    ljzxloaf
        36
    ljzxloaf  
       2020-06-29 13:13:00 +08:00 via Android
    @walnsrully
    不是使用数据库,是实现数据库
    zliea
        37
    zliea  
       2020-06-29 13:28:04 +08:00
    让我想起了,ipip 的 ip 数据库。
    hugedata
        38
    hugedata  
       2020-06-29 16:46:41 +08:00
    @ztechstack 老哥跟我想一块儿去了。。。。
    lianglianglee
        39
    lianglianglee  
       2020-06-29 16:57:37 +08:00 via Android
    文件按照手机号的 hash 分割成 200 个文件,如果是 ssd 就文件就再多点(1000),用 RandomAccess 访问小文件遍历,速度还是非常快的
    lhy0dyx
        40
    lhy0dyx  
       2020-06-29 19:09:12 +08:00
    一棵 11 层的十叉树行吗
    Jooooooooo
        41
    Jooooooooo  
       2020-06-29 19:11:50 +08:00
    题目本身不错, 不过有些东西没有描述清楚
    palmers
        42
    palmers  
       2020-06-30 11:31:58 +08:00
    根据题目我更偏向于 通过类似 hash 的机制将大文件拆分为若干小文件, 小文件的大小限制需要根据 3M 来做处理 针对于第一条 这个并发不是问题
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1512 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 17:10 · PVG 01:10 · LAX 09:10 · JFK 12:10
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.