Java基础底层-ArrayList源码分析

客官°小女子只卖身不卖艺 2022-12-24 00:44 178阅读 0赞

### 一、前言 ###

> 继承了什么类，实现了什么接口？作用是什么？

实现了四个接口一个抽象类。它继承了AbstractList抽象类，实现了List、RandomAccess, Cloneable, Serializable接口  
ArrayList 继承了AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能  
ArrayList 实现了RandmoAccess接口，即提供了随机访问功能。  
ArrayList 实现了Cloneable接口，即覆盖了函数clone()，能被克隆  
ArrayList 实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输

### 二、成员变量 ###

> ArrayList属性主要是当前数组长度size和存放数组对象的elementData;除此之外还有一个经常用到的属性modCount属性，是从AbstractList继承过来的，代表ArrayList集合的修改次数。

public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    { 
    	//序列ID
        private static final long serialVersionUID = 8683452581122892189L;
    	//默认初始化容量
        private static final int DEFAULT_CAPACITY = 10;
    	//空对象，参入参数为0的容量时创建此对象
        private static final Object[] EMPTY_ELEMENTDATA = { };
    	//空对象，使用默认构造函数创建，默认对象内容就是此对象
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };
    	//当前存储数据对象的地方，当前对象不参与序列化 transient介绍看第六点
        transient Object[] elementData;    
    	// 当前数组的长度
    	private int size;
    	//数组最长的长度
    	private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    }

### 三、构造函数 ###

*  无参构造函数

// 无参构造函数；如果不传参数则默认使用无参构造函数创建ArrayList
    // 此时我们创建的对象，elementData中的长度是0，size是0，
    //当进行第一次add的时候，elementData将会变成默认的长度10
    public ArrayList() { 
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

*  带int的构造函数

//带Int类型的构造函数:指定Array List的初始数组长度没传入参数如果大于0，则使用用户的参数初始化
    //如果用户传入的参数小于0，则抛出异常，如果等于0，则创建一个空对象
    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);
        }
    }

*  带Collection对象的构造函数

