ANSI C哈希表在一个内存块中的实现

Question

我正在寻找一个开放源码的哈希表的C实现，它将所有的数据保存在一个内存块中，这样它就可以很容易地通过网络发送。我只能找到为添加到其中的每个键-值对分配较小内存的方法。

非常感谢您的所有投入。

编辑:它不一定要是一个哈希表，不管键-值对表可能做什么。

Answer 1

在unix系统上，我可能会使用共享内存缓冲区(请参阅shm_open())，或者如果不能使用带有MAP_SHARED标志的内存映射文件，请通过http://en.wikipedia.org/wiki/Mmap查看特定于操作系统的差异

如果shm_open和mmap都不可用，你仍然可以使用磁盘上的文件(在某种程度上)，你必须关心正确的锁定，我会向下一个进程发送一个解锁信号，可能还会查找文件的更新部分，然后该进程再次锁定文件，寻找感兴趣的部分，并照常进行(更新/删除/等等)。

在任何情况下，您都可以自由地设计哈希表的布局或任何您想要的布局，比如具有固定宽度的键/寻道对。这样，您就可以快速访问哈希表的键，如果需要，您可以查找数据部分，然后复制/删除/修改/等等。

当然，理想情况下，这个文件应该在一个ram磁盘上。

Answer 2

你序列化这种数据结构的次数(通过网络发送也是序列化的)与你使用这种数据结构(在你的程序中)的次数是相当低的。因此，大多数实现更关注速度，而不是“可能更容易序列化”这一方面。

如果所有数据都在一个分配的内存块中，那么在该数据结构上的许多操作将会有点昂贵，因为您必须：

• 在add-operations
• most上重新分配内存类似于删除操作时的压缩/真空(这样，您最喜欢的数据块就是密集的，没有空洞)

大多数网络操作都是缓冲的，只需迭代键并发送键+值。

Answer 3

我完全同意akira (+1)。关于数据局部性，只需要再多说一句。一旦表变得更大，或者如果卫星数据足够大，几乎肯定会有缓存污染，这会进一步减慢表上的任何操作，或者换句话说，当您必须访问卫星数据(例如，用于序列化)时，您可以依赖1/2/3级缓存链来及时提供关键数据，同时忍受缓存未命中。