允許線性佈局的快速算法/數據結構？

我想實現一個系統，我將有鍵值結構對。它們需要以某種線性方式進行（即可以對它們進行索引），並且一旦給定了一個位置就不能移動，所以只能追加插入（並且不能進行太多排序）。只是作爲一個例子，這是什麼算盤：允許線性佈局的快速算法/數據結構？

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

允許線性佈局的快速算法/數據結構？

回答

相關問題