存储8M sha256哈希的最节省内存的方法

Question

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

目前，根据我的一些测试，我估计需要大约10Gb的内存来存储8000000个哈希，因为实际存储的数据只有512MB（每个哈希32字节，所以每个记录64字节）

有人有什么建议吗？

更新，基于我认为应该更新的一些评论。我将散列存储为字节，而不是十六进制字符串。我使用sqlite数据库永久存储的数据，但插入许多记录与索引后约1,000,000记录变得太慢，而没有索引检查键的存在也会指数级变慢。这就是为什么我想使用内存结构来进行查找。

更新2

这行吗？atbr哈希表

我的解决方案：（我应该把这个作为答案吗？）最后我从@abarnert那里得到了很多建议，创建了一个新类，实现了1024个[count，bytearray（8000*32），bytearray（8000*32）]

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

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

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

搜索从8000000个散列中随机选取的200000个散列需要30秒，因此比编写要慢40倍，但它应该足够快，可以满足我的需要。

另外，对于所有8000000个哈希，它现在只消耗519MB内存。

谢谢大家的帮助。

Answer 1

匿名用户

我单独写了一个更复杂的答案，因为我不确定这是否适用于您，但是：

dbm是一个键值数据库，其工作原理几乎与dict（其键值和值为字节字符串）完全相同，只是它会备份到磁盘，并根据需要将值分页进出。

它比SQL数据库简单得多，SQL数据库有三大优势。

>

您不需要将代码从hash=hash[thingy]更改为hash=db。执行（'SELECT*FROM hash，其中Thingy=？'，（Thingy，））。fetchone（）[0]，您只需继续使用哈希[thingy]。

没有正确的索引——关键哈希是数据库中一个表的唯一索引——也没有其他优化要做。

数据库中的一大块数据将被缓存在内存中，从而使其速度更快。

尽管被称为Unix数据库，但每个平台都存在各种dbm模块系列中的至少一个。有关详细信息，请参阅dbm：不仅仅是Unix。

Answer 2

如果您不想或不能使用外部数据库，可以创建一个内存中数据库，该数据库非常接近信息理论上的最小内存使用量，同时速度非常快。不过，您需要使用比Python对象更低级别的工具。

您可以使用数组。数组或bytearray以存储键和值，而无需任何开销，这意味着488 MiB中可以容纳800个条目。然后你可以在上面写一个哈希表。但这相当不方便，因此您可能希望使用像cffi这样的外部库来处理紧凑的C结构和数组。

一个简单的带线性探测的开放寻址哈希表可以很好地用于您的数据（将密钥的最低N位作为哈希），并且不太难实现，如果不需要删除，甚至更容易实现。只要保持合理的负载系数，在一半到三分之二之间。如果要节省空间（每个空条目浪费半KB），请将键值对紧密打包到数组中，并且只在哈希表中存储指针/索引。

Answer 3

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

每个都有32个字节。这意味着以二进制形式存储大约需要32个字节，例如字节或字节数组对象的存储。到目前为止，一切顺利。

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

那么，您如何摆脱150%的额外存储空间呢？将字节打包成一个巨大的数组，如字节或字节数组。然后总共有48个字节加上每个哈希32，而不是每个哈希48 32。当您需要访问散列时，如果您已经获得了索引，那么它只是切片[index*32：（index 1）*32]。

此外，根据您创建bytes的方式，可能存在一些溢出漏洞。您可以检查-ifsys.getsizeof（s）-sys.getsizeof（b"）

不管怎样，现在你有了8百万个额外的索引。如果这些是暂时的，那没关系，但是如果您将它们作为ints存储在dict值槽中，那么它们中的每一个都有一个头。通过快速测试，在实际存储的4字节之上（对于小于1的整数）

您可以使用某种形式的打包存储，如阵列模块。数组类型I每个整数仅使用4个字节。但是你需要索引到数组中，这和你刚才解决的问题是一样的。

但是你甚至不需要索引——如果你把键本身存储在一个数组中，任何键的索引都已经是字节串中哈希的索引（除以32），对吗？

只有当您可以将密钥存储在某种紧凑的数组中时，这才有效。如果它们的大小都差不多，你可以再次使用同样的“giantbytestring”技巧。在你的例子中，它们是键，也是32字节的散列。因此，您只需按键值对两个大字节字符串进行排序（请参阅bisect模块，这样您就不必自己编写代码）。

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

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