[Java Performance] Java集合API

Java集合API

Java 7提供了至少58個功能和實現各異的集合類型，在不同的場景下選擇合適的集合類型十分重要。因為，程序的性能和集合類型的選擇有莫大的關聯。

關于選擇哪個集合類型，第一個需要考慮的就是程序使用的算法和操作方式。實際上這就是從數據結構的出發點來看問題，和使用的語言無關。

比如，LinkedList不適合用在搜索操作較多的場合；如果需要以O(1)的開銷從集合中得到某個元素，那么使用HashMap；如果集合中的元素需要保持有序，那么使用TreeMap而不要試圖自己來對集合排序；如果希望能夠通過索引訪問元素那么可以考慮ArrayList；如果經常性的需要在有序集合的中間插入元素，那么就不要選擇ArrayList，等等。

除了這些通用于所有語言的考慮之外，在Java中選擇合適的集合時當然也有其他考慮。

同步還是非同步

幾乎所有的Java集合都是非同步的。除了Hashtable，Vector和其相關同步集合外。

同步集合的歷史

在Java 1.2之前，Hashtable和Vector是僅有的集合類型。那時還沒有Java集合框架(Java Collection Framework)這一概念。當時的Java是一門新興的語言，大多數開發者都不能很好地理解線程機制(Threading)，所以Java的設計者們希望能盡量把語言設計的簡單一些來讓開發者們避開一些由于使用線程而導致的問題。因此，這些集合類就被設計成同步的，從而保證了線程安全。

然而，在早期的Java中，同步帶來的性能弊端是很嚴重的，即使是在沒有競爭的同步(Uncontended Synchronization)中。所以在Java的下一個版本中，使用了一種截然不同的設計思路：所有的集合類型默認都是非同步的。

當在一個不存在競爭的環境中調用同步方法的性能如何呢？下表是在一個無競爭的環境中對分別對調用5億次基于CAS的方法，同步方法和非同步方法的執行性能：

就單詞操作時間而言，差異并不太大。當時當一個應用需要運行相當長的時間且相應方法被執行的非常頻繁時，還是能夠看出它們的性能差異。無論使用相對高級的CAS操作還是傳統的同步方法，在非競爭環境下的性能都比費同步方法落后很多。因此，需要仔細查看和考慮程序中被聲明為同步的方法及同步代碼塊是否真的有必要。

所以在一個非競爭環境中，ArrayList的性能要比Vector的性能好大概2倍(100% vs 302.6%)。同時，HashMap的性能也比ConcurrentHashMap好大概0.7倍(100% vs 169.2%)。

集合容量(Collection Size)

對于Java中的集合類型，表示集合中元素的方法有以下幾種情況：

• 使用數組進行集合元素的保存，比如ArrayList，HashMap等
• 使用自定義類型進行元素的保存，比如LinkedList中使用了Node類型表示單個元素
• 結合了數組和自定義類型的方式，比如HashMap它使用數組來作為元素的保存方式，但是數組元素的類型是HashMap$Entry

如何知道一個集合類型是否使用的是數組作為其元素的保存方式呢？可以查看該類型的構造函數，如果其中會接受一個初始空間的整型變量作為參數，那么它在內部使用的就是數組。

對于使用數組的集合，需要在對它們進行初始化時，給出一個精確的容量。這樣能夠帶來更好的性能。比如ArrayList類型內部的數組默認容量是10，那么當需要存放第11個元素的時候，ArrayList會做以下幾件事：

1. 計算擴容數組的新空間值
2. 創建該數組
3. 將當前數組的所有元素拷貝到新數組中

以上的第二步和第三步對性能會有較大的影響。

其它類型比如HashMap在對其內部數組進行擴容時，使用的算法會更加復雜，但是本質上也遵循上述的三個步驟。

數組的擴容容量是通過每次增加當前容量的一半計算得到的。比如對于一個ArrayList對象，初始的空容量是10，那么再需要擴容時，下一次會分配一個能容納15個元素的數組，再下次是22個，然后33個，以此類推。使用這種方式擴容，在平均情況下數組的空間利用率大概是83.3%。所以當這個數組的容量本身已經非常大時，每次擴容都會帶來大量的內存浪費，從而增加了GC的壓力。這還不算拷貝數組這個操作帶來的性能損耗。

非集合類型中的擴容

除了集合類型，還有不少類型也會在內部使用數組來存儲和表示實際的數據。典型的比如：ByteArrayOutputStream，StringBuilder和StringBuffer。對于這些類型，也可以發現它們的構造函數也能夠接受一個size作為參數來指定初始的容量。所以，在使用它們時盡可能地估計一個靠譜的初始容量能夠帶來更好的性能。

集合和內存效率(Collections and Memory Efficiency)

在使用基于數組的集合時，還有另外一個更極端的情況，即集合元素非常少。這種情況下，數組的空間利用率就更低了，導致的就是無謂的內存空間浪費和GC壓力。對于這種情況，有兩個解決方案：

• 在創建集合時指定容量(通過構造函數)
• 考慮使用單獨的對象進行表示

當開發人員問問到哪種排序方法能夠最快地對一個數組進行排序時，不少人會回答“快速排序”。但是好的開發人員則會首先問這個數組的容量是多大。如果一個數組的容量足夠小，那么使用插入排序才是最快的排序方法。實際上，在快速排序中當被劃分的子數組的容量小于某個閾值時，會轉而使用插入排序。JDK中的Arrays.sort()方法中，就假設了當數組的容量小于47時，插入排序會有更好的性能。

JDK 7u40 中集合的延遲初始化

由于在很多應用中，集合空間都沒有被充分利用。在JDK 7u40中引入了一種針對ArrayList和HashMap實現的優化：當創建它們的實例時如果未指定容量信息，那么不再創建內部數組。只有當第一次對集合進行操作的時候，才會創建內部數組。這是延遲初始化的一個典型應用。在進行了大量測試后，證明在大多數應用中，使用該優化能夠帶來更好的性能。

總結

1. 根據需要使用最合適的集合類型，注意應用場景是否真的需要同步集合。
2. 對于基于數組的集合，在創建它們時指定容量至關重要，這樣能夠帶來更好的性能。

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