疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

Java集合类之ArrayList和LinkedList性能比较


 

 
关于ArrayList和LinkedList这两个集合类的性能,网上很多文章表示:ArrayList的插入性能要比LinkedList差。今天突然想测试下,这个结论是否准确。
 
编写了如下代码:
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
 
public class Demo {
 
public static void main(String[] args) {
int count = 1000000; //循环次数
System.out.println("循环 " + count + " 次,ArrayList LinkedList 尾部插入性能测试:");
List<Integer> lst = new ArrayList<Integer>();
List<Integer> link = new LinkedList<Integer>();
new Demo().testInsert(lst, count);
new Demo().testInsert(link, count);
int index = 0; //插入位置
count = 90000;
System.out.println(" 循环 " + count + " 次,ArrayList LinkedList 指定位置插入性能测试:");
 
lst = new ArrayList<Integer>();
link = new LinkedList<Integer>();
new Demo().testInsertForIndex(lst, count, index);
new Demo().testInsertForIndex(link, count, index);
}
/**
* 向默认位置插入元素
* @param count 循环次数
*/
public void testInsert(List<Integer> lst, int count){
long bTime = System.currentTimeMillis();
for(int i=0; i<count; i++){
lst.add(1);
}
long eTime = System.currentTimeMillis();
System.out.println(lst.getClass().getName() + " 共耗时:" + (eTime - bTime) + " ms");
}
/**
* 向指定位置插入元素
* @param count 循环次数
* @param index 插入位置
*/
public void testInsertForIndex(List<Integer> lst, int count, int index){
long bTime = System.currentTimeMillis();
for(int i=0; i<count; i++){
lst.add(index,1);
}
long eTime = System.currentTimeMillis();
System.out.println(lst.getClass().getName() + " 共耗时:" + (eTime - bTime) + " ms");
}
}
执行结果如下:
循环 1000000 次,ArrayList LinkedList 尾部插入性能测试:
java.util.ArrayList 共耗时:56 ms
java.util.LinkedList 共耗时:192 ms
 
循环 90000 次,ArrayList LinkedList 指定位置插入性能测试:
java.util.ArrayList 共耗时:3885 ms
java.util.LinkedList 共耗时:5 ms
 
 
根据结果发现,在都使用add(E e)函数添加元素时,LinkedList的性能反而不如ArrayList。那这到底是为何?
我们来看看具体的源码:
ArrayList的add(E e)函数
public boolean add(E e) {
    ensureCapacity(size + 1);  //数组扩容
    elementData[size++] = e;
    return true;
}
第一行代码:用于给ArrayList中的元素数组进行扩容,且先判断是否需要扩容,如果需要则扩容算法为:目前容量*3/2+1
第二行代码:向元素数组的尾部追加新元素
 
LinkedList的add(E e)函数
public boolean add(E e) {
    addBefore(e, header);
     return true;
}
 
private Entry<E> addBefore(E e, Entry<E> entry) {
    Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
    newEntry.previous.next = newEntry;
    newEntry.next.previous = newEntry;
    size++;
    modCount++;
    return newEntry;
}
addBefore函数首先创建一个新的Entry节点,并插入到链接表,然后分别调整新节点的前一节点的向后引用和后一节点的向前引用。
 
看了这两段代码前面的结论也就有了答案。
 
我们再来看看为什么向指定位置插入时,性能差距如此之大?
ArrayList的add(int index, E element)函数
public void add(int index, E element) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
 
    ensureCapacity(size+1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,size - index);
    elementData[index] = element;
    size++;
}
此处可以看到每插入一个元素都会使用System.arraycopy进行数组的复制,可想而知这效率会有多低。
 
LinkedList的add(int index, E element)函数
public void add(int index, E element) {
    addBefore(element, (index==size ? header : entry(index)));
}
此处,依然调用了addBefore函数,性能与add(E e)没有差异。
 
总结:作为coder,每个细节都应该自己进行验证,不能人云亦云。