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

我想实现一个系统，我将有键值结构对。它们需要以某种线性方式进行（即可以对它们进行索引），并且一旦给定了一个位置就不能移动，所以只能追加插入（并且不能进行太多排序）。只是作为一个例子，这是什么算盘：允许线性布局的快速算法/数据结构？

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

我设计的系统，这样以便当键搜索，它的索引可以被缓存，然后用一定的时间访问。现在，由于我无法预测数据的顺序或数量，而且我也无法对其进行排序，所以我需要关于算法或数据结构的想法，这种想法不仅仅是一种线性搜索，而且还保留了我的约束条件，喜欢。

任何人有任何想法？我怀疑我可以加快它的速度，但每一点帮助，因为这将是我的系统的核心。提前致谢！

== EDIT ==

使用两个单独的结构（如哈希表和一个动态数组）的想法实际上是我的第一意图。不幸的是，这对我来说不起作用，因为我无法分开钥匙和价值。密钥将用于错误和消息，因此即使索引已被缓存，原始密钥仍需要被访问。基本上，他们仅仅是一个数组结构，如：

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

来源

2012-02-03 Miguel

为什么你需要缓存索引？散列表的要点是给你O（1）按键的访问权限。 – 2012-02-03 00:47:33

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

那么，我会做的只是把这个大的长键和一起擦到短（如采取32位或64位校验，或者可能是一个消息摘要），或者也许只是将它转换成一串长的位，或一个长字符串。无论散列函数想要什么。与运行散列所需的周期相比，周期方面不应该太昂贵，并且取决于每秒需要执行多少次。 – 2012-02-03 14:42:16

一种选择是使用散列表和动态数组的组合。这个想法如下 - 无论何时向数据结构中插入一个元素，都会将其附加到动态数组中，然后将该密钥插入到与该索引相关联的哈希表中，然后插入到键/值对所在的动态数组中。这样，通过索引查找，您只需查看动态数组，然后按名称查找，即可在散列表中查找索引，然后在该索引处查询。这需要用于插入，删除和访问的预期O（1）时间，这比线性搜索快得多。

希望这会有所帮助！

来源

2012-02-03 00:14:03 templatetypedef

我不认为这对我有效，因为我无法从数据中分离出密钥。请参阅编辑该问题，请:) – Miguel 2012-02-03 00:41:41

@ athlon32-我不确定我明白为什么这不起作用。如果你的数组持有键和值，并且哈希表只是存储了键，为什么这个数据结构不起作用？ – templatetypedef 2012-02-03 00:42:57

好吧，那可以工作，但如果我有成千上万的条目，可能会有点矫枉过正，尽管我可以保留指向该键的指针，但仍然会比我想要的要多一点。：/这就是说，我不希望从这个问题中得到更多的答案，所以我可能不得不使用这种方法...... – Miguel 2012-02-03 00:49:27

怎么样一个哈希表键 - >索引数组？

来源

2012-02-03 00:12:14 Marcin

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

回答

相关问题