C中关联集合的简单空间高效实现？

Question

我正在寻找一个关联集合，它支持至少在O(Log(N))时间内按键检索和插入值(删除不重要)，并且在代码大小和运行时内存消耗方面都具有非常低的内存开销。

我这样做是为了一个用C编写的小型嵌入式应用程序，所以我试图尽量减少所需的代码量和占用的内存量。

如果Google稀疏散列数据结构不是用C++编写的，并且更简单，那么它是一种可能。

我所知道的大多数哈希表实现使用了相当多的额外空间，所需的空间至少是键值总数的两倍，或者每个条目需要额外的指针(例如桶链哈希算法)。在我的结构中，键值对只是两个指针。

目前，我使用的是排序的键/值对数组，但是插入是O(N)。我情不自禁地认为，必须有一个聪明的方法来提高分期运行的插入时间，例如，通过分组进行插入，但我没有取得任何成功。

我认为这一定是某些圈子里比较有名的问题，所以为了使这个问题不太主观，我想知道上面提到的问题最常见的解决方法是什么？

编辑：

一些可能相关的补充资料：

• 键是整数
• 值的数目在1到2^32之间的任何地方都可能很小。
• 使用模式是不可预测的。
• 我希望保持尽可能低的内存消耗(例如，增加一倍所需内存，这并不理想)。

Answer 1

您可以使用不使用链接的哈希表，例如线性探测或杜鹃散列方案。支持实现只是一个数组，负载因子约为0.5，开销不会太大，实现复杂度(至少对于线性或二次探测而言)不会太大。

如果您想要一个很好的二进制搜索树的实现，它对性能有很好的保证，并且不太难编码，可以考虑查看显示树。它们保证摊销的O(lg n)查找，并且每个节点只需要两个指针。平衡步骤也比大多数平衡的BST简单得多。

Answer 2

看看二值搜索树，为了克服最坏的情况(搜索和插入都具有O(n)复杂性)，请使用平衡树。

Answer 3

我可能会使用带有双哈希的哈希表来解决冲突。一般的想法是散列原始值，如果发生碰撞，则执行第二个哈希，该哈希将给出一个步骤值，用于遍历数组以找到放置该值的位置。这很好地利用了内存，因为它没有指针的开销，并且在比线性探测高得多的负载因子下保持了合理的效率。

编辑:如果您想要改变您现在正在做的事情，一种可能是处理集群中的插入:保持一个排序数组和一个单独的新插入集合。当新插入的集合变得太大时，将这些项合并到主集合中。

对于二次收集，您有几个选择。你只需使用一个未排序的数组，然后进行线性搜索--只需限制它的大小，例如，log(M)，其中M是主数组的大小。在这种情况下，整个搜索仍然是O(log )，不增加内存开销，并且保持大多数插入相当快。当您将集合合并在一起时，您(通常)希望对辅助集合进行排序，然后与主集合合并。这使您可以根据辅助集合中的项数摊销线性合并。

或者，您也可以使用树作为辅助集合。这意味着新插入的项对指针使用额外的存储，但是(同样)保持这个大小限制了开销。