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

探讨大量数据下某个值是否存在的问题,大佬们指教一下

  •  
  •   xrzxrzxrz · 2021-12-16 23:59:57 +08:00 · 1821 次点击
    这是一个创建于 1073 天前的主题,其中的信息可能已经有所发展或是发生改变。

    我们现在有这么个需求,允许运营上传一批用户 ID (可能会有很多个,最大值可以到千万级),然后服务端需要在请求的时候确定这次 id 是否在一批用户 ID 中。其实就是面试很常见的,怎么在一堆值中确定某个值是否存在。

    我们这边目前的打算是通过 redis + bloom filter 的形式去判定该 ID 是否命中(跟产品讨论过,允许一定的误差),但是个人感觉这个方案思路有点常规,或者说有点简单。不知道大佬们是否有其他的思路。指教下一些其他的路子~

    13 条回复    2021-12-18 02:20:47 +08:00
    fishCatcher
        1
    fishCatcher  
       2021-12-17 00:03:10 +08:00 via iPhone
    最大千万级,直接放内存哈希表就行了
    foam
        2
    foam  
       2021-12-17 00:09:34 +08:00
    布隆过滤器+1.
    蹲一波别的想法
    ximenmenglong
        3
    ximenmenglong  
       2021-12-17 00:13:52 +08:00
    https://nullprogram.com/blog/2014/09/18/
    这个实例挺符合你的需求
    raycool
        4
    raycool  
       2021-12-17 00:21:18 +08:00
    这样应该能满足要求吧。
    这个思路很常规吗。
    monkeyWie
        5
    monkeyWie  
       2021-12-17 10:04:29 +08:00
    id 是整数型的直接用 bitmap 就行吧
    xrzxrzxrz
        6
    xrzxrzxrz  
    OP
       2021-12-17 10:06:20 +08:00
    @fishCatcher 主要是考虑内存成本问题,因为理论上允许用户上传很多批用户 ID ,这样会用到太多内存
    xrzxrzxrz
        7
    xrzxrzxrz  
    OP
       2021-12-17 10:07:03 +08:00
    @monkeyWie 额 不是纯数字。。会有 md5 值
    xrzxrzxrz
        8
    xrzxrzxrz  
    OP
       2021-12-17 10:07:42 +08:00
    @ximenmenglong 我看看哈
    xrzxrzxrz
        9
    xrzxrzxrz  
    OP
       2021-12-17 10:09:44 +08:00
    @raycool 应该是能满足的 因为当时看到这个需求的时候,第一时间想到的就是这个方案,所以觉得太常规,想看看有没有其他的思路,可能是我认识不够
    t4we
        10
    t4we  
       2021-12-17 10:14:59 +08:00
    hyperloglog
    dqzcwxb
        11
    dqzcwxb  
       2021-12-17 11:05:03 +08:00
    试试布谷鸟过滤 Cuckoo Filter
    git00ll
        12
    git00ll  
       2021-12-17 18:25:12 +08:00
    见张表,加个索引。一亿数据都没关系
    Rocketer
        13
    Rocketer  
       2021-12-18 02:20:47 +08:00
    现在都是拿空间换时间,这种需求只要不是大到离谱的数据量都可以放内存里用 HashSet 实现。内存才多少钱,O(1)的复杂度不香吗?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1545 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 17:16 · PVG 01:16 · LAX 09:16 · JFK 12:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.