最新消息: PyCharm vs VSCode,哪个更好?
您现在的位置是:群英 > 服务器 > 系统运维 >
浅析ArrayList的底层原理
CSDN发表于 2020-09-15 16:50 次浏览
ArrayList简介
ArrayList是我们在开发中非常常用的数据存储容器之一,其底层是数组实现的,我们可以在集合中存储任意类型的数据。ArrayList又是线程不安全的,这在接下来代码分析的过程中会有体现。ArrayList非常适合对元素进行查找,效率非常高。

ArrayList源码分析

1、java.util.ArrayList<E> : List 接口的大小可变数组的实现类

  • ArrayList 内部基于 数组 存储 各个元素。
  • 所谓大小可变数组,是指当 数组容量不足以存放新的元素时,创建新数组,并将原数组中的内容复制过来。

2、ArrayList底层实现原理

  • 构造方法源码分析
    
    		
    1.  
      //对象数组:ArrayList的底层数据结构,transient表示该字段不进行序列化操作
    2.  
      transient Object[] elementData;
    3.  
      //实例化一个空数组
    4.  
      private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    5.  
      //实例化一个空数组
    6.  
      private static final Object[] EMPTY_ELEMENTDATA = {};
    7.  
       
    8.  
      /**
    9.  
      *指定初始容量的有参构造
    10.  
      */
    11.  
      public ArrayList(int initialCapacity) {
    12.  
      //如果初始容量大于0就,对象数组就指向到一个新的数组,大小为所指定的大小
    13.  
      if (initialCapacity > 0) {
    14.  
      this.elementData = new Object[initialCapacity];
    15.  
      } else if (initialCapacity == 0) {
    16.  
      //如果大于0就指向一个空数组
    17.  
      this.elementData = EMPTY_ELEMENTDATA;
    18.  
      } else {
    19.  
      throw new IllegalArgumentException("Illegal Capacity: "+
    20.  
      initialCapacity);
    21.  
      }
    22.  
      }
    23.  
      /**
    24.  
      * 无参构造
    25.  
      */
    26.  
      public ArrayList() {
    27.  
      //对象数组就指向到一个空数组
    28.  
      this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    29.  
      }

    ArrayList基于数组实现,构造方法有有参构造和无参构造如果指定了初始容量且大于0就将对象数组指定到一个新的数组,大小为所指定的大小。如果调用无参构造就将对象数组指定到一个空的数组。

  • 添加方法源码分析
    
    		
    1.  
      //elementData中已存放的元素的个数,注意:不是elementData的容量
    2.  
      private int size;
    3.  
      //elementData的默认容量为10
    4.  
      private static final int DEFAULT_CAPACITY = 10;
    5.  
      //对象数组:ArrayList的底层数据结构,transient表示该字段不进行序列化操作
    6.  
      transient Object[] elementData;
    7.  
      //实例化一个空数组
    8.  
      private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    9.  
      //实例化一个空数组
    10.  
      private static final Object[] EMPTY_ELEMENTDATA = {};
    11.  
       
    12.  
      protected transient int modCount = 0;
    13.  
       
    14.  
      @Native public static final int MAX_VALUE = 0x7fffffff;
    15.  
       
    16.  
      private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    17.  
       
    18.  
      /**
    19.  
      * 向elementData末尾中添加元素
    20.  
      */
    21.  
      public boolean add(E e) {
    22.  
      //确保对象数组elementData有足够的容量,可以将新加入的元素e加进去
    23.  
      ensureCapacityInternal(size + 1);
    24.  
      //加入新元素e,size加1
    25.  
      elementData[size++] = e;
    26.  
      return true;
    27.  
      }
    28.  
       
    29.  
      // minCapacity = seize+1,即表示执行完添加操作后,数组中的元素个数
    30.  
      private void ensureCapacityInternal(int minCapacity) {
    31.  
      //判断是否是空数组
    32.  
      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    33.  
      //用最小容量和10进行比较,取最大值赋值给最小容量
    34.  
      minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    35.  
      }
    36.  
       
    37.  
      ensureExplicitCapacity(minCapacity);
    38.  
      }
    39.  
       
    40.  
      /**
    41.  
      *确保数组的容量足够存放新加入的元素,若不够,要扩容
    42.  
      */
    43.  
      private void ensureExplicitCapacity(int minCapacity) {
    44.  
      modCount++;
    45.  
      //如果数组个数minCapacity (size+1)大于数组长度就需要进行扩容
    46.  
      if (minCapacity - elementData.length > 0)
    47.  
      grow(minCapacity);
    48.  
      }
    49.  
       
    50.  
      private void grow(int minCapacity) {
    51.  
      int oldCapacity = elementData.length;
    52.  
      // 将旧的数组容量增加为原来的1.5倍作为新的容量
    53.  
      int newCapacity = oldCapacity + (oldCapacity >> 1);
    54.  
      //如果新的容量小于数组个数,将数组个数赋值给新容量
    55.  
      if (newCapacity - minCapacity < 0)
    56.  
      newCapacity = minCapacity;
    57.  
      // 如果新的容量大于最大容量,就根据数组个数来决定新的容量大小
    58.  
      if (newCapacity - MAX_ARRAY_SIZE > 0)
    59.  
      newCapacity = hugeCapacity(minCapacity);
    60.  
      // 根据新的容量,将数组拷贝到新的数组并赋值给数组
    61.  
      elementData = Arrays.copyOf(elementData, newCapacity);
    62.  
      }
    63.  
       
    64.  
      private static int hugeCapacity(int minCapacity) {
    65.  
      // 如果数组个数小于0抛出OutOfMemoryError异常
    66.  
      if (minCapacity < 0) // overflow
    67.  
      throw new OutOfMemoryError();
    68.  
      // 如果最数组个数大于最大容量 就返回最大值,否则返回最大容量
    69.  
      return (minCapacity > MAX_ARRAY_SIZE) ?
    70.  
      Integer.MAX_VALUE :
    71.  
      MAX_ARRAY_SIZE;
    72.  
      }
    73.  
      /**
    74.  
      * 向elementData指定位置添加元素
    75.  
      */
    76.  
      public void add(int index, E element) {
    77.  
      //指定位置检查
    78.  
      rangeCheckForAdd(index);
    79.  
      // 扩容检查
    80.  
      ensureCapacityInternal(size + 1); // Increments modCount!!
    81.  
      //通过拷贝使数组内位置为 index 到 (size-1)的元素往后移动一位
    82.  
      System.arraycopy(elementData, index, elementData, index + 1,
    83.  
      size - index);
    84.  
      // 找到位置添加元素
    85.  
      elementData[index] = element;
    86.  
      // 元素个数加一
    87.  
      size++;
    88.  
      }
    89.  
      // 判断指定位置是否超出数组个数
    90.  
      private void rangeCheckForAdd(int index) {
    91.  
      if (index > size || index < 0)
    92.  
      throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    93.  
      }
    94.  
      /**
    95.  
      * @param src 原数组.
    96.  
      * @param srcPos 原数组的起始位置.
    97.  
      * @param dest 目标数组.
    98.  
      * @param destPos 目标数组的起始位置.
    99.  
      * @param length 拷贝长度.
    100.  
      */
    101.  
      public static native void arraycopy(Object src, int srcPos,
    102.  
      Object dest, int destPos,
    103.  
      int length);

    ArrayList在无参的add方法中,每次插入新的元素时,先判断是否需要扩容,判断数组是否为空,为空则建默认的容量10赋值给minCapacity,判断是否要扩容,第一次添加,数组的size是10,之后添加元素时,在ensureExplicitCapacity方法中判断数组元素个数即size+1(形参minCapacity)是否超过数组长度,超过则需要进行扩容操作,扩容是将旧的容量扩大到1.5倍,然后将数组拷贝到新的数组完成扩容操作。最后将元素添加,并size+1。ArrayList在指定位置添加元素时,是先检查指定位置是否在数组范围内,即数组中元素个数是1,则index得小于或者低于1。然后通过拷贝使数组内位置为 index 到 (size-1)的元素往后移动一位,腾出位置之后放入元素,数组个数加一。

  • 删除方法源码分析
    
    		
    1.  
      public E remove(int index) {
    2.  
      //指定位置检查
    3.  
      rangeCheck(index);
    4.  
      modCount++;
    5.  
      //保留要删除的值
    6.  
      E oldValue = elementData(index);
    7.  
      //要移动元素个数
    8.  
      int numMoved = size - index - 1;
    9.  
      if (numMoved > 0)
    10.  
      //通过拷贝使数组内位置为 index+1到 (size-1)的元素往前移动一位
    11.  
      System.arraycopy(elementData, index+1, elementData, index,
    12.  
      numMoved);
    13.  
      //清除末尾元素让GC回收
    14.  
      elementData[--size] = null; // clear to let GC do its work
    15.  
      //返回删除的值
    16.  
      return oldValue;
    17.  
      }

    删除指定位置的元素,先对index进行检查,在将要删除的值保留,计算出需要移动元素个数,再通过拷贝使数组内位置为 index+1到 (size-1)的元素往前移动一位,最后将末尾元素清理让GC回收返回删除值。由于List接口继承了Collection,因此ArrayList还有一个来自Collection接口定义的删除对象boolean remove( Object o ) ,而ArrayList自定义的remove方法是T remove(int index)删除的是下标位置的对象并返回值。

标签:arraylist
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:mmqy2019@163.com进行举报,并提供相关证据,查实之后,将立刻删除涉嫌侵权内容。
相关信息推荐