源码分析之ArrayList容器

分手后的思念是犯贱 2022-11-13 10:22 168阅读 0赞

### 源码分析之ArrayList容器 ###

*   *  1、ArrayList容器概述
     *  2、ArrayList类主要属性
     *  3、ArrayList类构造器
     *  4、查找相关方法
     *  5、插入相关方法
     *  6、删除相关方法
     *  7、其它方法
     *  8、总结
     *  9、往期佳文
     *   *  9.1、面试系列
         *  9.2、技术系列
         *  9.3、源码系列

## 1、ArrayList容器概述 ##

Java中的ArrayList类声明如下：

public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70]  
       Java中的ArrayList容器是一个可动态调整大小的数组，每当我们往容器中插入元素都不必考虑容器是否装的下，其内部可以自动扩展大小。ArrayList容器的实现原理是封装了一个数组，每当插入元素就判断当前数组是否还有空位置存放，如果没有空位置，则新建一个更长的数组，并且把之前的元素复制到新数组中。

## 2、ArrayList类主要属性 ##

ArrayList类中的主要属性如下：

/** * 默认数组初始化的大小 */
    private static final int DEFAULT_CAPACITY = 10;
    
    /** * 空数组实例（当初始化容量=0时） */
    private static final Object[] EMPTY_ELEMENTDATA = { };
    
    /** * 调用默认构造器时，初始化的空数组实例 */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };
    
    /** * ArrayList底层存放元素使用的数组 */
    transient Object[] elementData;
    
    /** * 数组中存放的元素个数（注意与数组长度的区分） */
    private int size;

## 3、ArrayList类构造器 ##

ArrayList类中共有3个构造器：

