Java列表對象的性能分析和測試

　　Java列表對象的性能分析和測試   軟件測試

　　SDK提供了有序集合接口java.util.List的幾種實現，其中三種最為人們熟知的是Vector、ArrayList和LinkedList。有關這些List類的性能差別是一個經常被問及的問題。在這篇文章中，我要探討的就是LinkedList和Vector/ArrayList之間的性能差異。

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

　　一、Vector和ArrayList的實現

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

　　{ // 首先檢查index是否合法...此處不顯示這部分代碼 return

　　elementData[index]; }

　　內部數組可以大于Vector/ArrayList對象擁有元素的數量，兩者的差值作為剩余空間，;便實現快速添加新元素。有了剩余空間，添加元素變得非常簡單，只需把新的元素保存到內部數組中的一個空余的位置，然后為新的空余位置增加索引值： public boolean add(Object o)

　　{ ensureCapacity(size + 1); // 稍后介紹 elementData[size++] = o; return true;

　　// List.add(Object) 的返回值 }

　　把元素插入集合中任意指定的位置(而不是集合的末尾)略微復雜一點：插入點之上的所有數組元素都必須向前移動一個位置，然后才能進行賦值： 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對象必須用一個更大的新數組替換其內部Object[]數組，把所有的數組元素復制到新的數組。根據SDK版本的不同，新的數組要比原來的大50%或者100%(下面顯示的代碼把數組擴大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);

　　}

　　}

原文轉自：http://www.anti-gravitydesign.com