我需要在内存中以二进制形式存储大约200,000个SHA256哈希值 .
我的要求是,

数据结构应该是大多数内存效率 . 我将按排序顺序读回哈希(插入顺序并不重要),因此,支持词典阅读的数据结构更好 . 如果可以比较两个相同类型的结构以找到它们中的共同哈希,那将是一个加号(尽管不是强制性的) .

以下是我考虑的数据结构,

数组:

数组似乎是最简单和内存有效的数组,但我不能使用数组,因为,

  • 我必须在阅读时对数据进行排序 . 数据结构本身不支持它 .

  • 由于200K哈希不是一个硬限制,也可以超过这个,我不会知道预先分配数组长度的大小 . 这意味着我有时可能需要通过将数组的全部内容复制到一个新数组(同时在内存中同时包含新旧数据)来调整数组大小 .

Compressed Radix Trie(Patricia Trie?)

Compressed Radix Trie似乎是我实施的最有希望的DS . 但是一个快速的谷歌搜索显示了这个链接:https://news.ycombinator.com/item?id=101987表示Radix Tries不是非常优化内存,

引用链接:

基数尝试很好 . 在......时使用它们(4)你不关心内存使用情况那么多 . 我将一个简单的8位基数树与一些标准的哈希表实现进行了比较 - 前者占用了大约十倍的内存 . 然后我将我的基数改为基于4位(每个char只分成2部分)并且内存使用率提高了两倍 . 现在我想知道基数是否有更大的改进空间 .

哈希表?

我知道散列表不像Radix尝试那样支持排序读取,但是它们真的是内存最优(比基数树好10倍)吗?


我还是不明白/不相信,压缩基数Trie不是内存最优数据结构?如果没有,哪种数据结构最适合我的需求?

如果Radix trie是已知的最佳算法,那么是否有一个最佳算法可以比较2个Radix尝试以找到它们中的常见哈希值 .


P.S:我在SO上发现了以下类似的问题,但它们没有解决我的问题:

Storing 1 million phone numbers:这并没有像_1585785那样关闭太多的信息,答案是关于找到电话号码的增量 . 但哈希的三角洲没有帮助?

Most memory efficient way to store 8M+ sha256 hashes:这是关于存储键值映射,答案是要求使用数据库 .