社会很单纯复杂的是人心 發表於 2025-6-29 10:51:00

4.Java SDK源码分析系列笔记-ArrayList

<p></p><div class="toc"><div class="toc-container-header">目录</div><ul><li>1. 是什么</li><li>2. 如何使用</li><li>3. 原理分析<ul><li>3.1. uml</li><li>3.2. 构造方法</li><li>3.3. add方法<ul><li>3.3.1. 确保容量足够容纳新的元素</li><li>3.3.2. 把元素放入数组最后一个位置</li></ul></li><li>3.4. remove方法【按下标删除元素】<ul><li>3.4.1. 把数组index位置之后的数据往前挪</li><li>3.4.2. 更新size【数组不缩容】</li></ul></li><li>3.5. remove方法【按元素内容删除】<ul><li>3.5.1. 首先找到要删除的元素的下标</li><li>3.5.2. 把数组index位置之后的数据往前挪</li><li>3.5.3. 更新size【数组不缩容】</li></ul></li></ul></li><li>4. ConcurrentModificationException<ul><li>4.1. 原因分析</li><li>4.2. 解决</li></ul></li></ul></div><p></p>
<h2 id="1-是什么">1. 是什么</h2>
<p>底层由数组实现的，可扩容的顺序表<br>
有序、可以重复</p>
<h2 id="2-如何使用">2. 如何使用</h2>
<pre><code class="language-java">public class ArrayListTest
{
    public static void main(String[] args)
    {
      ArrayList&lt;String&gt; list = new ArrayList&lt;&gt;();
      list.add("1");
      list.add("2");

      System.out.println(list);
      
      list.remove(0);
      list.remove("2");



    }
}
</code></pre>
<h2 id="3-原理分析">3. 原理分析</h2>
<h3 id="31-uml">3.1. uml</h3>
<p><img src="https://raw.githubusercontent.com/TDoct/images/master/img/20200122170737.png"><br>
可以看出ArrayList是个List、可克隆、可序列化、可以使用下标访问</p>
<h3 id="32-构造方法">3.2. 构造方法</h3>
<p>使用object数组，并且初始化长度为0</p>
<pre><code class="language-java">public class ArrayList&lt;E&gt; extends AbstractList&lt;E&gt;
      implements List&lt;E&gt;, RandomAccess, Cloneable, java.io.Serializable
{
    //如果使用默认的无参构造初始容量为0，第一次扩容时容量为10
    private static final int DEFAULT_CAPACITY = 10;

    //没有元素时使用空数组，两者区别是啥？
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //List底层使用Object数组实现
    transient Object[] elementData;

    //Object数组中实际使用的大小
    private int size;

    public ArrayList() {
      //默认空数组
      this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
}
</code></pre>
<h3 id="33-add方法">3.3. add方法</h3>
<ul>
<li>不扩容O（1），扩容O（N）</li>
</ul>
<pre><code class="language-java">public boolean add(E e) {
        //确保容量足够
    ensureCapacityInternal(size + 1);// Increments modCount!!
    //在默认赋值
    elementData = e;
    return true;
}

</code></pre>
<h4 id="331-确保容量足够容纳新的元素">3.3.1. 确保容量足够容纳新的元素</h4>
<pre><code class="language-java">private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //使用默认的无参构造方法创建的容量为0，那么第一次扩容为10个
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
      return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
        //减法比较大小防止溢出
    if (minCapacity - elementData.length &gt; 0)
            //需要扩容
      grow(minCapacity);
}


private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    //新长度=原长度*1.5
    int newCapacity = oldCapacity + (oldCapacity &gt;&gt; 1);
    //新长度&lt;最小需要的长度，那么取最小需要的长度
    if (newCapacity - minCapacity &lt; 0)
      newCapacity = minCapacity;
   
    //新长度比数组最大限制长度还大private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
    if (newCapacity - MAX_ARRAY_SIZE &gt; 0)
            //转而使用最小需要的长度
      newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    //复制原数组的元素到新数组中
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
        //最小需要的长度也溢出了，OOM
    if (minCapacity &lt; 0) // overflow
      throw new OutOfMemoryError();
    //最小需要的长度比数组最大限制长度大则使用Integer.MAX_VALUE，否则使用数组最大限制长度
    return (minCapacity &gt; MAX_ARRAY_SIZE) ?
      Integer.MAX_VALUE :
      MAX_ARRAY_SIZE;
}
</code></pre>
<h4 id="332-把元素放入数组最后一个位置">3.3.2. 把元素放入数组最后一个位置</h4>
<pre><code class="language-java">//没啥好说的，赋值然后下标+1
elementData = e;
</code></pre>
<h3 id="34-remove方法按下标删除元素">3.4. remove方法【按下标删除元素】</h3>
<ul>
<li>O（N）</li>
</ul>
<pre><code class="language-java">public E remove(int index) {
        //防止下标越界
    rangeCheck(index);

    modCount++;
    //保存要删除的数以便返回
    E oldValue = elementData(index);

        //需要移动的个数
    int numMoved = size - index - 1;
    if (numMoved &gt; 0)
            //后面的往前移
      System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
   //其实数组大小没有变化。当然size属性必须更新的
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}
</code></pre>
<h4 id="341-把数组index位置之后的数据往前挪">3.4.1. 把数组index位置之后的数据往前挪</h4>
<pre><code class="language-java">//计算index后面需要移动的个数
int numMoved = size - index - 1;
if (numMoved &gt; 0)
        //后面的往前移
    System.arraycopy(elementData, index+1, elementData, index,
                     numMoved);
