源码分析ArrayList自动扩充原理

秒速五厘米 2022-02-02 12:31 181阅读 0赞

**ArrayList是动态增长和缩减的索引序列，基于数组的List实现**

那么，ArrayList到底是怎么样实现动态增长？

ArrayList的自动增长一般出现在使用add方法向集合中添加数据时，当集合中容量不够时自动扩充容量，使得数据可以添加进去。

接下来通过解析源码（jdk1.8）的方式来看一看当使用add向集合中添加元素时jvm会调用那些方法完成那些操作来进行容量扩展。

首先列出来在ArrayList中声名的几个常量或者变量

private static final int DEFAULT_CAPACITY = 10;
    
        private static final Object[] EMPTY_ELEMENTDATA = {};
    
    
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
      
        transient Object[] elementData;
    
     //arraylist中元素的个数
        private int size;

add方法，e为即将添加到集合中的元素

public boolean add(E e) {
    
            size为原集合中元素个数
            
            size+1为添加此元素后，集合中元素个数
    
           向ensureCapacityInternal方法中传入size+1来判断添加此元素时ArrayList中的容量是否够用
           以及容量不够时自动扩充等操作。
            
            ensureCapacityInternal(size + 1);  // Increments modCount!!
    
           向数组的末尾添加元素e，elementData为ArrayList的底层数组
           
            elementData[size++] = e;
            return true;
        }

ensureCapacityInternal方法用来做判断当原数组为空时为数组设置最小容量的操作  
参数minCapacity为add方法传过来的size+1的大小。

private void ensureCapacityInternal(int minCapacity) {
      
      判断原数组是否为空数组，为空时令数组的最小容量minCapacity的值为10
      此处只是设置变量的值为10，并没有扩充原数组的容量，此时元数组容量仍未0
          
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            
            ensureExplicitCapacity(minCapacity);
        }

ensureExplicitCapacity方法，用来判断原数组长度是否能满足添加元素后数组所需的最小容量  
当原数组为空时，显然条件成立进入grow方法进行容量扩充  
当原数组不为空时，实则比较添加元素后size+1的大小与数组原长度大小

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

grow方法，实现容量扩充

private void grow(int minCapacity) {
      
             获取扩容前容量      
            int oldCapacity = elementData.length;
            新的容量为扩容前容量的1.5倍
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            判断新的容量是否能满足添加元素的需求
            if (newCapacity - minCapacity < 0)
            如果size+1大新的容量，则令新容量的值等于size+1
                newCapacity = minCapacity;
             如果新的容量已经超过了最大容量限制，就通过 hugeCapacity方法将最大容量给他
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity is usually close to size, so this is a win:
            最后调用copyOf方法进行扩容
            elementData = Arrays.copyOf(elementData, newCapacity);
        }

hugeCapacity方法，比较返回值  
MAX\_VALUE = 0x7fffffff;

private static int hugeCapacity(int minCapacity) {
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
    
            return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
        }

以上就是ArrayList中自动扩充容量的所有过程，简单的过程如下图所示  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01hc3Rlcl9LaW4_size_16_color_FFFFFF_t_70]  
接下来通过向源码中添加断点的方式，用debug运行一下，看一下一个空ArrayList到底是怎样扩充容量的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01hc3Rlcl9LaW4_size_16_color_FFFFFF_t_70 1]向源码中的几处随机的添加了断点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01hc3Rlcl9LaW4_size_16_color_FFFFFF_t_70 2]写一个简单的测试，使用add方法  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01hc3Rlcl9LaW4_size_16_color_FFFFFF_t_70 3]debug运行，进入add方法，此时的size=0

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01hc3Rlcl9LaW4_size_16_color_FFFFFF_t_70 4]进入ensureCapacityInternal方法，进过空集合判断，使minCapactiy的值为10

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01hc3Rlcl9LaW4_size_16_color_FFFFFF_t_70 5]进入ensureExplicitCapacity方法  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01hc3Rlcl9LaW4_size_16_color_FFFFFF_t_70 6]grow方法，由于原集合为空，所以oldCapacity和newCapacity都为0  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01hc3Rlcl9LaW4_size_16_color_FFFFFF_t_70 7]经过赋值后newCapactiy=minCapacity=10  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01hc3Rlcl9LaW4_size_16_color_FFFFFF_t_70 8]运行完成，可以看到size变为1

以上就是ArrayList中空集合添加元素时容量自动扩充的全部过程。

如果以上解析有错误或者有其他问题请在评论中指出。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01hc3Rlcl9LaW4_size_16_color_FFFFFF_t_70]: /images/20220202/d6c1deffc4814a75b3824a7826abeac3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01hc3Rlcl9LaW4_size_16_color_FFFFFF_t_70 1]: /images/20220202/f6080566fbce48949e7bc975c143d291.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01hc3Rlcl9LaW4_size_16_color_FFFFFF_t_70 2]: /images/20220202/89d1d6f8f75c4d6899c2943585eb6ad8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01hc3Rlcl9LaW4_size_16_color_FFFFFF_t_70 3]: /images/20220202/66b2b2a7e1734f599f809e9e2da0397c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01hc3Rlcl9LaW4_size_16_color_FFFFFF_t_70 4]: /images/20220202/9d80f170864948fd9ed8ad8d3735087f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01hc3Rlcl9LaW4_size_16_color_FFFFFF_t_70 5]: /images/20220202/6b42f4f74b374273be3101e82199a61c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01hc3Rlcl9LaW4_size_16_color_FFFFFF_t_70 6]: /images/20220202/bd4c7cefbb8c455cb843e1413b011f55.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01hc3Rlcl9LaW4_size_16_color_FFFFFF_t_70 7]: /images/20220202/0a4392d8557c499ead7b8c196971127c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01hc3Rlcl9LaW4_size_16_color_FFFFFF_t_70 8]: /images/20220202/d294d9c747a64bf188b31ff2203b4717.png