存储8M+sha256哈希的最有效内存方法

Question

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

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

有人有什么建议吗？在

更新，基于我认为我应该更新的一些评论。我将散列存储为字节，而不是十六进制字符串。我使用sqlite数据库来永久存储数据，但是在大约1000000条记录之后，插入带有索引的许多记录的速度太慢了，如果不进行索引检查，键的存在速度也会成倍地慢下来。这就是为什么我要使用内存结构来进行查找。在

更新2

这行吗？atbr hashtable

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

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

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

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

搜索从8000000中随机抽取的200000个哈希值需要30秒，因此比写作慢40倍，但它应该足够快，以满足我的需要。在

更重要的是，它现在只消耗519MB的RAM来处理8000000哈希。在

谢谢大家的帮助。在

Answer 1

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

您可以使用array.array或bytearray来存储键和值，而无需任何开销，这意味着488mib中可以容纳8M个条目。然后你可以在上面写一个哈希表。但是这很不方便，所以您可能需要使用一个外部库，比如cffi来处理紧凑的C结构和数组。在

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

Answer 2

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

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

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

那么，你怎样才能摆脱那150%的额外存储空间呢？将字节打包到一个巨大的数组中，比如bytes或{}。然后每个散列有48个字节的总计加上32个，而不是每个散列48+32个。当你需要访问一个散列时，如果你有索引的话，它就是片[index*32:(index+1)*32]。在

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

不管怎样，现在你有800万个额外的索引。如果这些都是暂时的，那没关系，但是如果您将它们作为int存储在dict值槽中，那么每个也都有一个头。通过快速测试，在实际存储的4个字节之上（对于小于1<；<；31的int），32位和64位都有一个24字节的头（尽管很明显很小的int可以塞进头中）。所以，所有这些只会将48字节的浪费减少到28字节，这并不好。在

您可以使用某种形式的压缩存储，如^{}模块。数组类型I每个整数只使用4个字节。但是你需要数组的索引，这和你刚刚解决的问题是一样的。在

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

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

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

当然，您可以用Python构建一个定制的哈希表，使用两个大字节数组作为存储，两个array('I')作为索引。但这是一个更大的工作，所以我先试试简单的方法。在

Answer 3

使用^{} library将哈希值存储在数据库中。sqlite嵌入式数据库将尽可能使用内存缓冲和磁盘存储来管理内存，以满足您的查询。在

一张非常简单的表格就足够了：

import sqlite3

connection = sqlite3.connect('/tmp/hashes.db')
connection.execute('CREATE TABLE hashes (key UNIQUE, value)')

然后使用：

^{pr2}$

您可以通过以下方式查询数据库：

with connection:
    cursor = connection.cursor()
    sql = 'SELECT hash FROM hashes WHERE key=?'
    cursor.execute(sql, (key,))
    hash = cursor.fetchone()
    if hash is not None:
        hash = hash[0]