/** * 指定数组的初始化长度 */
    public ArrayList(int initialCapacity) { 
    	// 主要是初始化elementData数组
        if (initialCapacity > 0) { 
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) { 
        	// EMPTY_ELEMENTDATA默认的空数组实现（前面介绍了这个静态属性）
            this.elementData = EMPTY_ELEMENTDATA;
        } else { 
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    
    /** * 默认构造器 */
    public ArrayList() { 
    	// 表示数组未初始化（DEFAULTCAPACITY_EMPTY_ELEMENTDATA数组空实现，前面介绍过这个静态属性）
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    /** * 复制构造器 */
    public ArrayList(Collection<? extends E> c) { 
    	// 调用容器c中的toArray方法，获取数组形式的数据
        elementData = c.toArray();
        if ((size = elementData.length) != 0) { 
            // c.toArray可能返回的不是Object[].class，所以进行类型转换
            if (elementData.getClass() != Object[].class)
            	// 调用Arrays.copyOf方法，copy出一个Object[].class形式的副本
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else { 
            // 如果容器c为空，则初始化elementData为空数组示例
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

## 4、查找相关方法 ##

1、get方法

/** * 通过index获取elementData中的元素（此方法未使用任何权限修饰符，所以默认是default，在当前包下可使用） */
    @SuppressWarnings("unchecked")
    E elementData(int index) { 
        return (E) elementData[index];
    }
    
    /** * 通过index获取elementData中的元素（public修饰，对外展示接口） */
    public E get(int index) { 
    	// 查找前先判断index是否超过了size（数组中元素的个数）
        rangeCheck(index);
    
        return elementData(index);
    }

2、contains方法

/** * 判断Object是否存在于容器中 */
    public boolean contains(Object o) { 
    	// 如果能查找到该元素的下标，则说明是存在的
        return indexOf(o) >= 0;
    }

3、indexOf、lastIndexOf方法

/** * 查找Object在容器数组中的第一个下标（未查找到返回-1） */
    public int indexOf(Object o) { 
    	// 如果o为null，则o需要==判断，否则调用equals方法判断是否相等
        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]))
                    return i;
        }
        return -1;
    }
    
    /** * 查找Object在容器数组中的最后一个下标（未查找到返回-1） */
    public int lastIndexOf(Object o) { 
    	// 与indexOf的区别就是从后往前查找，找的的就是最后一个下标
        if (o == null) { 
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else { 
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

## 5、插入相关方法 ##

1、add方法

/** * 往容器尾端增加一个元素 */
    public boolean add(E e) { 
    	// 增加元素前需要判断是否有空位置（没有就需要扩容
        ensureCapacityInternal(size + 1);
        // 直接放入elementData数组中的下一个空位置
        elementData[size++] = e;
        return true;
    }
    /** * 往容器指定下标插入一个元素 */
    public void add(int index, E element) { 
    	// 插入前需要判断插入的下标是否在[0, size]中，也就是不能插入到非连续的其它位置
        rangeCheckForAdd(index);
    	// 当然还需要判断容器是否有空间供插入
        ensureCapacityInternal(size + 1);
        // arraycopy的五个参数分别是，数组src，起始下标，数组des，起始下标，复制的个数
        // 此时我们需要把elementData[index]这个位置空出来，也就是[index, size)区间的元素全部往后移动一个位置，index移动到index+1，index+1移动到index+2
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        // 现在就可以放入插入的元素了
        elementData[index] = element;
        // 容器中的元素数量自增1
        size++;
    }
           2、set方法
    /** * 此方法是修改指定下标的元素值 */
    public E set(int index, E element) { 
    	// 如果这个下标超出[0, size)都算错误！（注意与[0, elementData.length)的区别）
    	// 因为这是修改方法，如果这个index对应没有值，则不能修改
        rangeCheck(index);
    	// 修改前记录旧值，在替换心值
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

## 6、删除相关方法 ##

1、remove方法

/** * 移除容器中指定下标的元素 */
    public E remove(int index) { 
    	// 检查下标是否在[0, size)区间中
        rangeCheck(index);
    	// 父类AbstractList中的一个变量，用于记录结构性调整（插入、删除、修改等）的次数
        modCount++;
        E oldValue = elementData(index);
    	// [index + 1, size)区间的中的元素全部前一个位置
        int numMoved = size - index - 1;
        // arraycopy的五个参数分别是，数组src，起始下标，数组des，起始下标，复制的个数
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        // 将size - 1的元素移除
        elementData[--size] = null;
    
        return oldValue;
    }
    
    /** * 移除容器中的o对象（第一个） */
    public boolean remove(Object o) { 
    	// 遍历一遍容器，把值为对象o的元素全部移除
        if (o == null) { 
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) { 
                	// 此方法移除时不判断index的合法性，直接移除（因为传入的下标就是合法的）
                    fastRemove(index);
                    return true;
                }
        } else { 
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) { 
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
    
    /* * 移除index下标对应的元素（不进行index判断，默认index是合法的） */
    private void fastRemove(int index) { 
    	// 与public E remove(int index)方法是一样的，只是没了index判断
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        elementData[--size] = null;
    }

## 7、其它方法 ##

1、trimToSize方法

/** * 此方法的作用是将elementData数组中的空余位置剔除（有点像瘦身） */
    public void trimToSize() { 
    	// 次方法也属于结构性调整
        modCount++;
        if (size < elementData.length) { 
        	// 如果elementData数组存在元素，则调用Arrays.copyOf方法，复制到一个长度为size的数组中
            elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size);
        }
    }

2、grow扩容方法

/** * 增加elementData数组的长度 */
    private void grow(int minCapacity) { 
        // 新长度为原长度的1.5倍
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果新长度 比 最小的长度小，则修改为最小的长度
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 如果新长度比MAX_ARRAY_SIZE还大，修改为默认的最大值
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 调用Arrays.copyOf方法，复制到一个长度为newCapacity的数组中
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

## 8、总结 ##

经过上面的分析不难看出，ArrayList容器的底层实现特别简单，就是封装了一个数组，每当插入元素就判断一下是否容的下，容不下就扩容。ArrayList容器支持尾端插入、根据下标插入（随机插入）；支持按下标查找（随机查找）、按值查找。

## 9、往期佳文 ##

### 9.1、面试系列 ###

1、[吊打面试官之一面自我介绍][Link 1]  
2、[吊打面试官之一面项目介绍][Link 2]  
3、[吊打面试官之一面系统架构设计][Link 3]  
4、[吊打面试官之一面你负责哪一块][Link 4]  
5、[吊打面试官之一面试官提问][Link 5]

······持续更新中······

--------------------

### 9.2、技术系列 ###

1、[吊打面试官之分布式会话][Link 6]  
2、[吊打面试官之分布式锁][Link 7]  
3、[吊打面试官之乐观锁][Link 8]  
4、[吊打面试官之幂等性问题][Link 9]  
5、[吊打面试关之分布式事务][Link 10]  
6、[吊打面试官之项目线上问题排查][Link 11]

······持续更新中······

### 9.3、源码系列 ###

1、[源码分析之SpringBoot启动流程原理][SpringBoot]  
2、[源码分析之SpringBoot自动装配原理][SpringBoot 1]

······持续更新中······

--------------------

转载：[Java容器之ArrayList源码分析][Java_ArrayList]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70]: /images/20221022/1e7eaa9a17574641a00fc0929a09057e.png
[Link 1]: https://blog.csdn.net/wtyicy/article/details/114933478
[Link 2]: https://blog.csdn.net/wtyicy/article/details/114983053
[Link 3]: https://blog.csdn.net/wtyicy/article/details/115005012
[Link 4]: https://blog.csdn.net/wtyicy/article/details/115064661
[Link 5]: https://blog.csdn.net/wtyicy/article/details/115296365
[Link 6]: https://blog.csdn.net/wtyicy/article/details/114685293
[Link 7]: https://blog.csdn.net/wtyicy/article/details/114915987
[Link 8]: https://blog.csdn.net/wtyicy/article/details/114915177
[Link 9]: https://blog.csdn.net/wtyicy/article/details/114888754
[Link 10]: https://blog.csdn.net/wtyicy/article/details/115081790
[Link 11]: https://blog.csdn.net/wtyicy/article/details/115292969
[SpringBoot]: https://blog.csdn.net/wtyicy/article/details/115181539
[SpringBoot 1]: https://blog.csdn.net/wtyicy/article/details/115233701
[Java_ArrayList]: https://blog.csdn.net/qq_41855420/article/details/105744523