Java ArrayList源码剖析

   <h2>总体介绍</h2>    <p><em>ArrayList</em>实现了<em>List</em>接口，是顺序容器，即元素存放的数据与放进去的顺序相同，允许放入<code>null</code>元素，底层通过<strong>数组实现</strong>。除该类未实现同步外，其余跟<em>Vector</em>大致相同。每个<em>ArrayList</em>都有一个容量（capacity），表示底层数组的实际大小，容器内存储元素的个数不能多于当前容量。当向容器中添加元素时，如果容量不足，容器会自动增大底层数组的大小。前面已经提过，Java泛型只是编译器提供的语法糖，所以这里的数组是一个Object数组，以便能够容纳任何类型的对象。</p>    <p><img alt="Java ArrayList源码剖析" src="https://simg.open-open.com/show/966f23b07473fba12049e21ec51fdb6a.png" width="800" height="245"></p>    <p>size(), isEmpty(), get(), set()方法均能在常数时间内完成，add()方法的时间开销跟插入位置有关，addAll()方法的时间开销跟添加元素的个数成正比。其余方法大都是线性时间。</p>    <p>为追求效率，ArrayList没有实现同步（synchronized），如果需要多个线程并发访问，用户可以手动同步，也可使用Vector替代。</p>    <h2>方法剖析</h2>    <h3>set()</h3>    <p>既然底层是一个数组<em>ArrayList</em>的<code>set()</code>方法也就变得非常简单，直接对数组的指定位置赋值即可。</p>    <pre>  <code class="language-java">public E set(int index, E element) {      rangeCheck(index);//下标越界检查      E oldValue = elementData(index);      elementData[index] = element;//赋值到指定位置，复制的仅仅是引用      return oldValue;  }</code></pre>    <h3>get()</h3>    <p><code>get()</code>方法同样很简单，唯一要注意的是由于底层数组是Object[]，得到元素后需要进行类型转换。</p>    <pre>  <code class="language-java">public E get(int index) {      rangeCheck(index);      return (E) elementData[index];//注意类型转换  }</code></pre>    <h3>add()</h3>    <p>跟C++ 的<em>vector</em>不同，<em>ArrayList</em>没有<code>bush_back()</code>方法，对应的方法是<code>add(E e)</code>，<em>ArrayList</em>也没有<code>insert()</code>方法，对应的方法是<code>add(int index, E e)</code>。这两个方法都是向容器中添加新元素，这可能会导致<em>capacity</em>不足，因此在添加元素之前，都需要进行剩余空间检查，如果需要则自动扩容。扩容操作最终是通过<code>grow()</code>方法完成的。</p>    <pre>  <code class="language-java">private void grow(int minCapacity) {      int oldCapacity = elementData.length;      int newCapacity = oldCapacity + (oldCapacity >> 1);//原来的3倍      if (newCapacity - minCapacity < 0)          newCapacity = minCapacity;      if (newCapacity - MAX_ARRAY_SIZE > 0)          newCapacity = hugeCapacity(minCapacity);      elementData = Arrays.copyOf(elementData, newCapacity);//扩展空间并复制  }</code></pre>    <p>由于Java GC自动管理了内存，这里也就不需要考虑源数组释放的问题。</p>    <p><img alt="Java ArrayList源码剖析" src="https://simg.open-open.com/show/7080cbd74808bf624ca5fa34ab76d8cd.png" width="850" height="458"></p>    <p>空间的问题解决后，插入过程就显得非常简单。</p>    <p><img alt="Java ArrayList源码剖析" src="https://simg.open-open.com/show/5afb9088190cb7581455ccdeecca352f.png" width="804" height="806"></p>    <p><code>add(int index, E e)</code>需要先对元素进行移动，然后完成插入操作，也就意味着该方法有着线性的时间复杂度。</p>    <h3>addAll()</h3>    <p><code>addAll()</code>方法能够一次添加多个元素，根据位置不同也有两个把本，一个是在末尾添加的<code>addAll(Collection<? extends E> c)</code>方法，一个是从指定位置开始插入的<code>addAll(int index, Collection<? extends E> c)</code>方法。跟<code>add()</code>方法类似，在插入之前也需要进行空间检查，如果需要则自动扩容；如果从指定位置插入，也会存在移动元素的情况。<br> <code>addAll()</code>的时间复杂度不仅跟插入元素的多少有关，也跟插入的位置相关。</p>    <h3>remove()</h3>    <p><code>remove()</code>方法也有两个版本，一个是<code>remove(int index)</code>删除指定位置的元素，另一个是<code>remove(Object o)</code>删除第一个满足<code>o.equals(elementData[index])</code>的元素。删除操作是<code>add()</code>操作的逆过程，需要将删除点之后的元素向前移动一个位置。需要注意的是为了让GC起作用，必须显式的为最后一个位置赋<code>null</code>值。</p>    <pre>  <code class="language-java">public E remove(int index) {      rangeCheck(index);      modCount++;      E oldValue = elementData(index);      int numMoved = size - index - 1;      if (numMoved > 0)          System.arraycopy(elementData, index+1, elementData, index, numMoved);      elementData[--size] = null; //清除该位置的引用，让GC起作用      return oldValue;  }</code></pre>    <p>关于Java GC这里需要特别说明一下，<strong>有了垃圾收集器并不意味着一定不会有内存泄漏</strong>。对象能否被GC的依据是是否还有引用指向它，上面代码中如果不手动赋<code>null</code>值，除非对应的位置被其他元素覆盖，否则原来的对象就一直不会被回收。</p>    <p>来源：https://github.com/CarpenterLee/JCFInternals/blob/master/markdown/2-ArrayList.md</p>