ArrayList集合底层原理

阳光穿透心脏的1/2处 2023-09-24 22:01 9阅读 0赞

### ArrayList集合底层原理 ###

*  ArrayList集合底层原理
 *   *  1.介绍
     *  2.底层实现
     *  3.构造方法
     *  3.1集合的属性
     *  4.扩容机制
     *  5.其他方法
     *  6.总结

# ArrayList集合底层原理 #

## 1.介绍 ##

ArrayList是List接口的可变数组的实现。实现了所有可选列表操作，并允许包括 null 在 内的所有元素。 每个 ArrayList 实例都有一个容量，该容量是指用来存储列表元素的数组的大小。它是至少等于列表的大小。随着向 ArrayList 中不断添加元素，其容量也自动增长。自动增长会带来数据向新数组的重新拷贝，因此，如果可预知数据量的多少，可在构造 ArrayList 时 指定其容量。

[ArrayList集合特点为什么是增删慢、查询快][ArrayList]

## 2.底层实现 ##

底层使用数组实现
    transient Object[] elementData;

## 3.构造方法 ##

ArrayList 提供了三种方式的构造器，可以构造一个默认初始容量为 10 的空列表、构造 一个指定初始容量的空列表以及构造一个包含指定 collection 的元素的列表，这些元素按照 该 collection 的迭代器返回它们的顺序排列的。

