Vector vs ArrayList vs HashSet

記錄一下在 Java Code Geeks 上看到的文章 [1]，主題是做 Vector、ArrayList 跟 HashSet 的比較。

[1] 本文中在透過 Collestions.synchronizedXXX() 的方法做 Thread-Safe 之後，分別對 Vector、ArrayList 跟 HashSet 做插入資料、刪除資料和列舉資料做了效能測試。
三個測試的結果如下：

插入資料

依序刪除第一筆資料

依序刪除最後一筆資料

列舉資料
從圖中看出來的大略的結論，可以看出在插入時 HashSet 的效率相對比較差一些，主因是因為 HashSet 在插入時需要做計算雜湊和雜湊比對
而刪除時比較特別，文中有節錄一段由網友 James Watson 發表的回應 [2] 如下：

The reason is that on ArrayList and Vecrtor, the remove() method will result in a System.arraycopy() call if any element except the last element is removed (the last element being the element with index: size - 1). Removing the first element means the entire rest of the array is copied which is an O(n) operation. Since the test removes all the elements in the List, the full test becomes O(n^2) (slow.)

HashSet remove does not do any such array copies so it's remove is O(1) or constant time. For the full test it then is O(n) (fast.). If the tests were rewritten to remove the last element from the ArrayList and Vector, you would likely similar performance to the HashSet.

即 ArrayList 和 Vector 在刪除資料時的 best case 是刪除最後一筆資料，而 worst case 是刪除第一筆資料
因為刪除非最後一筆資料時，需要對陣列做整體的變更，也就是會透過 System.arraycopy() 產生一個新的陣列
而如果是刪除最後一筆資料時，它只需要單純把陣列的索引值 -1 即可。
因此效能測試中，刪除第一筆資料會導致效率相當差，但如果刪除最後一筆資料時，則效率與 HashSet 相當接近。

列舉時則是 ArrayList 明顯比 Vector 和 HashSet 快很多～。

參考資料：
1、Java Best Practices – Vector vs ArrayList vs HashSet
2、Re: Java Best Practices – Vector vs ArrayList vs HashSet