Java数据结构（2）ArrayList

ArrayList

• ArrayList 是一个数组队列，相当于 动态数组，与数组相比，它的容量能动态增长。
• 和Vector不同，ArrayList中的操作不是线程安全的！所以，建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或者CopyOnWriteArrayList。
• ArrayList包含了两个重要的对象：elementData 和 size。
  • elementData是"Object[]类型的数组"，它保存了添加到ArrayList中的元素。实际上，elementData是个动态数组，我们能通过构造函数 ArrayList(int initialCapacity)来执行它的初始容量为initialCapacity；如果通过不含参数的构造函数ArrayList()来创建ArrayList，则elementData的容量默认是10。elementData数组的大小会根据ArrayList容量的增长而动态的增长，具体的增长方式，请参考源码分析中的ensureCapacity()函数。
  • size 则是动态数组的实际大小。

ArrayList的使用优化

1. 上面说到的动态数组，就存在扩容的问题

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

看看ensureCapacity():

     public void ensureCapacity(int minCapacity) {
         // 将“修改统计数”+1
         modCount++;
         int oldCapacity = elementData.length;
         // 若当前容量不足以容纳当前的元素个数，设置 新的容量=“(原始容量x3)/2 + 1”
             Object oldData[] = elementData;
              int newCapacity = (oldCapacity * 3)/2 + 1;
              if (newCapacity < minCapacity)
                  newCapacity = minCapacity;
              elementData = Arrays.copyOf(elementData, newCapacity);
          }
      }

当然不同jdk版本写法略有不同，上面是1.6版本的，1.8版本的如下：

    private void grow(int minCapacity) {
        ...
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 结果都是一样的
        ...
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

2. 使用优化：
   由于初始化ArrayList,默认数组长度是10，如果是特别大的数据，可通过ensureCapacity(int length)初始化数组长度;

public static void main(String[] args){
        final int N = 10000000;
        Object obj = new Object();
        
        //没用调用ensureCapacity()方法初始化ArrayList对象
        ArrayList list = new ArrayList();
        long startTime = System.currentTimeMillis();
        for(int i=0;i<=N;i++){
            list.add(obj);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("没有调用ensureCapacity()方法所用时间：" + (endTime - startTime) + "ms");
        
        //调用ensureCapacity()方法初始化ArrayList对象
        list = new ArrayList();
        startTime = System.currentTimeMillis();
        list.ensureCapacity(N);//预先设置list的大小
        for(int i=0;i<=N;i++){
            list.add(obj);
        }
        endTime = System.currentTimeMillis();
        System.out.println("调用ensureCapacity()方法所用时间：" + (endTime - startTime) + "ms");
    }

运行结果：
没有调用ensureCapacity()方法所用时间：137ms
调用ensureCapacity()方法所用时间：78ms

补充一点：arraycopy本地方法是通过c的动态内存分配，创建动态数组，这点java没法做到
System.arraycopy(a, 0, newArray, 0, s);

public static native void arraycopy(Object src, int srcPos,Object dst, int dstPos, int length);