optimization - 我应该使用哪种数据结构来存储哈希值？

Question

我有一个哈希表要存储到磁盘。该列表如下所示:

<16-byte key                   > <1-byte result>
a7b4903def8764941bac7485d97e4f76 04
b859de04f2f2ff76496879bda875aecf 03
etc...

有 1-5 百万个条目。目前我只是将它们存储在一个文件中，每个条目 17 字节乘以条目数。该文件有几十兆字节。我的目标是以一种首先优化磁盘空间然后优化查找时间的方式存储它们。插入时间并不重要。

做这个的最好方式是什么？我希望文件尽可能小。多个文件也可以。帕特里夏特里？萝卜吗？

无论我得到什么好的建议，我都会实现和测试。我会把结果贴在这里让大家看看。

Answer 1

您可以按键对条目进行排序并进行二进制搜索。

固定大小的键和数据条目意味着您可以非常快速地从一行跳转到另一行，并且仅存储键和数据意味着您不会在元数据上浪费任何空间。

我不认为你会在磁盘空间上做得更好，而且查找时间是 O(log(n))。插入时间很长，但你说没关系。

如果您真的愿意容忍较长的访问时间，请对表进行排序，然后将其分成一定大小的块并进行压缩。将每个块的偏移*和开始/结束键存储在文件的开头部分中。使用此方案，您可以在线性时间内找到包含您需要的 key 的块，然后在解压后的块内执行二分查找。根据您愿意一次加载到内存中的文件量来选择块大小。

使用现成的压缩方案(如 GZIP)，您可以根据需要调整压缩率；较大的文件可能会具有更快的查找时间。

我怀疑空间节省会不会那么大，因为您的结构似乎主要是散列。如果它们实际上是散列，则它们是随机的并且不会压缩得非常好。排序将有助于提高压缩率，但不是一吨。

*使用header查找一个block的offset来解压使用。