List

ArrayList

實現原理內部封裝Object[]數組(若創建時未指定長度?數組初始長度默認為10)

實質為?:無序數組?插入快?查找和刪除指定元素慢

總結

O(1)

O(N)

O(1)?System.arraycopy

get(int?i)

Y

set(int?index,Object?obj)

Y

add(Object?obj)

Y

add(int?index,Object?obj)

Y

remove(int?index)

remove(Object?o)

Y

contains(Object?obj)

Y

結論(實驗ArrayListPerformanceTest.java)

add(int?index,?E?element)?添加元素到指定位置?效率低下

add(E?e)?添加單個元素?效率高

LinkedList

實質：雙向鏈表

O(1)

O(N)

getFirst()/getLast()

Y

removeFirst()/removeLast()

Y

addFirst(E?e)/?addLast(E?e)

Y

contains(Object?o)

Y

add(E?e)

Y

remove(Object?o)

Y

get(int?index)

Y

set(int?index,?E?element)

Y

實驗結果

ArrayList?add(E?e):??????????????????? ??60460850ns

LinkedList?add(E?e):?? ?? ??54999241ns

ArrayList?remove(index):?? ??????1855036016ns

LinkedList?remove(object):? ??42823941ns

ArrayList?contains(Object?o):?? ??15517890276ns

LinkedList?contains(Object?o):? ??29827766030ns

ArrayList與LinkedList效率比較

ArrayList查找操作的效率最高為，但其在添加和刪除操作時需要拷貝數組所以效率較低，尤其是刪除操作。該數據結構適用于需要頻繁快速查找的地方。

LinkList?查找操作效率較低為，但其插入與刪除操作效率較高，適用于需要頻繁進行插入刪除操作的情況。

MAP

HashMap

Map是一組key-value(鍵值對)集合，其中的key(鍵)不能重復。

HashMap?用key對象生成hashcode然后映射到Entry[]數組中(JDK1.6中其hashtable默認大小為16，在持有對象數量查過默認大小之后就會重新生成一個更大HashTable，然后將原有持有的對象逐個散列到新哈希表中)。其get(Object?key)最佳時間復雜度為O(1)，最壞則為O(n)。但就查找的平均效率來說是要高于TreeMap。

TreeMap?用key對象為關鍵值存放在RBTree(紅黑樹)中。其get(Object?key)方法的平均時間復雜度為O(logn)。

References?Resource

總結

以上是生活随笔為你收集整理的移除集合效率高还是add高_效率比较--集合的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。