Java最佳實踐– Vector vs ArrayList vs HashSet

在使用Java編程語言時，我們將繼續討論與建議的實踐有關的系列文章，我們將在三個最常用的Collection實現類之間進行性能比較。為了使事情變得更現實，我們將在多線程環境下進行測試，以討論和演示如何將Vector ， ArrayList和/或HashSet用于高性能應用程序。

所有討論的主題均基于用例，這些用例來自于電信行業的關鍵任務超高性能生產系統的開發。

在閱讀本文的每個部分之前，強烈建議您參考相關的Java API文檔以獲取詳細信息和代碼示例。

所有測試均針對具有以下特征的Sony Vaio進行：

系統：openSUSE 11.1（x86_64）
處理器（CPU）：Intel（R）Core（TM）2 Duo CPU T6670 @ 2.20GHz
處理器速度：1,200.00 MHz
總內存（RAM）：2.8 GB
Java：OpenJDK 1.6.0_0 64位

應用以下測試配置：

并發工作線程數：50
每個工作人員測試重復次數：100
整體測試次數：100

向量vs ArrayList vs HashSet

Java開發人員必須執行的最常見任務之一是從Collections中存儲和檢索對象。 Java編程語言提供了一些具有重疊和獨特特征的Collection實現類。 Vector ， ArrayList和HashSet可能是最常用的。

但是，使用Collection實現類（特別是在多線程環境中）可能會很棘手。默認情況下，它們中的大多數不提供同步訪問。因此，以并行方式更改Collection的內部結構（插入或縮回元素）肯定會導致錯誤。

這里將要討論的案例場景是通過上述每個Collection實現類的元素進行多個Thread的插入，縮回和迭代。我們將演示如何在多線程環境中正確利用上述集合實現類，并提供相關的性能比較表，以顯示在每個測試用例中哪個性能更好。

為了進行票價比較，我們將假定不允許使用NULL元素，并且我們不介意Collections中元素的順序。此外，由于矢量是唯一集合實現類我們的測試組提供了默認的同步訪問，同步的ArrayList和HashSet的集合實現類將使用Collections.synchronizedList和Collections.synchronizedSet靜態方法來實現。這些方法提供了指定Collection實現類的“包裝”同步實例，如下所示：

列表syncList = Collections.synchronizedList（new ArrayList（））;
設置syncSet = Collections.synchronizedSet（new HashSet（））;

測試用例＃1 –在集合中添加元素

對于第一個測試用例，我們將有多個線程在每個Collection實現類中添加String元素。為了保持String元素之間的唯一性，我們將如下所示構造它們：

靜態的第一部分，例如“ helloWorld”
工作線程ID，請記住，我們有50個并發運行的工作線程
worker線程測試重復次數，請記住，每個worker線程每次測試執行100次測試重復

對于每個測試運行，每個工作線程將插入100個String元素，如下所示：

對于第一次測試重復
- 工作線程1將插入String元素：“ helloWorld-1-1”
對于第二次測試重復
- 工作線程1將插入String元素：“ helloWorld-1-2”
等等...

在每次測試運行結束時，每個Collection實現類都將填充5000個不同的String元素。

下面我們展示了上述三個Collection實現類之間的性能比較表

橫軸表示測試運行的次數，縱軸表示每次測試運行的每秒平均事務數（TPS）。因此，較高的值更好。如您所見，在向Vector和ArrayList Collection實現類添加元素時，它們的執行效果幾乎相同。另一方面， HashSet Collection實現類的性能稍差，主要是由于內部結構和哈希生成機制更加復雜。

測試案例2 –從集合中刪除元素

對于第二個測試用例，我們將有多個線程從每個Collection實現類中刪除String元素。所有集合實現類都將使用來自先前測試用例的String元素進行預填充。為了刪除元素，我們將為每個Collection實現類在所有工作線程之間利用共享的Iterator實例。對Iterator實例的同步訪問也將實現。每個工作線程都將刪除Collection實現類的下一個可用元素，并發出“ next（）”和“ remove（）” 迭代器操作（以避免ConcurrentModificationException ）。下面是上述測試用例的性能比較表。

橫軸表示測試運行的次數，縱軸表示每次測試運行的每秒平均事務數（TPS）。因此，較高的值更好。同樣，從中移除String元素時， Vector和ArrayList Collection實現類的性能幾乎相同。另一方面， HashSet Collection實現類的性能遠遠優于Vector和ArrayList ，平均速度為678000 TPS。

在這一點上，我們必須指出，通過使用Vector和ArrayList Collection實現類的“ remove（0）”方法刪除String元素，與使用同步共享Iterator實例相比，我們獲得了更好的性能結果。我們之所以演示同步共享Iterator實例“ next（）”和“ remove（）”操作方法，是為了維持三個Collection實現類之間的票價比較。

重要的提醒

我們的測試用例場景要求我們從每個Collection實現類中刪除第一個元素。盡管如此，我們必須指出，這對于Vector和ArrayList Collection實現類是最壞的情況。作為我們的讀者之一，詹姆斯·沃森（James Watson）成功評論了TheServerSide的相關帖子

“ 原因是在ArrayList和Vecrtor上，如果刪除了除最后一個元素以外的任何元素（最后一個元素是索引為：size – 1的元素），則remove（）方法將導致System.arraycopy（）調用。 刪除第一個元素意味著將復制數組的整個其余部分，這是一個O（n）操作。 由于測試刪除了列表中的所有元素，因此完整測試變為O（n ^ 2）（緩慢）。

