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

Question

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

我正在为一个用 C 编写的小型嵌入式应用程序执行此操作，因此我试图尽量减少所需的代码量和消耗的内存量。

Google sparse hash data structure如果它不是用 C++ 编写的，并且更简单，那将是可能的。

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

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

我想这在某些圈子里应该是一个比较知名的问题，所以为了不至于太主观，我想知道上述问题最常见的解决方案是什么？

[编辑:]

一些可能相关的附加信息:

• 键是整数
• 值的数量可以很小，介于 1 到 2^32 之间。
• 使用模式是不可预测的。
• 我希望保持尽可能低的内存消耗(例如，将所需的内存大小加倍，这并不理想)

Answer 1

看binary search tree并克服最坏的情况(搜索和插入都具有 O(n) 复杂度)使用 balanced tree .