python - 存储 8M+ sha256 哈希的最有效内存方式

Question

我一直在使用 dict 来存储键值对，其中键和值都是 sha256 哈希摘要。我需要能够查明列表中是否存在键，并且还能够检索该字典的值。

根据我的一些测试，目前我估计我需要大约 10Gb 的内存来存储 8,000,000 个哈希值，而实际存储的数据只有大约 512MB(每个哈希值 32 字节，所以每条记录 64 字节)

有人有什么建议吗？

更新，根据我认为应该更新的一些评论。我将哈希存储为字节，而不是十六进制字符串。我正在使用一个 sqlite 数据库来永久存储数据，但是在大约 1,000,000 条记录之后插入那么多带有索引的记录变得太慢，并且如果没有索引检查键的存在也会以指数方式变慢。这就是为什么我想使用内存结构来进行查找。

更新 2

这行得通吗？ atbr hashtable

我的解决方案:(我应该把这个作为答案吗？)我最终做的是听取了@abarnert 的很多建议，创建了一个新类，该类实现了 1024 个 [count, bytearray(8000 * 32), bytearray(8000 *32)]

列表

我使用散列的前 10 位作为我应该将散列存储到的列表的索引。然后我只需将键附加到下一个 32 字节槽，并将值附加到另一个字节数组中的相同槽。

我可以生成 16,000,000 个散列(一个用于键，一个用于值)并在大约 30 秒内将 8,000,000 个键值对插入到结构中。

搜索正好相反，我使用前 10 位来查找列表，然后我只对哈希进行线性搜索，直到找到为止。

从 8,000,000 个中随机选择 200,000 个哈希值搜索需要 30 秒，因此比写入慢 40 倍，但它应该足够快以满足我的需求。

最重要的是，它现在只为所有 8,000,000 个哈希消耗 519MB RAM。

谢谢大家的帮助。

Answer 1

首先，让我们看看为什么它这么大。

每个都有 32 个字节。这意味着以二进制形式存储大约需要 32 个字节，例如 bytes 或 bytearray 对象的存储。到目前为止，还不错。

但是所有 Python 对象都有 header ，通常为 24-64 字节。通过快速检查，看起来 bytes 对象在 32 位(可能加上对齐填充)上占用额外的 36 个字节，在 64 位上占用 48 个字节，至少在我检查的两个 CPython 版本上是这样。

那么，您如何摆脱这 150% 的额外存储空间呢？将字节打包成一个巨大的数组，如 bytes 或 bytearray。然后你有 48 个字节 total 加上每个散列 32 个，而不是每个散列 48+32 个。当您需要访问哈希时，如果您有索引，它只是切片 [index*32:(index+1)*32]。

此外，根据您创建 bytes 的方式，可能会有一些溢出溢出。您可以检查——如果 sys.getsizeof(s) - sys.getsizeof(b'') > len(s)，您需要对所有对象进行切片以创建没有额外填充的新副本.

无论如何，现在你有 8M 的额外索引。如果它们是 transient 的，那很好，但是如果您将 它们 作为 int 存储在 dict 值槽中，那么它们中的每一个也是有一个标题。通过快速测试，在实际存储的 4 个字节之上(对于 1<<31 以下的整数)，32 位和 64 位都有一个 24 字节的 header (尽管非常小的整数显然可以塞进 header )。所以，所有这一切只是将 48 字节的浪费减少到 28 字节，这不是很好。

您可以使用某种形式的打包存储，例如 array模块。数组类型 I 每个整数仅使用 4 个字节。但是随后您需要对数组进行索引，这……与您刚刚解决的问题相同。

但您实际上什至不需要索引——如果您将键本身存储在一个数组中，那么任何键的索引已经是字节字符串中散列的索引(除以 32)，对吧？

这仅在您可以将键存储在某种紧凑数组中时才有效。如果它们的大小都差不多，您可以再次使用相同的“giantbytestring”技巧来做到这一点。在您的情况下，它们是 — 键也是 32 字节散列。因此，您只需保留两个按键值排序的巨字节字符串(请参阅 bisect 模块，这样您就不必自己编写该代码)。

当然，使用二进制搜索算法而不是散列算法意味着您要使查找和插入成为对数而不是常量。而且，虽然 log(8M) 只有 16 左右，比 8M 好很多，但它仍然是 1 的 16 倍。但这实际上是你从一个理想调整的关系数据库中得到的，除了你不需要进行任何调整，并且都在内存中，没有额外的开销，因此它必须是对您迄今为止尝试过的方法的改进。

您当然可以在 Python 中构建自定义哈希表，使用两个巨大的字节数组作为存储空间，并使用两个 array('I') 作为索引。但这需要做更多的工作，所以我会先尝试简单的方法。