我需要一个内存高效的数据结构来存储大约一百万个键值对，其中键是大约 80 字节的字符串，值是大约 200 字节的字符串，键和值的总大小约为 280MB .我还需要按键高效查找值，最好是 HashMap 。内存开销应尽可能少，例如对于 280MB 的有用数据，数据结构不应使用超过 300MB 的虚拟内存(包括 malloc() 开销和其他所有内容)。使用模式如下:我们从一个空数据结构开始，逐渐填充它，从不更改键，从不更改值的长度。此外，数据结构可能支持更改值的长度，但代价是 100% 的值开销(这意味着对于 x 值字节，x 字节可能会暂时浪费在未使用的缓冲区空间中)。
我需要一个纯 Python 模块，或者一个内置的 Python 模块，或者一个最好带有 (C)Python 绑定(bind)的 C 实现。如果可以将整个数据结构序列化到磁盘并快速读回，我更愿意。
为了证明如此小的开销是可能的，我用 open addressing 创建了一个简单的设计, 包含125万个元素的哈希表包含指向1MB数据 block 的4字节指针，数据 block 包含的键和值长度为base-128 varints .这种设计有一个重要的限制:它不允许在不浪费内存区域的情况下删除或更改对。根据我对 100 万个键值对(每个 280 字节)的计算，开销小于 3.6%(10 080 000 字节)。上面的限制更为宽松，它们允许 20 000 000 字节的开销。
我刚找到 http://www.pytables.org/ ，它提供了快速访问和内存高效的数据打包。我必须更仔细地检查它是否符合我的需要。
最佳答案
好的，非常简单的方法。
使用 python 字典作为数据结构。我用 100 万个随机键值对填充了一个 Python 字典，其中键是 80 个字符，值是 200 个字符。它在我的计算机上占用了 360,844 Kb，这超出了您不超过 300 MB 的规范，但我还是将其作为解决方案提供，因为它的内存效率仍然很高。
这也不符合您对 C API 的要求。我不确定您为什么需要 C，但由于问题被标记为 Python 并且缺少 C 标记，我将提供纯 Python 以查看它是否符合要求。
关于坚持。使用 cPickle 模块。它非常快，而且非常简单。保存字典:
cPickle.dump(mydict, "myfile.pkl")
要重新加载您的词典:
mydict = cPickle.load("myfile.pkl")
第二个非常简单的想法是使用 shelve 模块，它基本上是基于磁盘的 python 字典。内存开销非常低(都在磁盘上)。但它也慢得多。
关于python - Python(或 C)中的内存高效字符串到字符串映射，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4026359/