ArrayList源码（JDK1.8）

心已赠人 2023-10-04 10:26 4阅读 0赞

#### 目录 ####

*   *  1.ArrayList新建对象
     *  2.add
     *   *  2.1默认的初始化容量大小
         *  2.2add的自动扩容
     *  3.contains
     *  4，size

首先可以看看ArrayList类的继承结构（idea的diagrams绘画）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NTUwOTg2_size_16_color_FFFFFF_t_70_pic_center]

### 1.ArrayList新建对象 ###

1.1我们不指定容量时，ArrayList数组的容量是多少？

ArrayList<Integer> list = new ArrayList<>();

看源码：

/**
         * Constructs an empty list with an initial capacity of ten.
         */
        public ArrayList() {
        
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;//这首一个空数组对象：{}；
        }
    
        /**
         * Shared empty array instance used for default sized empty instances. We
         * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
         * first element is added.
         */
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
        };

所以直接new Arraylist（）；得到的只是一个空数组：\{\}；初始容量：0；

1.2.指定容量

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);
            }
        }

指定容量很简单，只要>=0,就是合法的，会按照指定的大小去初始化数组大小；小于0，会报错；

### 2.add ###

#### 2.1默认的初始化容量大小 ####

我们知道如果没有指定数组大小，会赋值一个\{\}，在这种情况下我们可以往ArrayList里add数据，比如下图，我们new的是一个空数组，但是却能往里面添加数据，那在add的时候到底发生了什么？

ArrayList<Integer> list = new ArrayList<>();
            list.add(1);
            list.add(2);
            list.add(3);
            list.add(4);
            list.add(5);

看源码：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NTUwOTg2_size_16_color_FFFFFF_t_70_pic_center 1]  
我们先看到这里，先解释一下：  
size：是数组里面已经存储元素的个数；  
看到这里我们可以了解到为什么我们空数组可以添加数据了；

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        
        //如果是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，会返回一个DEFAULT_CAPACITY（10）
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            return minCapacity;
        }
    
    
        /**
         * Default initial capacity.
         */
        private static final int DEFAULT_CAPACITY = 10;

如果我们在new对象时，没有初始化大小，那么在add的时候，会初始化数组容量：DEFAULT\_CAPACITY = 10；

#### 2.2add的自动扩容 ####

看源码：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NTUwOTg2_size_16_color_FFFFFF_t_70_pic_center 2]

看这段代码:

private void ensureExplicitCapacity(int minCapacity) {
        
            modCount++;
    
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }

其实要分2种情况：  
数组初始化的时候有没有指定数组的容量；

第一种情况：没有指定数组容量：此时的minCapacity的值是：10（默认的数组容量）,而此时的elementData是\{\}，所以elementData.length=0；因此这个时候必定会进入下面的grow(minCapacity)方法，这个方法其实就是对数组进行扩容；  
第二种情况，指定了数组大小，这个时候minCapacity = size+1；这个时候就是size+1与elementData.length进行比较；  
我们之前说过size是：数组已经存储元素的个数；因此用size+1来判断此时数组还能不能再存储一个元素；  
如果size+1>elementData.length;说明数组长度不够，因此需要扩容，就会进入下面的grow(minCapacity)方法进行扩容；  
如果size+1<=elementData.length;说明数组长度足够，则不需要扩容；直接存储元素即可；

扩容的关键代码：

