SDK提供了有序集合接口java.util.List的幾種實(shí)現，其中三種最為人們熟知的是Vector、ArrayList和LinkedList。有關(guān)這些List類(lèi)的性能差別是一個(gè)經(jīng)常被問(wèn)及的問(wèn)題。在這篇文章中，我要探討的就是LinkedList和Vector/ArrayList之間的性能差異。
為全面分析這些類(lèi)之間的性能差異，我們必須知道它們的實(shí)現方法。因此，接下來(lái)我首先從性能的角度出發(fā)，簡(jiǎn)要介紹這些類(lèi)的實(shí)現特點(diǎn)。
一、Vector和ArrayList的實(shí)現
Vector和ArrayList都帶有一個(gè)底層的Object[]數組，這個(gè)Object[]數組用來(lái)保存元素。通過(guò)索引訪(fǎng)問(wèn)元素時(shí)，只需簡(jiǎn)單地通過(guò)索引訪(fǎng)問(wèn)內部數組的元素： public Object get(int index)
{ // 首先檢查index是否合法...此處不顯示這部分代碼 return
elementData[index]; }
內部數組可以大于Vector/ArrayList對象擁有元素的數量，兩者的差值作為剩余空間，;便實(shí)現快速添加新元素。有了剩余空間，添加元素變得非常簡(jiǎn)單，只需把新的元素保存到內部數組中的一個(gè)空余的位置，然后為新的空余位置增加索引值： public boolean add(Object o)
{ ensureCapacity(size + 1); // 稍后介紹 elementData[size++] = o; return true;
// List.add(Object) 的返回值 }
把元素插入集合中任意指定的位置(而不是集合的末尾)略微復雜一點(diǎn)：插入點(diǎn)之上的所有數組元素都必須向前移動(dòng)一個(gè)位置，然后才能進(jìn)行賦值： public void add(int index, Object element) {
// 首先檢查index是否合法...此處不顯示這部分代碼
ensureCapacity(size+1);
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
剩余空間被用光時(shí)，如果需要加入更多的元素，Vector/ArrayList對象必須用一個(gè)更大的新數組替換其內部Object[]數組，把所有的數組元素復制到新的數組。根據SDK版本的不同，新的數組要比原來(lái)的大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);
}
}
文章來(lái)源于領(lǐng)測軟件測試網(wǎng) http://kjueaiud.com/
