ArrayList源码浅析（一）（jdk1.8）

我将会通过源码和图片，把ArrayList的结构描述清楚。

---

构造方法

ArrayList总共有三个构造方法，这里就只看最简单的那个。

 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 transient Object[] elementData;
 // 中间代码省略
 public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
 }

从上述源码，我们可以得出以下几个结论
1. ArrayList是一个对象数组，elementData。
2. new ArrayList()的时候会赋值一个空的数组给elementData，如果要指定初始容量，可以使用另一个带指定初始容量的构造方法 public ArrayList(int initialCapacity），这里不做过多的介绍。
那么问题来了，ArrayList什么时候去初始化数组大小的？

---

Add

上面的问题，答案其实就在add方法里。

  1 public boolean add(E e) {
  2      ensureCapacityInternal(size + 1); 
  3      elementData[size++] = e;
  4      return true;
  5  }
   // 中间代码省略
  6 private void ensureCapacityInternal(int minCapacity) {
  7      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  8          minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  9      }
  10      ensureExplicitCapacity(minCapacity);
  11 }

  12 private void ensureExplicitCapacity(int minCapacity) {
  13      modCount++;
  14      // overflow-conscious code
  15      if (minCapacity - elementData.length > 0)
  16           grow(minCapacity);
  17 }
  // 中间代码省略
  18 private void grow(int minCapacity) {
  19      // overflow-conscious code
  20      int oldCapacity = elementData.length;
  21      int newCapacity = oldCapacity + (oldCapacity >> 1);
  22      if (newCapacity - minCapacity < 0)
  23          newCapacity = minCapacity;
  24      if (newCapacity - MAX_ARRAY_SIZE > 0)
  25          newCapacity = hugeCapacity(minCapacity);
  26      // minCapacity is usually close to size, so this is a win:
  27      elementData = Arrays.copyOf(elementData, newCapacity);
  28  }

  29 private static int hugeCapacity(int minCapacity) {
  30      if (minCapacity < 0) // overflow
  31          throw new OutOfMemoryError();
  32      return (minCapacity > MAX_ARRAY_SIZE) ?
  33          Integer.MAX_VALUE :
  34          MAX_ARRAY_SIZE;
  35  }    

上面贴的代码，基本上把ArrayList的add过程描述清楚了。我一点点来分析。
假设第一次add元素且初始化用的是ArrayList的无参构造函数（后面的//注释代表上述代码的行数）
3. 首先会进入ensureCapacityInternal方法，此时size = 0 // 2
4. 因为无参构造函数初始化的，所以默认用的DEFAULTCAPACITY_EMPTY_ELEMENTDATA数组。// 7
5. 因为DEFAULT_CAPACITY>minCapacity,所以minCapacity = DEFAULT_CAPACITY，而DEFAULT_CAPACITY的值默认为10。 // 8
6. 随后进入ensureExplicitCapacity方法 //10
7. 此时elementData.length = 0，所以if条件为真（换种理解就是每次add，如果当前add的序号小于等于数组长度，就没必要重新扩容，即不会进入grow方法） //15
8. 进入grow方法 // 16
9. grow方法主要功能就是用来确认最终的数组容量大小并完成数组的复制。新容量newCapacity=oldCapacity+oldCapacity/2。容量确认后就是数组的复制操作了。
10. 最后，将元素添加到数组的末尾，size+1,完成整个add过程。

add方法总结
1. 初始容量在第一次添加元素的时候确定，默认为10。
2. 实际应用中，如果能确定元素个数，请直接填写和元素个数一样的容量大小。这样数组就不用去扩容了，相当于空间换时间，但能提升多少效率我就不得而知了。

---

Get

get方法就相当简单了，就是单纯的数组值获取，因为是数组的缘故，所以ArrayList的get效率很高，适合大量查询的场景。
源码如下。

public E get(int index) {
        rangeCheck(index);
        return elementData(index);
 }

 private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 }

E elementData(int index) {
        return (E) elementData[index];
}

---

由于时间关系，两个remove方法，将在下一篇介绍,另外后续想研究下高并发下的ArrayList会有什么问题。