快速的算法/数据结构，允许线性布局？

Question

我正在尝试实现一个系统，其中将有键值结构对。它们需要以某种线性方式保存（即，它们可以被索引），并且一旦给定位置就不能移动，因此插入只能进行追加（并且不能进行排序）。仅作为示例，以下是我的想法：

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; 
}

- Miguel

---

为什么需要缓存索引？哈希表的目的是通过键提供 O(1) 访问。 - Mike Dunlavey

@MikeDunlavey 关键是相当复杂的（它将是一个任意长度的字符串和一个设置数组。几个关键字可以有相同的字符串，但通过设置而不同）。在这种情况下，有什么好的无碰撞哈希表算法可以使用？ - Miguel

我的建议是将那个长长的密钥压缩成一个短字符串（例如采用32位或64位的校验和，或者信息摘要），或者只是将其转换为一长串比特或字符串，视哈希函数而定。这应该比运行哈希所需的周期花费少得多，具体取决于每秒需要执行多少次。 - Mike Dunlavey

如果你这样做，而不是将索引缓存到表中，哈希映射就不需要无冲突。 - Mike Dunlavey

Answer 1

如何将哈希表的键值映射成数组的下标？

- Marcin

Answer 2

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

希望这有所帮助！

- templatetypedef

---

我认为这对我不起作用，因为我无法将键与数据分开。请参见问题的编辑 :) - Miguel

@athlon32- 我不确定为什么这个方法行不通。如果你的数组包含键和值，而哈希表只存储键，那么这种数据结构为什么不能工作呢？ - templatetypedef

好的，那样做是可行的，但如果我有成千上万条目，可能会有点过度，虽然我可以只保留指向关键字的指针，但仍然比我想要的多一点。 :/ 话虽如此，我不指望从这个问题中得到更多的东西，所以我可能不得不使用这种方法... - Miguel

@athlon32- 实际上，相比你所得到的性能，额外开销并不算太大。你将会使用大约2倍于原来的内存来存储哈希表，随着条目数量的增加，性能优势也会增加。 - templatetypedef

您不需要将键与数据分开。如果为您的键实现哈希函数，您可以将哈希索引保持在(hash_value->list_index)形式中，以获得最小的开销。 - comingstorm