// 带Collection对象的构造函数：将Collection对象转换成数组，然后将数组的地址赋值给elementData
    //更新size的值，同事判断size的大小，如果size等于0，直接将空对象EMPTY_ELEMENTDATA的地址赋值给elementData
    //如果size的值大于0，则执行Arrays.copy方法，把Collection对象的内容（可以理解为深拷贝）从copy到elementData中
    public ArrayList(Collection<? extends E> c) { 
        elementData = c.toArray();
        if ((size = elementData.length) != 0) { 
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else { 
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

### 四、扩容缩容机制 ###

##### 扩容机制 #####

扩容机制其实就是在添加元素的时候会检查数组空间大小，如果数组空间不够一般会自动扩容当前容量的1.5倍（一般是增加1.5倍；具体情况可以看源码解释）

// 增加元素的方法
    public boolean add(E e) { 
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
    //minCapacitt表示修改后的数组容量，minCapacity = size + 1
    private void ensureCapacityInternal(int minCapacity) { 
        //判断看看是否需要扩容
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

//判断当前数组是否是默认构造方法生成的空数组，如果是的话minCapacity=10
    //反之则根据原来的值传入下一个方法去完成下一步的扩容判断
    private static int calculateCapacity(Object[] elementData, int minCapacity) { 
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    
    //判断当前ArrayList是否需要进行扩容
    private void ensureExplicitCapacity(int minCapacity) { 
        modCount++;
        //可以看到如果修改后的数组容量大于当前的数组长度那么就需要调用grow进行扩容，反之则不需要
        if (minCapacity - elementData.length > 0)
           grow(minCapacity);
    }

> 核心方法： 此方法有三种情况进行扩容
> 
>  *  第一种：  
>     当前数组是由默认构造方法生成的空数组并且第一次添加数据。此时minCapacity等于默认的容量（10）  
>     那么根据下面逻辑可以看到最后数组的容量会从0扩容成10。而后的数组扩容才是按照当前容量的1.5倍进行扩容
>  *  第二种  
>     当前数组是由自定义初始容量构造方法创建并且指定初始容量为0。此时minCapacity等于0  
>     那么根据下面逻辑可以看到最后数组的容量会从0变成1。这边可以看到一个严重的问题，一旦我们执行了初始容量为0，  
>     那么根据下面的算法前四次扩容每次都 +1，在第5次添加数据进行扩容的时候才是按照当前容量的1.5倍进行扩容。
>  *  第三种  
>     当扩容量（newCapacity）大于ArrayList数组定义的最大值后会调用hugeCapacity来进行判断。  
>     如果minCapacity已经大于Integer的最大值（溢出为负数）那么抛出OutOfMemoryError（内存溢出）  
>     否则的话根据与MAX\_ARRAY\_SIZE的比较情况确定是返回Integer最大值还是MAX\_ARRAY\_SIZE。  
>     这边也可以看到ArrayList允许的最大容量就是Integer的最大值（-2的31次方~2的31次方减1）

private void grow(int minCapacity) { 
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        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);
    }
    
    private static int hugeCapacity(int minCapacity) { 
        if (minCapacity < 0) // overflow
           throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;
    }

##### 缩容机制 #####

在执行remove等删除操作都不会改变原数组的容量大小，如果需要改变数组的容量大小需要手动执行缩容的方法

public void trimToSize() { 
        modCount++;
        if (size < elementData.length) { 
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

### 五、常用方法 ###

#### 1. 增加操作 ####

add(E e)：添加一个元素到列表的末尾  
add( int index, E element ) :在指定的位置添加元素  
addAll( Collection<? extends E> c )：添加一个集合到元素的末尾.以上返回类型是

// 根据索引位置进行添加
    // 1. 先判断索引是否有无越界
    // 2. 与add方法一致；判断是否需要扩容
    // 3. 将index位置后面的数据往后移一位
    // 4. index赋值为指定的value
    public void add(int index, E element) { 
        rangeCheckForAdd(index);
    
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,size - index);
        elementData[index] = element;
        size++;
    }
    
    private void rangeCheckForAdd(int index) { 
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

#### 2. 删除操作 ####

remove(Object o)：删除列表中第一个出现O的元素  
remove( int index)：删除列表中指定位置的元素  
removeAll（Collection<?> c）：删除列表中包含C的所有元素  
removeRange( int from,int to )：删除从from到to的所有元素  
clear（）：清除所有的元素。返回类型为void  
retainAll(); 保留Collection中的所有元素  
removeAll(); 清除Collection中的所有元素

// 删除指定索引中的值 （删除操作不会改变数组容量的大小，改变的是size）
    // 1. 数组越界检查，判断索引是否越界（此处只判断上限，没有判断负数的情况下）
    // 2. modCount次数+1 （此处涉及到快速失败机制，后面会提到，目前可忽略）
    // 3. 获取要删除的值
    // 4. 将要删除的索引后面的值全部往前移
    // 5. 将最后一个值置null，方便GC进行清理
    // 6. 返回删除的值
    public E remove(int index) { 
        rangeCheck(index);
    
        modCount++;
        E oldValue = elementData(index);
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        elementData[--size] = null; // clear to let GC do its work
        return oldValue;
    }
    
    private void rangeCheck(int index) { 
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

// 此处有为null判断，说明arrayList可以存放null值
    public boolean remove(Object o) { 
    	if (o == null) { 
    		for (int index = 0; index < size; index++)
    			if (elementData[index] == null) { 
    				fastRemove(index);
    				return true;
    			}
    	} else { 
    	for (int index = 0; index < size; index++)
    		if (o.equals(elementData[index])) { 
    			fastRemove(index);
    			return true;
    		}
    	}
    	return false;
    }

// 清理，直接将数组中所有的元素置为null，GC会自动回收；然后size置为0
    public void clear() { 
        modCount++;
    
        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;
    
        size = 0;
    }

//删除参数中的元素（batchRemove可以自己看源码）
    //retainAll可以用来取交集，而removeAll可以用来排除值
    public boolean removeAll(Collection<?> c) { 
    	Objects.requireNonNull(c);
    	return batchRemove(c, false);
    }
    // 保留参数中的元素
    public boolean retainAll(Collection<?> c) { 
    	Objects.requireNonNull(c);
    	return batchRemove(c, true);
    }

#### 3. 修改操作 ####

retainAll( Collection<?> c )：仅仅保留列表中和C相同的元素，相当于&运算  
set（int index,E element）：用element替换index位置上的元素。  
sort(Comparator<? super E> c)：按照指定的排序规则排序  
subList( int from , int to )：返回从from到to之间的列表  
toArray()：将列表转化为数组  
trimToSize( )：修改当前实例的容量是列表的当前大小

//越界判断，然后修改完成后将修改前的值返回
    public E set(int index, E element) { 
            rangeCheck(index);
    
            E oldValue = elementData(index);
            elementData[index] = element;
            return oldValue;
        }

#### 4. 查询操作 ####

size()：返回此列表的元素数  
contains（Object o）：如果包含元素o,则返回为true  
get（int index）:返回指定索引的元素  
indexOf( Object o )：返回此列表中指定元素的第一次出现的索引，如果列表不包含此元素，返回-1  
lastindexOf( Object o ):返回此列表中指定元素的最后一次出现的索引，如果列表不包含此元素，返回-1  
isEmpty（）：如果列表为空，返回true.

//返回集合中为此元素的第一个下标
    public boolean contains(Object o) { 
    	return indexOf(o) >= 0;
    }
    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]))
    				return i;
    	}
    	return -1;
    }
    //返回集合中为此元素的最后一个下标
    public int lastIndexOf(Object o) { 
        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. 遍历循环 ####

iterator()：返回列表中元素的迭代器  
listIterator（）：返回列表的列表迭代器（按适当的顺序）  
listIterator(int index)：从适当的位置返回列表的列表迭代器（按照正确的顺序）

### 六、序列化介绍 ###

#### 1. 介绍 ####

> 所谓java序列化与反序列化，序列化就是将java对象以一种形式保存，比如存放硬盘，或者用于传输；反序列化就是一个逆过程  
> java规定被序列化的对象必须实现java.io.Serializable这个接口。

#### 2. 为什么elementData要加transient关键字 ####

> 此关键字的作用：被transient修饰的字段变量，序列化对象的时候，这个字段变量就不会序列化到指定的目的地中。  
> 由于elementData是个数组，每次存储的时候并不是每个空间都是有数据的，如果采用默认序列化，则会将其余的null也序列化到文件中；如果声明为transient类型，就能让虚拟机不会自行处理我们的这个数组。通过这种方式避免了浪费资源去存储没有的数据

#### 3. elementData怎么手动序列化（writeObject() 和 readObiect() 方法的作用） ####

> 序列化不会自动保存static和transient变量，如果我们要保存他们，则需要通过writeObject和readObject去手动保存；  
> 通过writeObject()方法，写入要保存的变量；通过readObject()方法读取之前保存的变量

// 此处只贴writeObject源码，readObject源码的实现与此一致
    private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException{ 
            // 在写入时，修改此对象就会抛出修改异常ConcurrentModificationException
            int expectedModCount = modCount;
            s.defaultWriteObject();
            s.writeInt(size);
            for (int i=0; i<size; i++) { 
                s.writeObject(elementData[i]);
            }
            if (modCount != expectedModCount) { 
                throw new ConcurrentModificationException();
            }
        }

#### 4. writeObject和readObject怎么被使用？ ####

> writeObject() 和 readObiect()都是私有方法，怎么被调用怎么进行序列化（后续补充）

### 七、总结 ###

1）arrayList可以存放null。  
2）arrayList本质上就是一个elementData数组。  
3）arrayList区别于数组的地方在于能够自动扩展大小，其中关键的方法就是gorw()方法。  
4）arrayList中removeAll(collection c)和clear()的区别就是removeAll可以删除批量指定的元素，而clear是全是删除集合中的元素。  
5）arrayList由于本质是数组，所以它在数据的查询方面会很快，而在插入删除这些方面，性能下降很多，有移动很多数据才能达到应有的效果  
6）arrayList实现了RandomAccess，所以在遍历它的时候推荐使用for循环