Python（或C）中高效内存的字符串映射
我需要一个节省内存的数据结构，用来存储大约一百万对键值对。这里的键是大约80字节的字符串，值是大约200字节的字符串，这样总的键值大小大约是280MB。我还需要能够高效地通过键查找值，最好是用哈希表。内存的额外开销要尽量小，比如说对于280MB的有效数据，这个数据结构的虚拟内存使用量不应该超过300MB（包括malloc()的开销和其他所有东西）。使用模式是这样的：我们从一个空的数据结构开始，逐渐填充它，键不会改变，值的长度也不会改变。作为额外要求，这个数据结构可以支持改变值的长度，但会造成100%的值开销（也就是说，对于x字节的值，可能会有x字节暂时浪费在未使用的缓冲区空间里）。
我需要一个纯Python模块，或者一个内置的Python模块，或者一个C语言实现，最好带有(C)Python的绑定。我希望能够将整个数据结构序列化到磁盘上，并且能够非常快速地读取回来。
为了证明这样的小开销是可能的，我设计了一个简单的方案，使用开放寻址法，这个哈希表包含125万个元素，每个元素指向1MB的数据块，数据块里包含键和值的长度，使用base-128变长整数。这个设计有一个重要的限制：它不允许删除或更改键值对，否则会浪费它们的内存区域。根据我的计算，对于每个280字节的一百万对键值对，开销小于3.6%（10,080,000字节）。上面的限制更宽松，允许20,000,000字节的开销。
我刚刚发现了http://www.pytables.org/，它提供了快速访问和节省内存的数据打包。我需要更仔细地检查一下，看它是否符合我的需求。
10 个回答
Martijn在评论中提到过这个（我不太明白为什么有人在评论里给出答案），但我同意他的看法：用SQLite。你可以试试看，看看它是否能满足你的需求。
好的，咱们来聊聊一个超级简单的方法。
可以用一个Python字典来存储数据。我创建了一个包含100万个随机键值对的Python字典，其中每个键有80个字符，值有200个字符。在我的电脑上，这个字典占用了360,844 Kb的内存，虽然超出了你说的300 MB的限制，但我还是觉得这个方法不错，因为它的内存使用效率还是挺高的。
不过，这个方法不符合你要求的有C语言接口。我不太明白你为什么需要C语言，但既然问题是关于Python的，而且没有C语言的标签，我就先提供这个纯Python的方法，看看是否能满足你的需求。
关于数据持久化，可以使用cPickle模块。这个模块非常快，而且也很简单。要保存你的字典，可以用：
cPickle.dump(mydict, "myfile.pkl")
要重新加载你的字典，可以用：
mydict = cPickle.load("myfile.pkl")
还有一个简单的想法是使用shelve模块，它基本上是一个基于磁盘的Python字典。它的内存占用非常低（因为数据都在磁盘上）。不过，它的速度会慢一些。
因为我找不到任何现成的解决方案可以紧凑地存储内存，所以我决定自己用C语言来实现一个。可以在问题中看到我设计的使用开放寻址的方法。