private void grow(int minCapacity) {
        
            // overflow-conscious code
            int oldCapacity = elementData.length;
            //oldCapacity >> 1 =====》这个位运算就是oldCapacity/2的意思
            //oldCapacity + (oldCapacity >> 1);==》可以理解为：1.5 * oldCapacity 
            int newCapacity = oldCapacity + (oldCapacity >> 1);           
            //可能初看这段代码会觉得比较难以理解，怎么newCapacity会比minCapacity小，为什么会做这样的判断？
            //其实就是因为扩容后的值newCapacity 超过了最大整数，就会变回负数，因此会有这个判断        
            //如果创建对象没有指定数组容量，或者指定数组容量：1；这种情况也会导致newCapacity 比newCapacity 小
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;//minCapacity=size+1
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity is usually close to size, so this is a win:
            //将原数组的数据复制到新数组中；
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    
    	//ArrayList数组建议的最大数组长度，实际上最大值可以到 Integer.MAX_VALUE
        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private static int hugeCapacity(int minCapacity) {
        
            if (minCapacity < 0)//minCapacity<0 表示超过最大整数;其实ArrayList支持的最大值就是:Integer.MAX_VALUE
                throw new OutOfMemoryError();
            return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
        }

因此可以看到正常情况下扩容是：1.5倍；  
newCapacity = oldCapacity + (oldCapacity >> 1);可以看作newCapacity=1.5 \* oldCapacity ；  
特殊情况：  
newCapacity(1.5 \* oldCapacity) >Integer.MAX\_VALUE,此时先将newCapacity赋值：  
newCapacity=minCapacity;//minCapacity=size+1；  
再将newCapacity与MAX\_ARRAY\_SIZE比较：  
当newCapacity<=MAX\_ARRAY\_SIZE（MAX\_ARRAY\_SIZE是ArrayList数组设置的最大容量阈值）时，newCapacity=MAX\_ARRAY\_SIZE；  
当newCapacity>MAX\_ARRAY\_SIZE时：newCapacity=Integer.MAX\_VALUE；

我们可以总结一下ArrayList如何扩容:【用newCapacity代替oldCapacity + (oldCapacity >> 1)】

<table> 
 <thead> 
  <tr> 
   <th align="left">条件</th> 
   <th align="left">扩容</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">newCapacity &lt; Integer.MAX_VALUE</td> 
   <td align="left">newCapacity = oldCapacity + (oldCapacity &gt;&gt; 1)</td> 
  </tr> 
  <tr> 
   <td align="left">newCapacity&gt; Integer.MAX_VALUE &amp;&amp; size+1&lt;MAX_ARRAY_SIZE</td> 
   <td align="left">newCapacity = MAX_ARRAY_SIZE</td> 
  </tr> 
  <tr> 
   <td align="left">newCapacity &gt; Integer.MAX_VALUE &amp;&amp; size+1&gt;MAX_ARRAY_SIZE</td> 
   <td align="left">newCapacity = Integer.MAX_VALUE</td> 
  </tr> 
  <tr> 
   <td align="left">newCapacity &gt; Integer.MAX_VALUE &amp;&amp; size+1&gt;Integer.MAX_VALUE</td> 
   <td align="left">OutOfMemoryError</td> 
  </tr> 
 </tbody> 
</table>

### 3.contains ###

这个方法比较简单，看源码：

public boolean contains(Object o) {
        
            return indexOf(o) >= 0;//实际上去找元素的索引，索引值不是-1就说明存在；
        }

//在遍历数组时，最大值是size，而不是elementData.length,减少查询时间；
    //在元素存在的时候，两者并没有区别；
    //减少时间是在找不到的时候会减少查询次数，查询到下标：size-1就返回；而不用遍历整个数组
        public int indexOf(Object o) {
        
            if (o == null) {
        //从头开始查询
                for (int i = 0; i < size; i++)
                    if (elementData[i]==null)
                        return i;
            } else {
        //从头开始查询
                for (int i = 0; i < size; i++)
                    if (o.equals(elementData[i]))//这是直接用的object的equals方法，也就是说必须为同一个对象才会返回true
                        return i;
            }
            return -1;//没找到返回-1；
        }

### 4，size ###

/**
         *返回元素个数
         * Returns the number of elements in this list.
         *
         * @return the number of elements in this list
         */
        public int size() {
        
            return size;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NTUwOTg2_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20210410221212320.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NTUwOTg2,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NTUwOTg2_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20210410231736367.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NTUwOTg2,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NTUwOTg2_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20210410235146366.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NTUwOTg2,size_16,color_FFFFFF,t_70#pic_center