[Java Performance] Java集合API

Java集合API

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

關(guān)于選擇哪個集合類型，第一個需要考慮的就是程序使用的算法和操作方式。實際上這就是從數(shù)據(jù)結(jié)構(gòu)的出發(fā)點來看問題，和使用的語言無關(guān)。

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

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

同步還是非同步

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

同步集合的歷史

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

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

當(dāng)在一個不存在競爭的環(huán)境中調(diào)用同步方法的性能如何呢？下表是在一個無競爭的環(huán)境中對分別對調(diào)用5億次基于CAS的方法，同步方法和非同步方法的執(zhí)行性能：

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

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

集合容量(Collection Size)

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

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

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

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

1. 計算擴(kuò)容數(shù)組的新空間值
2. 創(chuàng)建該數(shù)組
3. 將當(dāng)前數(shù)組的所有元素拷貝到新數(shù)組中

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

其它類型比如HashMap在對其內(nèi)部數(shù)組進(jìn)行擴(kuò)容時，使用的算法會更加復(fù)雜，但是本質(zhì)上也遵循上述的三個步驟。

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

非集合類型中的擴(kuò)容

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

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

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

• 在創(chuàng)建集合時指定容量(通過構(gòu)造函數(shù))
• 考慮使用單獨(dú)的對象進(jìn)行表示

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

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

由于在很多應(yīng)用中，集合空間都沒有被充分利用。在JDK 7u40中引入了一種針對ArrayList和HashMap實現(xiàn)的優(yōu)化：當(dāng)創(chuàng)建它們的實例時如果未指定容量信息，那么不再創(chuàng)建內(nèi)部數(shù)組。只有當(dāng)?shù)谝淮螌线M(jìn)行操作的時候，才會創(chuàng)建內(nèi)部數(shù)組。這是延遲初始化的一個典型應(yīng)用。在進(jìn)行了大量測試后，證明在大多數(shù)應(yīng)用中，使用該優(yōu)化能夠帶來更好的性能。

總結(jié)

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

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