黑毛到白毛的攻城獅之路: [筆記] JDK 效率比較：Collection

在看 [1] 這本書時，覺得有些東西應該先寫下來
並且書上的比較方法我覺得還可以換點不同的圖表做比較～
所以花了些時間把書上的統計數據抄錄出來，用 Excel 畫了別的圖。

先前情提要，書上在比較 Collection 的各種物件時，主要針對插入、搜尋和刪除三個動作做比較
動作都是插入、搜尋或刪除 100 個元素。
在 Collection 已有不同的長度之下，比較各種長度的狀況的效率～
另外也同時對單執行緒和多執行緒的狀況分別做比較。

單執行緒

為了能夠明顯地看出插入、刪除和搜尋的效率差異，我在圖表上故意調整成三張圖的橫軸範圍都是 0ms～14000ms。

在插入的部份來說，大體上只有 TreeMap 和 TreeSet 在插入 100 個元素時效率明顯下降
其他 Collection 物件變化幅度都差不多。
值得注意的大概是～概念上等於是 synchronized 版 ArrayList 的 Vector
在插入的各種狀況，效率都比 ArrayList 來得高～XD（應該跟擴充方式有關，Vector 在擴充容量時的作法跟 ArrayList 稍有不同）。

尋找和刪除的部份，可以看出 List 相關的 Collection 物件在總元素數目到達 1,000 時，效率下降非常明顯
其實這也是蠻正常的結果，因為 List 類型的 Collection 在遇到搜尋和刪除時
平均來說應該要探訪一半的元素，才能順利找到目標元素。複雜度是 O(n)
而 HashMap 相關的 Map/Set 類型的 Collection 則理論上是 O(1)（雖然實際執行時看來並沒有 O(1) 那麼快 XD）。

書上實際上還有在總元素數目為 10,000 個時做插入、刪除和搜尋的資料，不過數據結果跟 1,000 的狀況差不多
List 相關的 Collection 的刪除和搜尋時間暴增，HashMap 相關的則沒什麼明顯差異。

多執行緒
同樣是增加、刪除和尋找 100 個元素，在多執行緒的狀況如下。X 軸的單位固定在 0ms~3000000ms。