ArrayList 底层原理和重点代码分析

ArrayList 相关类图

ArrayList 是 Java 中常用的一种数据结构，底层使用数组实现。

它的特点是支持动态扩容和随机访问，但是对于往中间插入或者删除，效率相对较低。

下面我们来详细讲解一下 ArrayList 的底层原理。

在创建 ArrayList 对象时，会先创建一个空数组，用来存放元素。

默认情况下，这个数组的大小为 10(DEFAULT_CAPACITY)，可以通过构造函数传入容量大小进行初始化。

 //默认大小的集合
 private static final int DEFAULT_CAPACITY = 10;
 
 //通过有参构造，创建一个指定大小的集合
 public ArrayList(int initialCapacity) {
   if (initialCapacity > 0) {
   this.elementData = new Object[initialCapacity];
   } else if (initialCapacity == 0) {
   this.elementData = EMPTY_ELEMENTDATA;
   } else {
   throw new IllegalArgumentException("Illegal Capacity: "+
   initialCapacity);
   }
 }

当需要添加元素时，如果当前数组已满，则会创建一个新的数组，将原数组的元素复制到新数组中，并将新元素添加到新数组的末尾。因此，ArrayList 的添加操作是一个比较耗时的操作，特别是在数组长度很大时。

关键代码如下：

     private void grow(int minCapacity) {
         // overflow-conscious code
         int oldCapacity = elementData.length;
       //容量扩容为原来的 1.5 倍
         int newCapacity = oldCapacity + (oldCapacity >> 1);
         if (newCapacity - minCapacity < 0)
             newCapacity = minCapacity;
         if (newCapacity - MAX_ARRAY_SIZE > 0)
             newCapacity = hugeCapacity(minCapacity);
         // 复制
         elementData = Arrays.copyOf(elementData, newCapacity);
     }
 
 
     public static  T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
         @SuppressWarnings("unchecked")
         T[] copy = ((Object)newType == (Object)Object[].class)
             ? (T[]) new Object[newLength]
             : (T[]) Array.newInstance(newType.getComponentType(), newLength);
         System.arraycopy(original, 0, copy, 0,
                          Math.min(original.length, newLength));
         return copy;
     }
 

随机访问 ArrayList 中的元素时，只需要根据元素的下标计算出在数组中的索引，然后直接访问该位置的元素即可。由于数组的内存是连续的，因此访问数组元素的速度非常快，时间复杂度为 O(1)。

     public E get(int index) {
         rangeCheck(index);
 
         return elementData(index);
     }
 
 
     //越界校验
     private void rangeCheck(int index) {
         if (index >= size)
             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
     }

上边你可以看到，这里有个 size 这个size是数组中实际的元素个数！而 elementData包含了元素，并且还有一部分的空余空间！

当需要删除 ArrayList 中的元素时，会将该元素从数组中删除，并将后面的元素往前移动。这个过程也是比较耗时的，特别是删除数组中靠前的元素时。

关键代码如下：

     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; // clear to let GC do its work
 
         return oldValue;
     }
 
 

当 ArrayList 中的元素数量变得很少时，我们可以使用 trimToSize 方法将容量缩小到实际元素数量，这样可以减小内存的开销。

 
     public void trimToSize() {
         modCount++;
         if (size < elementData.length) {
             elementData = (size == 0)
               ? EMPTY_ELEMENTDATA
               : Arrays.copyOf(elementData, size);
         }
     }

总结一下，ArrayList 的优点是支持随机访问，支持动态扩容；缺点是添加和删除元素比较耗时，特别是在数组长度很大时。在实际应用中，我们需要根据具体的业务场景，选择合适的数据结构来存储和操作数据