HashSet remove不執行任何此類數組副本，因此它的刪除時間為O（1）或恒定時間。 對于完整測試，則為O（n）（快速）。 如果重寫測試以從ArrayList和Vector中刪除最后一個元素，則性能可能與HashSet相似。 ”

因此，我們將再次進行此測試，從Vector和ArrayList Collection實現類中刪除最后一個元素，因為我們假定Collections中元素的順序并不重要。性能結果如下所示。

橫軸表示測試運行的次數，縱軸表示每次測試運行的每秒平均事務數（TPS）。因此，較高的值更好。不出所料，從其中刪除String元素時，所有Collection實現類的性能幾乎相同。

測試案例＃3 –迭代器

對于第三個測試用例，我們將有多個工作線程在每個Collection實現類的元素上進行迭代。每個工作線程將使用Collection “ iterator（）”操作檢索對Iterator實例的引用，并使用Iterator “ next（）”操作遍歷所有可用的Collection元素。所有Collection實現類都將使用第一個測試用例的String值預先填充。下面是上述測試用例的性能比較表。

橫軸表示測試運行的次數，縱軸表示每次測試運行的每秒平均事務數（TPS）。因此，較高的值更好。與ArrayList Collection實現類相比， Vector和HashSet Collection實現類的性能均較差。 Vector平均獲得68 TPS，而HashSet平均獲得9200 TPS。另一方面，到目前為止， ArrayList的性能優于Vector和HashSet ，平均速度為421000 TPS。

測試案例4 –添加和刪除元素

對于我們的最終測試用例，我們將實現測試用例1和測試用例2場景的組合。一組輔助線程將向每個Collection實現類插入String元素，而另一組輔助線程將從其中撤回String元素。

在組合（添加和縮回元素）操作中，無法使用用于刪除元素的同步共享Iterator實例方法。由于Collection的內部結構在不斷變化，因此從單個Collection中同時添加和刪除元素可避免使用共享的Iterator實例。對于Vector和ArrayList Collection實現類，可以通過使用“ remove（0）”操作來繞過上述限制，該操作將從Collection內部存儲器中收回第一個元素。不幸的是， HashSet Collection實現類不提供此類功能。我們建議的使用HashSet Collection實現類為組合操作獲得最大性能的方法如下：

使用兩個不同的HashSet，一個用于添加元素，另一個用于撤回
實現一個“控制器” 線程，該線程將在“收回” HashSet為空時交換上述HashSet類的內容。 “控制器” 線程可以實現為常規TimerTask ，可以定期檢查“縮回” HashSet的內容，并在需要時執行交換
交換兩個HashSet時，應為“收回” HashSet創建一個共享的Iterator實例。
所有撤消元素的輔助線程應等待“撤消” HashSet充滿元素并在交換后得到通知

以下是顯示建議實施的代碼段：

全球宣言：

Set<string> s = new HashSet<string>(); // The HashSet for retracting elements
Iterator<string> sIt = s.iterator(); // The shared Iterator for retracting elements
Set<string> sAdd = new HashSet<string>(); // The HashSet for adding new elements
Boolean read = Boolean.FALSE; // Helper Object for external synchronization and wait – notify functionality when retracting elements from the “s” HashSet
Boolean write = Boolean.FALSE; // Helper Object for external synchronization when writing elements to the “sAdd” HashSet

用于將元素添加到“ sAdd” HashSet的代碼：

synchronized(write) {sAdd.add(“helloWorld” + "-" + threadId + "-" + count);
}

用于從“ s” HashSet中撤回元素的代碼：

while (true) {synchronized (read) {try {sIt.next();sIt.remove();break;} catch (NoSuchElementException e) {read.wait();}}
}

“控制器”類代碼：

public class Controller  extends TimerTask {public void run() {try {performSwap();} catch (Exception ex) {ex.printStackTrace();}}private void performSwap() throws Exception {synchronized(read) {if(s.isEmpty()) {synchronized(write) {if(!sAdd.isEmpty()) {Set<string> tmpSet;tmpSet = s;s = sAdd;sAdd = tmpSet;sIt = s.iterator();read.notifyAll();}}}}}}

最后，安排“控制器” TimerTask的代碼

Timer timer = new Timer();
timer.scheduleAtFixedRate(new Controller(), 0, 1);

我們應該先啟動“控制器”任務，然后再啟動對相關HashSet進行讀寫的輔助線程。

請記住，對于Vector和ArrayList Collection實現類，我們使用了“ remove（0）”操作來收回元素。以下是上述Collection實現類的代碼段：

while (true) {try {vector.remove(0);break;} catch (ArrayIndexOutOfBoundsException e) {}
}while (true) {try {syncList.remove(0);break;} catch (IndexOutOfBoundsException e) {}
}

下面是上述測試用例的添加部分的性能比較表。

以下是上述測試案例的收回部分的性能比較表。

橫軸表示測試運行的次數，縱軸表示每次測試運行的每秒平均事務數（TPS）。因此，較高的值更好。 Vector和ArrayList Collection實現類在添加和撤消元素時的性能幾乎相同。另一方面，對于元素添加測試用例，與Vector和ArrayList實現相比，我們建議的實現（帶有“添加”和“縮回” HashSet對）的性能略遜一籌。但是，對于元素撤回測試用例，我們的“添加”和“撤回” HashSet對實現比Vector和ArrayList實現都要好，平均得分為6000 TPS。

快樂編碼

賈斯汀

相關文章：