V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
The Go Programming Language
http://golang.org/
Go Playground
Go Projects
Revel Web Framework
yujianwjj
V2EX  ›  Go 编程语言

求一个支持并发读写的数据结构

  •  
  •   yujianwjj · 2021-01-26 19:10:51 +08:00 · 1885 次点击
    这是一个创建于 1157 天前的主题,其中的信息可能已经有所发展或是发生改变。

    场景是,先加载 500 万个 sha256 字符串到内存中,后面会需要大量的对这 500 万个字符串进行查找操作。

    现在的实现方法是用 map,先单线程加载 500 万个字符串到 map 中,但是插入效率低。有没有其他支持并发写,且查询效率高的数据结构。

    写和读是分开的。不存在同时读写的情况。

    16 条回复    2021-01-31 21:53:19 +08:00
    Leigg
        1
    Leigg  
       2021-01-26 19:21:57 +08:00 via iPhone
    你这个题目和内容是相反的呀。
    wunonglin
        2
    wunonglin  
       2021-01-26 19:23:55 +08:00
    goroutine+chan 可以么
    gfreezy
        3
    gfreezy  
       2021-01-26 19:24:14 +08:00
    tries 书
    wingoo
        4
    wingoo  
       2021-01-26 19:25:10 +08:00
    map 可以根据 key 先拆掉, 不要放在一个 map 中
    Maboroshii
        5
    Maboroshii  
       2021-01-26 19:29:34 +08:00
    4L 正解, 对 key 做一个 hash,分成很多份。
    ppyybb
        6
    ppyybb  
       2021-01-26 19:42:12 +08:00 via iPhone
    你这要求需要细化下
    用的啥语言?要多久加载能满足要求?查询延迟要求是多少?有多少线程会去查?是在线 service 还是一次性脚本,还是别的定时 job ?这些都影响设计。

    假如是 java,你直接上 concurrenthashmap 是否可以满足需求?

    或者像前面说的那样,把 key 分段读写。

    复杂点,能不能先并发插入 concurrenthashmap,先应付着查询,然
    后台起个线程再慢慢拷贝到普通 map,弄完了来个原子交换。缺点是内存峰值会大不少
    ppyybb
        7
    ppyybb  
       2021-01-26 19:42:53 +08:00 via iPhone
    @ppyybb 忽略我,原来在 go 节点下面
    securityCoding
        8
    securityCoding  
       2021-01-26 19:48:50 +08:00
    分段吧 ,空间换时间
    asAnotherJack
        9
    asAnotherJack  
       2021-01-26 20:55:44 +08:00
    分段
    xyjincan
        10
    xyjincan  
       2021-01-26 21:46:29 +08:00 via Android
    Redis 可以存吗
    1011
        11
    1011  
       2021-01-26 21:59:25 +08:00
    写效率低,你就去优化写效率

    影响 map 读写效率的的因素:
    1. 哈希的计算
    2. 扩缩容
    3. 处理哈希冲突

    ps.已知条件太少,单从你给的条件看,可做的“优化”多了去了
    renmu123
        12
    renmu123  
       2021-01-26 22:05:16 +08:00 via Android
    哈希插入和查询都是 o1 的,除非有碰撞,那就找个合适的碰撞函数,你已经放内存里了。
    插入慢就多线程。
    Dongxiem
        13
    Dongxiem  
       2021-01-27 13:05:11 +08:00
    这个是静态存储吗?如果是只读不写,建议食用 groupcache 。
    xeaglex
        14
    xeaglex  
       2021-01-27 15:42:14 +08:00
    Trie
    SignLeung
        15
    SignLeung  
       2021-01-27 20:36:36 +08:00
    ConcurrentMap,可以并发插入
    YouLMAO
        16
    YouLMAO  
       2021-01-31 21:53:19 +08:00 via Android
    Trie tree,怎么用 map 呢,占太多内存当然太慢了大哥
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5309 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 09:08 · PVG 17:08 · LAX 02:08 · JFK 05:08
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.