</code></pre>
<h4 id="342-更新size数组不缩容">3.4.2. 更新size【数组不缩容】</h4>
<pre><code class="language-java"> //其实数组大小没有变化。当然size属性必须更新的
elementData[--size] = null; // clear to let GC do its work
</code></pre>
<h3 id="35-remove方法按元素内容删除">3.5. remove方法【按元素内容删除】</h3>
<ul>
<li>O（N）</li>
</ul>
<pre><code class="language-java">public boolean remove(Object o) {
    //为null
    if (o == null) {
            //找到下标
      for (int index = 0; index &lt; size; index++)
            //==null判断
            if (elementData == null) {
                    //删除该下标的元素
                fastRemove(index);
                return true;
            }
    } else {
      for (int index = 0; index &lt; size; index++)
            //equals判断
            if (o.equals(elementData)) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

</code></pre>
<h4 id="351-首先找到要删除的元素的下标">3.5.1. 首先找到要删除的元素的下标</h4>
<pre><code class="language-java">for (int index = 0; index &lt; size; index++)
{
//...
}
</code></pre>
<p>如上无非就时遍历查找，效率O（N），然后按照下标删除，如下</p>
<ul>
<li>fastRemove</li>
</ul>
<pre><code class="language-java"> private void fastRemove(int index) {
    modCount++;
    //计算移动元素的个数
    int numMoved = size - index - 1;
    if (numMoved &gt; 0)
            //复制到前面
      System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
        //赋为null，并且size--
    elementData[--size] = null; // clear to let GC do its work
}
</code></pre>
<p>这段代码同上面的remove方法【按下标删除元素】的逻辑</p>
<h4 id="352-把数组index位置之后的数据往前挪">3.5.2. 把数组index位置之后的数据往前挪</h4>
<pre><code class="language-java">//计算移动元素的个数
int numMoved = size - index - 1;
if (numMoved &gt; 0)
        //复制到前面
    System.arraycopy(elementData, index+1, elementData, index,
                     numMoved);
</code></pre>
<h4 id="353-更新size数组不缩容">3.5.3. 更新size【数组不缩容】</h4>
<pre><code class="language-java">//赋为null，并且size--
elementData[--size] = null; // clear to let GC do its work
</code></pre>
<h2 id="4-concurrentmodificationexception">4. ConcurrentModificationException</h2>
<p>参考：fail-fast.md</p>
<pre><code class="language-java">public class ConcurrentModificationExceptionTest
{
    public static void main(String[] args)
    {
      List&lt;String&gt; stringList = new ArrayList&lt;&gt;();
      for (int i = 0; i &lt; 1000; i++)
      {
            stringList.add(String.valueOf(i));
      }

      for (String s : stringList)
      {
            stringList.remove(s);//java.util.ConcurrentModificationException
      }
    }
}
</code></pre>
<p>如上的代码运行过程中会抛出ConcurrentModificationException异常<br>
<img src="https://raw.githubusercontent.com/TDoct/images/master/img/20200130164940.png"></p>
<h3 id="41-原因分析">4.1. 原因分析</h3>
<p>遍历时（get）执行删除操作（remove）会抛出这个异常，这叫做fast-fail机制<br>
这是modCount和expectedCount不相等导致的</p>
<h3 id="42-解决">4.2. 解决</h3>
<p>使用fail-safe的JUC包下的CopyOnWriteArrayList</p><br><br>
来源：https://www.cnblogs.com/ThinkerQAQ/p/18955861
頁: [1]
查看完整版本: 4.Java SDK源码分析系列笔记-ArrayList