浅析JDK1.7 ArrayList源码。

写在开篇

ArrayList源码相比我们之前看过的Map系列的源码要简单一些，所以接下来我们按照原来的套路，简单分析一下ArrayList的源码吧。

类的继承关系

ArrayList继承AbstractList抽象类，实现了List（规定了List的操作规范）、RandomAccess（可随机访问）、Cloneable（可拷贝）、Serializable（可序列化）这几个接口。

1
2
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

成员变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
    * 使用默认构造方法创建数组时的大小
    */
   private static final int DEFAULT_CAPACITY = 10;

   /**
    * 标识 elementData 使用默认构造方法创建
    */
   private static final Object[] EMPTY_ELEMENTDATA = {};

   /**
    * 元素数组
    */
   private transient Object[] elementData;

   /**
    * 实际数组大小
    */
   private int size;

构造方法

ArrayList中有三个构造方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
    * 给定参数初始化数组的大小
    */
   public ArrayList(int initialCapacity) {
       super();
       if (initialCapacity < 0)
           throw new IllegalArgumentException("Illegal Capacity: "+
                                              initialCapacity);
       this.elementData = new Object[initialCapacity];
   }

   /**
    * 默认初始化一个空数组
    */
   public ArrayList() {
       super();
       this.elementData = EMPTY_ELEMENTDATA;
   }

   /**
    * 以实现了Collection接口的集合类，来初始化elementData
    */
   public ArrayList(Collection<? extends E> c) {
       elementData = c.toArray();
       size = elementData.length;
       
       if (elementData.getClass() != Object[].class)
           elementData = Arrays.copyOf(elementData, size, Object[].class);
   }

List接口的实现

add()

ArrayList中有两个add方法，第一个是默认在下标为size+1的位置添加元素。

1
2
3
4
5
6
7
public boolean add(E e) {
	// 扩容检查
       ensureCapacityInternal(size + 1);  
       // 数组末尾添加元素
       elementData[size++] = e;	
       return true;
   }

另一个add()则是在指定位置添加元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1); 
        /**
         * 将旧数组拷贝到一个新数组中
         * @param elementData 被复制的原数组 
         * @param index 被复制数组的第几个元素开始复制
         * @param elementData 复制的目标数组
         * @param index + 1 从目标数组index + 1位置开始粘贴
         * @param size - index 复制的元素个数
         */
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        // 将新元素赋给该下标
        elementData[index] = element;
        size++;
    }

扩容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
private void ensureCapacityInternal(int minCapacity) {
	// 是否为空数组
       if (elementData == EMPTY_ELEMENTDATA) {
           minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
       }
	
       ensureExplicitCapacity(minCapacity);
   }

   private void ensureExplicitCapacity(int minCapacity) {
       modCount++; // 增加数组的操作次数（其为AbstractList的成员变量）
	// 如果需要的最小容量比elementData数组长度小，则扩容
       if (minCapacity - elementData.length > 0)
           grow(minCapacity);
   }
   
   private void grow(int minCapacity) {
       int oldCapacity = elementData.length;
       // 新容量为旧容量的3/2
       int newCapacity = oldCapacity + (oldCapacity >> 1);
       // 如果新容量还是小于扩容需要的最小容量，则将新容量调整为扩容需要的最小容量
       if (newCapacity - minCapacity < 0)
           newCapacity = minCapacity;
       // 新容量不超过Integer.MAX_VALUE-8
       if (newCapacity - MAX_ARRAY_SIZE > 0)
           newCapacity = hugeCapacity(minCapacity);

       elementData = Arrays.copyOf(elementData, newCapacity);
   }

set()

1
2
3
4
5
6
7
public E set(int index, E element) {
       rangeCheck(index); // 检查下标

       E oldValue = elementData(index);
       elementData[index] = element; // 将element赋值为指定下标
       return oldValue;
   }

get()

1
2
3
4
5
public E get(int index) {
       rangeCheck(index); // 检查下标

       return elementData(index); // 返回指定下标的元素
   }

remove()

同样地，有两个remove()方法。一个是删除下标为index的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public E remove(int index) {
       rangeCheck(index); // 检查下标

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

       int numMoved = size - index - 1; // 需要移动的个数
       if (numMoved > 0)
       	// 将下标为index+1后的元素向前移动一位
           System.arraycopy(elementData, index+1, elementData, index,
                            numMoved);
       // 将下标为size的元素置为空，同时将size-1
       elementData[--size] = null; 

       return oldValue;
   }

另一个是删除数组中相同的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public boolean remove(Object o) {
       if (o == null) { // 删除数组中的空元素
           for (int index = 0; index < size; index++)
               if (elementData[index] == null) {
                   fastRemove(index);
                   return true;
               }
       } else { // 输出数组中和o相同的元素
           for (int index = 0; index < size; index++)
               if (o.equals(elementData[index])) {
                   fastRemove(index);
                   return true;
               }
       }
       return false;
   }

   // 与上面讲的删除remove()过程相似
   private void fastRemove(int index) {
       modCount++;
       int numMoved = size - index - 1;
       if (numMoved > 0)
           System.arraycopy(elementData, index+1, elementData, index,
                            numMoved);
       elementData[--size] = null; 
   }

为什么是线程不安全的

主要有两个线程不安全的隐患，都出现在下面这段代码中：

1
2
3
4
5
6
7
public boolean add(E e) {
	// 扩容检查
       ensureCapacityInternal(size + 1);  
       // 数组末尾添加元素
       elementData[size++] = e;	
       return true;
   }

扩容检查时

假设现在有A、B两个线程在对数组进行插入元素操作，此时size=9（ArrayList 数组大小为默认的10）。

  1. 线程 A 进入add()，获取到size为9，调用ensureCapacityInternal()后判断不需要扩容，时间片消耗完，线程A挂起。
  2. 线程 B 开始执行，调用ensureCapacityInternal()后发现也不需要扩容。于是插入元素，且size自增1（size=10）。
  3. 线程 A 接着执行，尝试在下标为10的位置插入元素，此时就会抛出ArrayIndexOutOfBoundsException。

向数组末尾添加元素时

同样现在有两个线程A、B在对数组进行插入元素操作，size=0。

  1. 线程 A 执行完elementData[size] = e;后时间片耗尽，挂起。
  2. 线程 B 开始执行，由于size还是为0，所以在elementData[size] = e;时，会将线程 A 插入的元素覆盖掉。