ArrayList自动扩容原理

举报
brucexiaogui 发表于 2021/12/29 23:26:57 2021/12/29
【摘要】 ArrayList自动扩容原理 一、ArrayList三种初始化 1、默认的构造器,将会以默认的大小来初始化内部的数组 public ArrayList(); 2、用一个ICollection对象来构造,并将该集合的元素添加到ArrayList public ArrayList(Collection<? extends ...

ArrayList自动扩容原理

一、ArrayList三种初始化

1、默认的构造器,将会以默认的大小来初始化内部的数组

public ArrayList();
 

2、用一个ICollection对象来构造,并将该集合的元素添加到ArrayList

public ArrayList(Collection<? extends E> c)
 

3、用指定的大小来初始化内部的数组

public ArrayList(int initialCapacity)
 

二、扩容概括

     扩容概括为两步:

     1、扩容---把原来的数组复制到另一个内存空间更大的数组中

     2、添加元素---把新元素添加到扩容以后的数组中

下面详细介绍扩容代码的实现原理和方法之间的调用关系

三、自动扩容从ArrayList初始化开始

1、无参构造方法:创建一个空数组


      transient Object[] elementData;
      private static final Object[] EMPTY_ELEMENTDATA = {};
      /**
       *无参构造方法实现创建一个空数组,并且为这个数组赋一个空值
       *
      */
      public ArrayList() {
             super();
             //为数组赋空值
             this.elementData = EMPTY_ELEMENTDATA;
          }
  
 

2、扩容从add( )开始


      /**
       *1、 ArrayList 扩容从add()开始
       *2、add方法有两条语句如下:
       * ensureCapacityInternal(size + 1); 判断是否需要调用扩容方法
       * elementData[size++] = e; 调用add方法添加的值赋值给数组。
       *
       */
         public boolean add(E e) {
              ensureCapacityInternal(size + 1);  // Increments modCount!!
              elementData[size++] = e;
             return true;
          }
  
 

3、ensureCapacityInternal:判断是否需要扩容


         //1、add方法调用ensureCapacityInternal方法
      private void ensureCapacityInternal(int minCapacity) {
         //2、判断当前数组是否为空
             if (elementData == EMPTY_ELEMENTDATA) {
                  minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
              }
         //3、调用扩容判断的方法,将当前最小扩容值传进去。
              ensureExplicitCapacity(minCapacity);
          }
         private void ensureExplicitCapacity(int minCapacity) {
              modCount++;
          /**
       * 4、minCapacity:最小扩容值
       *elementData.length:数组空间长度
       * 判断是否扩容原理:
       * (最小扩容值 - 数组空间长度 > 0)则调用扩容方法grow(minCapacity);
       * 举例:第一次调用add方法,最小扩容值为11,数组长度为10 那么(11- 10 > 0)调用扩容,扩容后是当
       *前值的1.5倍=15。
       * 第二次调用add方法,最小扩容值+1是12,数组长度为15那么(12- 15 > 0)不大于0,不调用扩容方法
       */
             // overflow-conscious code
             if (minCapacity - elementData.length > 0)
                  grow(minCapacity);
          }
  
 

4、grow(minCapacity) :计算扩容空间大小,并调用复制数组方法。


         private void grow(int minCapacity) {
             // overflow-conscious code
         //1、获取现在数组的长度
             int oldCapacity = elementData.length;
         //2、扩容后的数组长度
         // oldCapacity >> 1 右移运算符 原来长度的一半 再加上原长度也就是每次扩容是原来的1.5倍
             int newCapacity = oldCapacity + (oldCapacity >> 1);
         //3、判断扩容后的长度是否小于需要的最小扩容
             if (newCapacity - minCapacity < 0)
                  newCapacity = minCapacity;
         //4、判断扩容后的长度是否超过规定的最大值
             if (newCapacity - MAX_ARRAY_SIZE > 0)
                  newCapacity = hugeCapacity(minCapacity);
             // minCapacity is usually close to size, so this is a win:
         //5、调用复制数组方法,将老的数组复制到新的数组中,并将需要添加的元素加到数组最后一位
              elementData = Arrays.copyOf(elementData, newCapacity);
          }
  
 

 

文章来源: brucelong.blog.csdn.net,作者:Bruce小鬼,版权归原作者所有,如需转载,请联系作者。

原文链接:brucelong.blog.csdn.net/article/details/94012710

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。