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` 啥的. 这样你即解决了 `内存占用` 问题, 也解决了开发的 `复杂度` 问题.
字典树应该是最佳方法了吧,节省内存的话要看你的md5值有没有规律,10亿的数据多少会有冗余。
可以考虑先编下码,比如ABC 用 00表示 ACB用01表示,将字符组成字符串并编码 用更少的比特位表示, 我初步想了下,耗时会增加。

zensh - https://github.com/zensh

楼主之前做个的 map和trie tree方案 benchmark 对比结果如何?字典树无论是计算还是内存消耗应该都是最低的
楼主又没说资源不够,就用空间换效率,挺好的啊。内存现在这么便宜

lifei6671 - PHPer

应该是BitMap算法吧。
用hashmap查找比较快。

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

要回复问题请先登录注册