3

我正在尝试实现一个具有键值结构对的系统。它们需要以某种线性方式保存（也就是说，它们可以被索引），一旦给定一个位置就不能移动，所以插入只能追加（实际上不能有太多的排序。）举个例子，这就是我的想法：

Data list:
    0: { "somekey", somevalue }
    1: { "someotherkey", someothervalue }
    ...
    n: { "justanotherkey", justanothervalue }

我已经设计了这样的系统，以便在搜索一个键时，它的索引可以被缓存，然后以恒定的时间访问。现在，由于我无法预测数据的顺序或数量，而且我无法对其进行排序，因此我需要关于算法或数据结构的想法，这些想法会比线性搜索更好，但仍然保持约束我'我喜欢。

有人有什么想法吗？我怀疑我能否加快速度，但每一点都会有所帮助，因为这将是我系统的核心。提前致谢！

==编辑==

使用两个独立结构（如哈希表和动态数组）的想法实际上是我的第一个意图。不幸的是，这对我不起作用，因为我无法分离键和值。键将用于错误和消息，因此即使缓存了索引，仍需要访问原始键。基本上它们必须只是一个数组结构，例如：

struct Entry {
    /* Key is actually a complex struct itself with string, and params */
    Key key;
    Data* data; 
}
4

2 回答 2

4

哈希表键-> 数组中的索引怎么样？

于 2012-02-03T00:12:14.960 回答
2

一种选择是使用哈希表和动态数组的组合。这个想法如下 - 每当您将元素插入数据结构时，您将其附加到动态数组中，然后将键插入与索引关联的哈希表中，并插入键/值对所在的动态数组中。这样，要按索引查找，您只需在动态数组中查找，按名称查找，您在哈希表中查找索引，然后在该索引处查询。这需要 O(1) 的插入、删除和访问时间，这比线性搜索要快得多。

希望这可以帮助！

于 2012-02-03T00:14:03.010 回答