Java列表對象的性能分析

2019-11-17 06:34:19

字體：大中小

來源：轉載

供稿：網(wǎng)友

　　為全面分析這些類之間的性能差異，我們必須知道它們的實現(xiàn)方法。因此，接下來我首先從性能的角度出發(fā)，簡要介紹這些類的實現(xiàn)特點。

　　一、Vector和ArrayList的實現(xiàn)

　　Vector和ArrayList都帶有一個底層的Object[]數(shù)組，這個Object[]數(shù)組用來保存元素。通過索引訪問元素時，只需簡單地通過索引訪問內部數(shù)組的元素：

public Object get(int index)
{ //首先檢查index是否合法...此處不顯示這部分代碼 return
elementData[index]; }
　　內部數(shù)組可以大于Vector/ArrayList對象擁有元素的數(shù)量，兩者的差值作為剩余空間，以便實現(xiàn)快速添加新元素。有了剩余空間，添加元素變得非常簡單，只需把新的元素保存到內部數(shù)組中的一個空余的位置，然后為新的空余位置增加索引值：

public boolean add(Object o)
{ ensureCapacity(size + 1); //稍后介紹 elementData[size++] = o; return true;
//List.add(Object) 的返回值 }
　　把元素插入集合中任意指定的位置（而不是集合的末尾）略微復雜一點：插入點之上的所有數(shù)組元素都必須向前移動一個位置，然后才能進行賦值：

public void add(int index, Object element) {
　//首先檢查index是否合法...此處不顯示這部分代碼
　ensureCapacity(size+1);
　System.arraycopy(elementData, index, elementData, index + 1,size - index);
　elementData[index] = element;
　size++;
}
　　剩余空間被用光時，假如需要加入更多的元素，Vector/ArrayList對象必須用一個更大的新數(shù)組替換其內部Object[]數(shù)組，把所有的數(shù)組元素復制到新的數(shù)組。根據(jù)SDK版本的不同，新的數(shù)組要比原來的大50%或者100%（下面顯示的代碼把數(shù)組擴大100%）：

public void ensureCapacity(int minCapacity) {
　int oldCapacity = elementData.length;
　if (minCapacity > oldCapacity) {
　　Object oldData[] = elementData;
　　int newCapacity = Math.max(oldCapacity * 2, minCapacity);
　　elementData = new Object[newCapacity];
　　System.arraycopy(oldData, 0, elementData, 0, size);
　}
}
　　Vector類和ArrayList類的主要不同之處在于同步。除了兩個只用于串行化的方法，沒有一個ArrayList的方法具有同步執(zhí)行的能力；相反，Vector的大多數(shù)方法具有同步能力，或直接或間接。因此，Vector是線程安全的，但ArrayList不是。這使得ArrayList要比Vector快速。對于一些最新的JVM，兩個類在速度上的差異可以忽略不計：嚴格地說，對于這些JVM，這兩個類在速度上的差異小于比較這些類性能的測試所顯示的時間差異。

　　通過索引訪問和更新元素時，Vector和ArrayList的實現(xiàn)有著卓越的性能，因為不存在除范圍檢查之外的其他開銷。除非內部數(shù)組空間耗盡必須進行擴展，否則，向列表的末尾添加元素或者從列表的末尾刪除元素時，都同樣有著優(yōu)秀的性能。插入元素和刪除元素總是要進行數(shù)組復制（當數(shù)組先必須進行擴展時，需要兩次復制）。被復制元素的數(shù)量和[size-index]成比例，即和插入/刪除點到集合中最后索引位置之間的距離成比例。對于插入操作，把元素插入到集合最前面（索引0）時性能最差，插入到集合最后面時（最后一個現(xiàn)有元素之后）時性能最好。隨著集合規(guī)模的增大，數(shù)組復制的開銷也迅速增加，因為每次插入操作必須復制的元素數(shù)量增加了。

　　二、LinkedList的實現(xiàn)

　　LinkedList通過一個雙向鏈接的節(jié)點列表實現(xiàn)。要通過索引訪問元素，你必須查找所有節(jié)點，直至找到目標節(jié)點：

public Object get(intindex) {
　//首先檢查index是否合法...此處不顯示這部分代碼
　Entry e = header; //開始節(jié)點
　//向前或者向后查找，具體由哪一個方向距離較
　//近決定
　if (index < size/2) {
　　for (int i = 0; i <= index; i++)
　　　e = e.next;
　} else {
　　for (int i = size; i > index; i--)
　　　e = e.PRevious;
　}
　return e;
}
　　把元素插入列表很簡單：找到指定索引的節(jié)點，然后緊靠該節(jié)點之前插入一個新節(jié)點：

public void add(int index, Object element) {
　//首先檢查index是否合法...此處不顯示這部分代碼
　Entry e = header; //starting node
　//向前或者向后查找，具體由哪一個方向距離較
　//近決定
　if (index < size/2) {
　　for (int i = 0; i <= index; i++)
　　　e = e.next;
　} else {
　　for (int i = size; i > index; i--)
　　　e = e.previous;
　}
　Entry newEntry = new Entry(element, e, e.previous);
　newEntry.previous.next = newEntry;
　newEntry.next.previous = newEntry;
　size++;
}
　　線程安全的LinkedList和其他集合

　　假如要從java SDK得到一個線程安全的LinkedList，你可以利用一個同步封裝器從Collections.synchronizedList(List)得到一個。

上一篇：Java的“對象思想”學習筆記[二]

下一篇：通過java提供的URL類包讀取網(wǎng)上的文件