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.ltesting.net