10亿的md5值,现在来一新的32位的字符串,如何判断该值是否已经存在10亿里,越快越好

如题: 已经存在10亿的md5值,现在来一新的32位的字符串,如何判断该值是否已经存在10亿里,越快越好

已邀请:

zensh - https://github.com/zensh

赞同来自: kakashi tupunco andylau004 Xargin mnhkahn

使用 Radix tree: github.com/armon/go-radix https://en.wikipedia.org/wiki/Radix_tree

duanquanyong

赞同来自: tupunco kylefeng

可以搜下布隆过滤 不过下面这个貌似更好 https://github.com/irfansharif/cfilter

tupunco

赞同来自: kakashi

经典 trie tree 并不是一个很好的方法, 虽然比较省内存, 但是查找复杂度太高. 1 楼 所说的方法效率不错, 内存消耗看起来也不是太大.

但是这么多数据用内存保存感觉有点 浪费, 现在 云服务器 内存 这么贵, 那只有放入 文件 中. 可以搞个 嵌入式数据库, 比如 BoltDB 啥的. 这样你即解决了 内存占用 问题, 也解决了开发的 复杂度 问题.

songtianyi

赞同来自:

字典树应该是最佳方法了吧,节省内存的话要看你的md5值有没有规律,10亿的数据多少会有冗余。 可以考虑先编下码,比如ABC 用 00表示 ACB用01表示,将字符组成字符串并编码 用更少的比特位表示, 我初步想了下,耗时会增加。

zensh - https://github.com/zensh

赞同来自:

楼主之前做个的 map和trie tree方案 benchmark 对比结果如何?字典树无论是计算还是内存消耗应该都是最低的

quetzal

赞同来自:

楼主又没说资源不够,就用空间换效率,挺好的啊。内存现在这么便宜

lifei6671 - PHPer

赞同来自:

应该是BitMap算法吧。

lys86_1205

赞同来自:

用hashmap查找比较快。

go 语言中map类型就是 用hashmap思想实现的

要回复问题请先登录注册