具有固定時間訪問和可變大小的數據結構

在我的一次採訪中，我被問到了這個問題。具有固定時間訪問和可變大小的數據結構

是否有其具有以下功能2的數據結構：

。恆定時間訪問（隨機訪問），如ArrayList

。可變大小，如LinkedList

如果沒有這樣的數據結構，請自行創建一個。

2011-03-19 Bhushan

Er，ArrayList *是*可變大小（？） – 2011-03-19 21:31:15

我相信你正在尋找的答案是「哈希表」（See: "Hash Table" in Wikipedia）爲你評論說，他們正在尋找一個又一個超越ArrayList（對於Java，請參閱：Hashtable）

雖然知道它可以是在附近的恆定時間取決於散列算法和數據集，因爲可能發生衝突導致（短）次級線性搜索。 Javadoc非常好地解釋了在Java實現中如何處理這個問題。

2011-03-19 21:38:43

或者[HashMap]（http://download.oracle.com/javase/6/docs/api/java/util/HashMap.html） – 2011-03-19 21:48:20

@Zack - 絕對。我編輯的時候更加清晰，我試圖描述泛型數據結構，然後給出一個java實現示例。 – 2011-03-19 21:55:28

我明白:-)。當我看到「Hashtable」提到HashMap時，只是本能。 – 2011-03-19 22:03:25

除了哈希表爲Brian Roach說，採訪者可能已經被影射到一個LinkedHashMap或LinkedHashSet，它提供了大約爲一些基本操作常數時間的性能，同時還保持插入的順序的，因爲它結合了的HashTable與雙向鏈表。

換句話說，如果循環遍歷鍵，則將元素放入LinkedHashMap的順序與它們檢索的順序相同。

雖然使用集合的一個缺點是你不能有重複，並且地圖也不能有重複的鍵。解決方法是使用一組列表，或者使用Google的Multimap。

但正如其他人所說，一個ArrayList已經滿足兩個要求。這是一個數組，它沒有可變大小。

另外，與ArrayList的O（n）性能相比，LinkedList在ArrayList上的主要優勢是在列表的末尾和開始處都是constant time insertion/deletion。兩者都可以提供可變大小。

2011-03-19 21:52:55

deque或「雙端隊列」如何？在許多實現，它不能有效地用於插入和刪除在任何位置，但其頭或尾改變大小，但它另有規定你所尋求的兩個屬性：

您可以通過標籤的方式提及的Java在你的問題—陣列通常被存儲，我必須注意到，在爪哇the Deque interface確實不是提供隨機存取。即使the ArrayDeque concrete class不提供它。這是一個不幸的選擇，是爲了使其更加抽象和儘可能少地要求界面。

無論如何，除了Java之外，您會發現滿足您請求的屬性的deque實現。

2011-03-19 22:20:02 seh

任何使用雙向鏈表的實現都將隨機訪問O（n），除了頭部或尾部，這實際上是您通過Java實現獲得的。 – 2011-03-19 22:55:42

爲什麼在將元素插入LinkedList並在恆定時間從哈希表中讀取時，爲什麼沒有一個散列表並插入其中的所有元素。

2012-12-28 19:35:59 AKS

回答