Go:没有哈希表(又名地图)的高效字符串查找？

Question

我在Golang中遇到问题,我需要能够查找大约5,000,000个字符串的字符串键,每个字符串只包含az(小写)和0-9个字符.与uint32和uint64类似的问题作为键.

地图(哈希表)是完美的,但它使用了太多的RAM.

对于这种类型的东西必须有已知的方法,我一直在研究B-Tree,但我不确定它是最有效的机制.

我的问题的一些特殊性,可以导致更有效的解决方案,是:

1. 键只需要是a-z0-9或简单uint值的字符串.
2. 一旦构建,它只需要是只读的.

因为它只需要是只读的,所以在我看来,将它作为带有一系列索引的预排序列表,可能会运行良好.我一开始以为我可能只能在每个级别(即字符)中使用36(26个字母+10个数字)索引进行切片...但当然这意味着36 ^无论哪个最终与...相反高效.然后我想也许我可以为每个级别只放一个36的索引,但最后我需要交叉一组数组/切片来获取结果的ID.

我想我正在寻找某种非常具体的B-Tree实现,但更多地关注我的目的(没有B.)

有谁知道我所建议的任何存在的东西？

Answer 1

我会尝试使用压缩 Trie。它是在具有字典键的场景中完美使用的数据结构。B 树主要用于外部存储器，因为它们最小化了树的深度。特里树或内存效率更高的散列是正确的方法。