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

2021 年 1 月 26 日
 yujianwjj

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

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

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

2677 次点击
所在节点    Go 编程语言
16 条回复
Leigg
2021 年 1 月 26 日
你这个题目和内容是相反的呀。
shakaraka
2021 年 1 月 26 日
goroutine+chan 可以么
gfreezy
2021 年 1 月 26 日
tries 书
wingoo
2021 年 1 月 26 日
map 可以根据 key 先拆掉, 不要放在一个 map 中
Maboroshii
2021 年 1 月 26 日
4L 正解, 对 key 做一个 hash,分成很多份。
ppyybb
2021 年 1 月 26 日
你这要求需要细化下
用的啥语言?要多久加载能满足要求?查询延迟要求是多少?有多少线程会去查?是在线 service 还是一次性脚本,还是别的定时 job ?这些都影响设计。

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

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

复杂点,能不能先并发插入 concurrenthashmap,先应付着查询,然
后台起个线程再慢慢拷贝到普通 map,弄完了来个原子交换。缺点是内存峰值会大不少
ppyybb
2021 年 1 月 26 日
@ppyybb 忽略我,原来在 go 节点下面
securityCoding
2021 年 1 月 26 日
分段吧 ,空间换时间
asAnotherJack
2021 年 1 月 26 日
分段
xyjincan
2021 年 1 月 26 日
Redis 可以存吗
1011
2021 年 1 月 26 日
写效率低,你就去优化写效率

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

ps.已知条件太少,单从你给的条件看,可做的“优化”多了去了
renmu123
2021 年 1 月 26 日
哈希插入和查询都是 o1 的,除非有碰撞,那就找个合适的碰撞函数,你已经放内存里了。
插入慢就多线程。
Dongxiem
2021 年 1 月 27 日
这个是静态存储吗?如果是只读不写,建议食用 groupcache 。
xeaglex
2021 年 1 月 27 日
Trie
SignLeung
2021 年 1 月 27 日
ConcurrentMap,可以并发插入
YouLMAO
2021 年 1 月 31 日
Trie tree,怎么用 map 呢,占太多内存当然太慢了大哥

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://study.congcong.us/t/748655

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX