所有集合類，性能在Java中
我已經經歷了很多那個帖子關於各種集合類的各種動作，即添加元素，檢索和刪除的性能網站。但我也注意到，他們都提供了不同的環境，其中測試進行，即操作系統，內存，線程運行等。
我的問題是，如果有任何網站/材料提供最佳測試相同的性能信息環境基礎？即配置不應成爲任何特定數據結構性能差的問題或催化劑。
[更新]：實施例，HashSet的和LinkedHashSet都具有的O（1）用於插入的元件的複雜性。然而，布魯斯埃克爾」測試聲稱插入將要花費更多的時間LinkedHashSet比的HashSet [http://www.artima.com/weblogs/viewpost.jsp?thread=122295]。那麼我還應該用Big-Oh符號去嗎？
這裏是我的建議：。
或者你可以..你知道......不是優化平臺和編譯器會改變，但一個好的設計應該 - 平均 - 執行不夠好
其他的事情，你也可以這樣做：。
話雖這麼說，我不知道爲什麼你需要的性能提升，所以也許你有一個非常有效原因。
我並不是說挑選正確的收藏並不重要。就是那些你知道選擇哪一個來解決特定問題，並且你已經考慮過替代方案，那麼你已經完成了你的工作而不必感到內疚。集合通常具有語義意義，只要你尊重它，你就會好起來的。
有道理。謝謝 ！ – 2010-10-20 15:52:55
@ darkie15：不客氣。 – haylem 2010-10-20 16:05:36
在我看來，所有你需要了解的數據結構是它的操作，從不同的架構不是主觀措施的大O。不同的收藏有不同的用途。
Map s爲詞典
Set小號斷言獨特
List小號提供分組，並保留迭代爲了
Tree小號提供廉價的排序和快速搜索動態改變的內容需要不斷訂貨
編輯到包括bwawok的樹結構的使用case語句
的哈希表和鏈接列表實現Set接口，具有可預知的迭代順序。
...
性能很可能只是略低於HashSet的，因維護鏈接列表，但有一個例外的額外費用了：LinkedHashSet迭代所需的時間與的大小不管其容量如何。 HashSet上的迭代可能會更加昂貴，需要的時間與其容量成正比。
現在我們已經從選擇適當數據結構接口的一般情況轉移到更具體的使用哪種實現的情況。但是，我們最終還是會得出這樣的結論：特定實現非常適合基於每個實現提供的獨特，細微不變的特定應用程序。
整體非常真實，我也認爲。我的小意見是，樹（樹圖和我假設的集合）並不便宜。如果打算製作一個1000000個項目的列表，然後查看它們的排序順序，最好使用您在最後排序的ArrayList。 tree map/set的實際使用情況非常罕見，必須添加很多東西，並且需要在任何給定點處對它進行排序。 – bwawok 2010-10-19 23:03:42
@bwawok，你說得很對。我已經更新了我的答案，希望能更好地反映您的非常有用的觀點。 – 2010-10-19 23:16:23
@Tim：更新了我的查詢。 – 2010-10-19 23:31:19
你有什麼需要了解他們，爲什麼？基準測試顯示給定的JDK和硬件設置的原因是，它們可以（理論上）被複制。你應該從基準中得到什麼是一個事情將如何工作的想法。對於一個絕對數字，你需要運行它與你自己的代碼做你自己的事情。
最重要的是要知道的是各種收藏的Big O運行。知道從未排序的ArrayList中獲取元素是O（n），但是將其從HashMap中取出爲O（1）是巨大。
如果您已經在給定的工作中使用正確的集合，那麼您就有90％的選擇。當你需要擔心你能夠以多快的速度將項目從HashMap中取出時，應該相當難得。
一旦你離開單線程的土地，並進入多線程的土地，你將需要開始擔心諸如ConcurrentHashMap vs Collections.synchronized散列表。除非你是多線程的，否則你可以不用擔心這種東西，並關注哪些集合用於哪些用途。
更新到HashSet的VS LinkedHashSet
我還沒有發現過，我需要一個鏈接哈希集合（用例，因爲如果我在乎我命令往往有一個列表，如果我在乎Ø （1）獲取，我傾向於使用一個HashSet實際上，大多數代碼將使用ArrayList，HashMap的，或HashSet的。如果你有什麼事，你是在一個「邊緣」情況
更新了我的查詢。 – 2010-10-19 23:30:43
LinkedHashSet用於當您希望能夠遍歷哈希集中添加元素的順序。 – 2010-10-20 01:16:58
@Jason S：好的，我會更新澄清。我從來沒有在我的代碼中滿足它的需求......如果我關心順序，我傾向於使用ArrayList。所以我想你會需要關心順序和O（1）變得想要一個LinkedHashSet。 – bwawok 2010-10-20 13:07:37
如果我不得不排序數百萬行，我會嘗試找到不同的方式。也許我可以改進我的SQL，改進我的算法，或者將元素寫入磁盤並使用操作系統的排序命令。
我從來沒有一個案例，其中我的表現問題的原因集合。
男孩，我有：http://stackoverflow.com/questions/926266/performance-optimization-strategies-of-last-resort/927773#927773 – 2010-10-20 01:18:42
我很抱歉，但我不確定你在這裏的意思。我從來不想談論持久性。 – 2010-10-20 16:01:40
不同的集合類有不同的大O表現，但所有告訴你是他們如何擴大規模。如果你的集合足夠大，那麼O（1）將會比O（N）或O（logN）好，但除了實驗外，沒有辦法告訴N的什麼值是盈虧平衡點。通常，我只是使用最簡單的可能的事情，然後如果它成爲一個「瓶頸」，如該數據結構上的操作所花費的時間百分比很長，那麼我將切換到更好的大O評分。通常情況下，集合中的項目數量不會接近盈虧平衡點，或者有另一種簡單的方法來解決性能問題。
HashSet和LinkedHashSet都具有O（1）的性能。 （HashMap和LinkedHashMap）（實際上前者是基於後者實現的）。這隻告訴你如何這些算法規模，而不是他們如何實際執行。在這種情況下，LinkHashSet完成與HashSet完全相同的工作，但始終必須更新上一個和下一個指針才能維護訂單。這意味着對於HashSet，常數（這在談論實際算法性能時也是一個重要的值）低於LinkHashSet。因此，由於這兩者具有相同的Big-O，所以它們本質上相同 - 也就是說，由於和的變化，兩者具有相同的性能變化，並且平均而言，O（1）的性能不變。
所以現在你的選擇是基於功能和你的要求（這真的應該是你首先考慮的東西）。如果您只需要快速加和得到操作，您應該始終選擇HashSet。如果您還需要一致的訂購 - 例如上次訪問或插入訂單 - 那麼您的必須也使用該類的Linked ...版本。
我在生產應用中使用了「鏈接」類，以及LinkedHashMap。我在一個案例中使用了這種符號，因此希望快速訪問符號和相關信息。但我也想按照用戶定義這些符號（插入順序）的順序在至少一個上下文中輸出信息。這使得輸出對用戶更友好，因爲他們可以按照定義的順序查找事物。
明白了。謝謝 – 2010-10-20 15:55:51
我用HashSets和LinkedHashSets創建了我自己的實驗。對於add（）並且包含運行時間是O（1），沒有考慮到很多衝突。在linkedhashset的add（）方法中，我將該對象放在用戶創建的散列表中，該散列表爲O（1），然後將該對象放入單獨的鏈接列表中以考慮順序。因此，從鏈接的哈希集中移除元素的運行時間，您必須在哈希表中查找元素，然後搜索具有順序的鏈接列表。因此，運行時間分別是O（1）+ O（n），它是o（n），用於刪除（）
你究竟在幹什麼？有一個原因，比方說，當你使用基元時，免費的和優秀的Trove集合圍繞着默認的Java集合運行。例如，將Trove的* TLongLongHashMap *的性能與默認的Java * HashMap {Long，Long}進行比較並非易事。*：Trove擊敗了Java。大O不是唯一重要的... – SyntaxT3rr0r 2010-10-19 23:20:33
@Webinator：更新了我的查詢。 – 2010-10-19 23:29:56