// 空参构造
    ArrayList<String> list1 = new ArrayList<>(); 
    // 源码
    public ArrayList() {
        
        /*
        DEFAULTCAPACITY_EMPTY_ELEMENTDATA: 指向private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};空数组.
        注意:默认长度是在第一次添加元素时赋值的数组
        */
         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
     }
    
    // 指定初始长度
    ArrayList<String> list2 = new ArrayList<>(100);
    // 源码
    public ArrayList(int initialCapacity) {
        
        // 判断传入的长度大小
        if (initialCapacity > 0) {
        
            // 根据长度创建数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
        
            // 如果等于0,返回默认长度数组
            // EMPTY_ELEMENTDATAprivate: 指向static final Object[] EMPTY_ELEMENTDATA = {};
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
        
            throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
        }
    }
    // 包含指定 collection 的元素的列表
    List<String> list = new ArrayList<>();
    ArrayList<String> list3 = new ArrayList<>(list);
    // 源码
    public ArrayList(Collection<? extends E> c) {
        
        // 先把传入的集合转成数组
        elementData = c.toArray();
        // 判断集合的长度是否等于0
        if ((size = elementData.length) != 0) {
        
           	// 判断数组字节码类型 为什么要判断,因为c.toArray()有可能转变的不是Object数组
            if (elementData.getClass() != Object[].class)
                // copyOf把参数集合的元素拷贝到定义数组
                // elementData:要复制的数组
                // size:长度
                // Object[].class:要返回的新数组
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
        
            //EMPTY_ELEMENTDATA:指向:private static final Object[] EMPTY_ELEMENTDATA = {};
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

## 3.1集合的属性 ##

//默认容量的大小
    private static final int DEFAULT_CAPACITY = 10;
    
    //空数组常量
    private static final Object[] EMPTY_ELEMENTDATA = {
        };
    
    //默认的空数组常量
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
        };
    
    //存放元素的数组，从这可以发现 ArrayList 的底层实现就是一个 Object数组
    transient Object[] elementData;
    
    //数组中包含的元素个数
    private int size;
    
    //数组的最大上限
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

## 4.扩容机制 ##

图解:  
![请添加图片描述][7d60ef179dce4f23a7e30155284ab743.png]

扩容源码:

public boolean add(E e) {
        
        // 计数器,返回实时增加的元素个数,比如调用size()方法返回的集合元素个数
        modCount++;
        /*
        	1.e:表示现在要添加的元素
        	2.elementData集合底层数组名
        	3.size本次要添加的索引位置,第一次添加size的值为0
        */
        add(e, elementData, size);
        return true;
    }
    
    private void add(E e, Object[] elementData, int s) {
        
        // 判断存入的位置索引
        if (s == elementData.length)
            // 调用grow方法进行扩容
            elementData = grow();
        // 索引位置小于数组长度正常存入
        elementData[s] = e;
        size = s + 1;
    }
    
    private Object[] grow() {
        
        // 第一次存入元素size默认为0,进行长度加1
        return grow(size + 1);
    }
    
    private Object[] grow(int minCapacity) {
        
        /*
        	创建一个新的数组长度为10
        	把原来数组元素拷贝进去
        	minCapacity:传入的容量
        */
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }
    
    private int newCapacity(int minCapacity) {
        
        // overflow-conscious code
        // 旧容量
        int oldCapacity = elementData.length;
        // 新容量 = 旧容量 * 1.5
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 拿新的容量 - 传入的大小 如果结果小于0,
        if (newCapacity - minCapacity <= 0) {
        
            // 第一次扩容
            // 判断数组是否是同一个数组
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                // DEFAULT_CAPACITY默认容量=10
                // 比较默认容量与传入容量大小,把最大返回
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow 内存溢出
                throw new OutOfMemoryError();
            return minCapacity;
        }
        // 返回新的长度
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }
    
    ArrayList的add方法，在插入元素之前，它会先检查是否需要扩容，然后再把元素添加到数组中最后一个元素的后面。
    在 newCapacity 方法中，我们可以看见，如果当 elementData 为空数组时，它会使用默认的大小去扩容。所以说，
    通过无参构造方法来创建 ArrayList 时，它的大小其实是为 0 的，只有在使用到的时候，才会通过 grow 方法去创建
    一个大小为 10 的数组。第一个 add 方法的复杂度为 O(1)，虽然有时候会涉及到扩容的操作，但是扩容的次数是非常
    少的，所以这一部分的时间可以忽略不计。如果使用的是带指定下标的 add方法，则复杂度为 O(n)，因为涉及到
    对数组中元素的移动，这一操作是非常耗时的。

## 5.其他方法 ##

// 修改方法
    public E set(int index, E element) {
        
        // 判断是否会发生异常
        Objects.checkIndex(index, size);
        // 根据索引获取元素
        E oldValue = elementData(index);
        // 把传入的元素替换原来的元素
        elementData[index] = element;
        // 返回原来的元素
        return oldValue;
    }
    
    
    // 指定索引处添加,如果当前有元素,则向右移动当前位与该位置的元素以及所有后续元素
    public void add(int index, E element) {
        
        // 判断是否发生异常
        rangeCheckForAdd(index);
        // 记录修改次数, 一般研究线程安全性问题,关注这个变量
        modCount++;
        final int s;
        Object[] elementData;
        /*
        	(s = size):数组长度,下面拷贝使用了
        	(elementData = this.elementData):当前数组,下面有用到
        	
        	判断元素个数是否与数组长度相同
        */
        if ((s = size) == (elementData = this.elementData).length)
            // 数组扩容前面已经讲解
            elementData = grow();
        // 将elementData中从index位置开始,长度为s-index的元素
        // 拷贝到从下标为index+1位置开始的新的elementData数组中
        // 也就是当前位于该位置的元素以及后面的元素向后移动一位
        System.arraycopy(elementData, index,
                         elementData, index + 1,
                         s - index);
        // 把元素赋值到指定索引处
        elementData[index] = element;
        // 长度加一
        size = s + 1;
    }
    
    // 返回此列表中指定位置上的元素。
    public E get(int index) {
        
        // 判断异常
        Objects.checkIndex(index, size);
        // 返回元素
        return elementData(index);
    }
    
    // 移除指定索引处元素
    public E remove(int index) {
        
        // 判断异常
        Objects.checkIndex(index, size);
        // 临时变量数组赋值
        final Object[] es = elementData;
    	// 拿到指定索引处的元素
        @SuppressWarnings("unchecked") E oldValue = (E) es[index];
        fastRemove(es, index);
        return oldValue;
    }
    private void fastRemove(Object[] es, int i) {
        
        // 记录修改次数, 一般研究线程安全性问题,关注这个变量
        modCount++;
        // 定义临时变量
        final int newSize;
        // 判断数组长度-1,是否大于变量索引
        if ((newSize = size - 1) > i)
            /*
            	将es中从索引i+1位置开始,长度为newSize - i的元素
            	拷贝到从下表i + 1位置开始的新的es数组中
            	也就是当前位于该位置的元素以及后面的元素向前一定一位
            */
            System.arraycopy(es, i + 1, es, i, newSize - i);
        // 临时变量在赋值为null
        es[size = newSize] = null;
    }
    // 移除指定元素
    public boolean remove(Object o) {
        
        // 定义临时数组,并赋值
        final Object[] es = elementData;
        // 定义临时长度变量,并赋值
        final int size = this.size;
        int i = 0;
        // found标识,发现指定元素
        found: {
        
            if (o == null) {
        
                for (; i < size; i++)
                    if (es[i] == null)
                        break found;
            } else {
        
                for (; i < size; i++)
                    if (o.equals(es[i]))
                        break found;
            }
            return false;
        }
        // 移除元素并移动
        fastRemove(es, i);
        return true;
    }

## 6.总结 ##

> 从上述代码中可以看出，数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的 1.5 倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造 ArrayList 实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用 ensureCapacity 方法来手动增加 ArrayList 实例的容量。

下一篇： [ArrayList源码分析][ArrayList 1]

[ArrayList]: https://blog.csdn.net/itcast_cn/article/details/128004753?spm=1001.2101.3001.6650.1&utm_medium=distribute.pc_relevant.none-task-blog-2~default~AD_ESQUERY~yljh-1-128004753-blog-129348419.pc_relevant_3mothn_strategy_and_data_recovery&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2~default~AD_ESQUERY~yljh-1-128004753-blog-129348419.pc_relevant_3mothn_strategy_and_data_recovery&utm_relevant_index=2
[7d60ef179dce4f23a7e30155284ab743.png]: https://img-blog.csdnimg.cn/7d60ef179dce4f23a7e30155284ab743.png
[ArrayList 1]: https://blog.csdn.net/weixin_43811057/article/details/129620049?spm=1001.2014.3001.5501