JAVA容器效率深度分析List

本文中的测试代码来源于《think in java》第四版

附件中有测试代码

1、各种List的各种操作的耗时

size：每一个list的元素数量，从10到10W

 

操作：add增加到list末端，get随机访问，set修改某个元素值，insert在list中间插入（代码中只是插入到了第五个元素，放大了随机插入的操作时间），rmMiddle从list中间删除元素（代码中是删除了第五个元素，放大了从list.size()/2的操作时间，rmLast从list末端删除，rmFirst从list首部删除

 

操作时间：是指每一次操作所用的时间，单位纳秒

 

环境：64bit JDK7

 

ArrayList和Vector都是基于数组实现的，区别就是Vector是同步的，以下将统称为“数组list”

2、分析

2.1 add操作，数组和链表旗鼓相当

首先，当list仅有10个元素的add耗时，要大于100/1k/1w/10w元素的add耗时，这里可能是因为“JIT的热点优化”导致。可以通过增加循环次数来验证，在我的机器上：“往一个list增加10个元素”，循环13W次时，每次的操作耗时降到 2位数

其次，比较数组list和链表list，向末端增加时，操作耗时几乎不随着list元素数变化而变化。

 

数组元素add时的扩容动作最终调用的方法：

    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

 无疑，native方法System.arraycopy的效率是高的，几乎不随list.size()变化而变化。

 

因为System.arraycopy的高效，在这里不得不提到一点，链表在add操作时比数组list要复杂的多（LinkedList是双向链表），当list.size()数量超过百万时，链表的add可能就会比数组add要慢，这一点有待验证。

 

2.2get随机访问，数组完胜

数组list的get耗时，在list.size()增长时，无变化

链表list的get耗时，在list.size()增长时，性能下降。

 

值得一提的就是jdk5中遍历操作的foreach写法，如下：

 

   for (String x : list) { 
            System.out.println(x); 
        } 

此种写法是基于集合的iterator迭代器，只要是实现了Iterable接口的类，均可使用此种写法。数组的迭代器访问，本质还是基于数组的随机访问，和get随机访问比，将无变化。而链表的迭代器访问，与get随机访问相比，性能将有大幅度提升，应该和数组的随机访问差不多，而且不会因为list.size()的增长而导致系能下降

 

2.3set修改，数组完胜

修改操作，数组list不随size增大而导致效率降低，链表则随着list.size()增大导致效率降低，看链表set源码

 

    public E set(int index, E element) {
        //查找Entry
        Entry<E> e = entry(index);
        E oldVal = e.element;
        e.element = element;
        return oldVal;
    }

    private Entry<E> entry(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+size);
        Entry<E> e = header;//从header开始
        //index小于size一半，则向后遍历，否则向前遍历
        if (index < (size >> 1)) {
            for (int i = 0; i <= index; i++)
                e = e.next;
        } else {
            for (int i = size; i > index; i--)
                e = e.previous;
        }
        return e;
    }

 

 

也就是说，每次set时候，都会从header向前或向后遍历链表。由此可以想到，修改第"list.size/2"个元素，则是代价最大的修改。

 

2.4 insert插入，链表完胜数组

1）无论链表还是数组，insert操作的效率将会随着list.size()的增大而降低

2）数组需要将insert元素，以后的元素，整体后移动

    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++;
    }

 

2.5 remove删除，链表小胜

    public E remove(int index) {
	RangeCheck(index);

	modCount++;
	E oldValue = (E) elementData[index];

	int numMoved = size - index - 1;
	if (numMoved > 0)
	    System.arraycopy(elementData, index+1, elementData, index,
			     numMoved);
	elementData[--size] = null; // Let gc do its work

	return oldValue;
    }

 数组list每次删除都有System.arraycopy操作，因此效率最低的应该是remove first删除list中的第一个元素。耗时最少的删除是remove last删除最后一个元素。

链表则无论是第一个删除、中间删除、末尾删除，都无需考虑效率问题，而且，删除效率不随list.size()增大而降低

如果是从末尾删除，数组甚至比链表要快。

 

结论：List中首选Arraylist,基于数组实现list平均性能是最好的，如果有大量的insert或者从首部/中部删除元素的操作，则应该选择LinkedList

其实LinkedList作为队列、堆栈来操作，无疑，应该是首选，效率够高