关于java:Java集合ArrayList源码分析

36次阅读

共计 8010 个字符,预计需要花费 21 分钟才能阅读完成。

其实我看到已有不少大佬写过此类文章,而且写的也比拟清晰明了,那我为什么要再写一遍呢?其实也是为了加深本人的印象,坚固本人的根底

(次要是很多文章没有写进去我想晓得的货色!!!​!!!!)


前言 

我说一下我认为怎么样能力去看懂,看透彻一个源码。

在你去剖析源码的时候,首先要会用,要明确这个工具类的作用,如果连一个工具类都蕴含哪些性能,这些性能的作用都不分明,我感觉看源码就是一种煎熬。(当然,大佬除外)

​自我洗脑中~我是大佬!我是大佬!我是大佬!(he~tui!我不配!!!)


注释

本次是基于 JDK1.8 来具体分析 ArrayList 源码

ArrayList 的概念:

动静数组,它提供了动静的减少和缩小元素,实现了 Collection 和 List 接口,灵便的设置数组的大小等益处。

每个 ArrayList 实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至多等于列表的大小。随着向 ArrayList 中一直增加元素,其容量也 主动增长

1、继承构造剖析

咱们先来看一下 ArrayList 类的继承构造:

Java 反对单继承,多实现

AbstractList<E>

形象接口类,目标是应用抽象类中曾经实现的办法。

咱们点开 AbstractList<E> 源码,会看到其实 AbstractList<E> 曾经也实现了 List<E> 接口,为什么要先继承 AbstractList<E>,而让 AbstractList 先实现 List<E>?而不是让 ArrayList 间接实现 List<E>?

这里是有一个思维,接口中全都是形象的办法,而抽象类中能够有形象办法,还能够有具体的实现办法,正是利用了这一点,让 AbstractList<E> 实现接口中一些通用的办法,而如 ArrayList 就继承这个 AbstractList 类,拿到一些通用的办法,而后本人在实现一些本人特有的办法,这样一来,让代码更简洁,就继承构造最底层的类中通用的办法都抽取进去,先一起实现了,缩小反复代码。所以个别看到一个类下面还有一个抽象类,应该就是这个作用。

List<E>

应用 List 的接口标准

RandomAccess

这个是一个标记性接口,通过查看 api 文档,它的作用就是用来疾速随机存取,无关效率的问题,在实现了该接口的话,那么应用一般的 for 循环来遍历,性能更高,例如 arrayList。而没有实现该接口的话,应用 Iterator 来迭代,这样性能更高,例如 linkedList。所以这个标记性只是为了让咱们晓得咱们用什么样的形式去获取数据性能更好。

Cloneable

目标是应用 clone 办法。想具体理解此办法的,点击这里,这篇文章写的还是不错的 Cloneable~~

Serializable

实现该序列化接口,表明该类能够被序列化,什么是序列化?简略的说,就是可能从类变成字节流传输,而后还能从字节流变成原来的类。

???????????????? 为什么 AbstractList 曾经实现了 List,ArrayList 还要再实现一次呢?

  • 其实 ArrayList 再去实现一次 List 在这里并没有什么实际意义,这其实是一个谬误,因为作者写这代码的时候感觉这个会有用途,然而其实并没什么用,但因为没什么影响,就始终留到了当初。有趣味的同学能够去钻研一下。

2、类剖析 

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * 缺省容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 有参结构缺省空数组
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 无参结构缺省空数组
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 数组元素(实际操作的数组,新增,删除等办法都是在此数组产生操作)*/
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * 理论数组的大小
     */
    private int size;

    /**
     * 数组的最大容量
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 

这里剖析几个中央:

(1)为什么数组最大容量是Integer.MAX_VALUE – 8,而不是Integer.MAX_VALUE

其实源码中给了备注:意思应该是有些虚拟机在数组中保留了一些头信息。防止内存溢出!

 /**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

(2)为什么定义了 两个空数组

首先定义空数组的根本原因是 优化解决,如果一个利用中有很多这样 ArrayList 空实例的话,就会有很多的空数组,无疑是为了优化性能,所有 ArrayList 空实例都指向同一个空数组。两者都是用来缩小空数组的创立,所有空 ArrayList 都共享空数组。两者的区别次要是用来起辨别作用,针对有参无参的结构在扩容时做辨别走不同的扩容逻辑,优化性能。

(3)elementData为什么定义成transient?

具体起因看这里:elementData 定义为 transent 的起因

3、构造方法

Array List 总共有三个构造方法,上面咱们一一剖析

1)无参构造方法 ArrayList()

 /**
     * 将空数组初始化大小为 10(将空数组初始化大小为 10,具体在什么时候初始化大小为 10,待会儿会说到)
     */
    public ArrayList() {
        // 将 elementData 元素数组初始化为空数组
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

无参构造方法中,将元素数组 elementData 初始化为空数组。(留神:这里就体现了我上文说到的,为什么定义两个空数组)

2)有参构造方法 ArrayList(int)

 /**
     * 结构一个具备指定初始容量的列表
     *
     * @param  initialCapacity: 初始化数组的值
     */
    public ArrayList(int initialCapacity) {
        // 如果初始化的值大于 0,则给定 elementData 一个长度为 initialCapacity 的数组
        if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) { // 如果初始化的值等于 0,则初始化为空数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else { // 否则(小于 0 的状况)抛出异样
            throw new IllegalArgumentException("Illegal Capacity:"+
                                               initialCapacity);
        }
    }

3)有参构造方法 ArrayList(Collection<? extends E> c)

 /**
     * 结构一个指定元素的汇合(此办法不太罕用)
     * @param c 
     */
    public ArrayList(Collection<? extends E> c) {
        // 将汇合转换为数组并赋值给 elementData
        elementData = c.toArray();
        // 如果汇合的大小不为 0
        if ((size = elementData.length) != 0) {// 如果转换后的数组不是泛型(object),则须要用 Arrays 的工具转换一下为 object 数组(这里不再对 Arrays.copyOf 开展阐述)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else { // 否则初始化 elementData 为一个空数组
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

对于以后构造方法,我举个例子,更清晰明了

4、罕用办法源码剖析

boolean add(E e)

重中之重,ArrayList 的外围神秘!!!!

 /**
     * 在数组中减少一个元素
     * @param e 元素对象
     */
    public boolean add(E e) {
        // 确定外部容量是否够用,size 是元素数组中数据的个数,因为要增加一个元素,所以 size+1,先判断 size+ 1 的这个个数数组是否放得下,就在这个办法中去判断是否数组.length 是否够用了。ensureCapacityInternal(size + 1); 
        // 将元素 e 赋值到 elementData 开端
        elementData[size++] = e;
        return true;
    }

    // 此办法能够了解为直达计算
    private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private static int calculateCapacity(Object[] elementData, int minCapacity) {// 判断数组是不是空数组, 如果是空数组(此时 minCapacity = 0 + 1 = 1),就将 minCapacity 初始化为 10,但此时仅仅是返回要初始化数组的大小,并没有真正初始化数组为 10
        // private static final int DEFAULT_CAPACITY = 10;
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {// Math.max(参数 1,参数 2)办法的意思是返回参数中最大的数,如果是空数组是,此时返回的是 10
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        // 如果初始化的汇合不是空,则返回元素数组的 size + 1
        return minCapacity;
    }
    
    // 别放心 我有奥秘全自动(奥秘洗衣粉~全国人民都晓得~~)
    private void ensureExplicitCapacity(int minCapacity) {
        // 构造变动记录 +1 在父类 AbstractList 中定义了一个 int 型的属性:modCount,记录了 ArrayList 结构性变动的次数
        modCount++;
        
        // 判断数组是否够用,如果不够用,则主动扩容
        // 1、当初始化的汇合为空数组时,此时 minCapacity 是 10,而 elementData 的长度为 0,所以须要扩容
        // 2、当初始化的汇合不为空是,也就是给定了大小,或曾经初始化了元素,此时的 minCapacity = 理论数组个数 +1,此时判断汇合不够用,也须要进行扩容,否则元素会溢出
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    // 主动扩容
    private void grow(int minCapacity) {// oldCapacity:元素数组的理论长度(即裁减前的数组大小)
        int oldCapacity = elementData.length;
        // oldCapacity 扩容 1.5 倍赋值给 newCapacity(>> 为右移运算符,相当于除以 2 即 oldCapacity/2)
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果初始化为空的状况,则将数组扩容为 10,此时才是真正初始化元素数组 elementData 大小为 10
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 如果 1.5 倍的数组大小超过了汇合的最大长度,则调用 hugeCapacity 办法,从新计算,也就是给定最大的汇合长度
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 曾经确定了大小,就将元素 copy 到 elementData 元素数组中~~
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        // 内存溢出判断
        if (minCapacity < 0)
            throw new OutOfMemoryError();
        // 这里的逻辑为:如果须要扩容的大小比数组的最大值都大,就返回 Integer,MAX_VALUE(int 最大值), 否则返回汇合的最大值(int 最大值 -8)
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

void add(int index, E element)

减少元素到指定下标

 /**
     * 减少元素到指定下标
     *
     * @param index 下标
     * @param element 元素
     */
    public void add(int index, E element) {
        // 参数校验
        rangeCheckForAdd(index);
        // 此办法不再赘述,参考上文 Add 办法重的阐述
        ensureCapacityInternal(size + 1);
        // 请看上面代码块的正文
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        // 将指定元素笼罩到指定下标
        elementData[index] = element;
        // 长度 size + 1
        size++;
    }

    /**
     * 实用于 add 和 addAll 的校验办法
     */
    private void rangeCheckForAdd(int index) {if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

System.arraycopy 办法解析

 /**
     * System 提供了一个静态方法 arraycopy(), 咱们能够应用它来实现数组之间的复制
     * 函数为:public static native void arraycopy(Object src,int srcPos,Object dest, int destPos,int length);* @param      src      the source array. 源数组
     * @param      srcPos   starting position in the source array. 源数组的起始地位
     * @param      dest     the destination array. 指标数组
     * @param      destPos  starting position in the destination data. 指标数组的起始地位
     * @param      length   the number of array elements to be copied. 复制的长度
         
    // 举个例子
    public static void main(String[] args){int[] arr = {1,2,3,4,5};
        int[] copied = new int[10];
        System.out.println(Arrays.toString(copied));

        System.arraycopy(arr, 0, copied, 1, 5);// 5 是复制的长度

        System.out.println(Arrays.toString(copied));

    }
   输入后果为:[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    [0, 1, 2, 3, 4, 5, 0, 0, 0, 0] 

boolean remove(Object o)

依据元素进行删除

 public E remove(int index) {
        // 参数校验
        rangeCheck(index);
        // 构造变动记录 +1
        modCount++;
        // 获取旧数据,返回给开发人员,目标是让开发人员晓得删除了哪个数据
        E oldValue = elementData(index);
        // 计算须要元素须要挪动的次数
        int numMoved = size - index - 1;
        if (numMoved > 0)
            // 同上文叙述
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // 将最初一个元素置为空(元素前移,最初一地位为空),让 GC 回收
        elementData[--size] = null;

        return oldValue;
    }

     private void rangeCheck(int index) {if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

void clear()

清空集合

 /**
     * 清空集合
     */
    public void clear() {
        modCount++;

        // 将数组置为空,促使 GC 回收
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

E get(int index)

返回此列表中指定地位上的元素 

 /**
     * 查看给定的索引是否在范畴内。如果没有,则抛出一个适当的运行时异样。* @param index : 下标
     */
    public E get(int index) {
        // 校验下标有效性
        rangeCheck(index);
        // 返回元素数组中指定 index 地位的数据
        return elementData(index);
    }
 
   
    private void rangeCheck(int index) {
        // 如果下标大于理论数组长度(元素数组最初一个数据下标为 size-1)if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

E set(int index, E element) 

 /**
     * 笼罩相应下标的数据
     * @param index 下标
     * @param element 元素数据
     */
    public E set(int index, E element) {// 校验办法(不再解释,与 get 办法中一样)
        rangeCheck(index);
        // 获取到旧数据,这里将旧数据返回进来,为了让开发者晓得替换的是哪个值
        E oldValue = elementData(index);
        // 将指定下标笼罩为新元素
        elementData[index] = element;
        return oldValue;
    }


结尾

其实 ArrayList 中还有很多很多办法,这里就不在一一叙述了,因为你了解了本文中所说的源码,其实其它再去了解,再去查看,是比拟容易简略的。

本篇文章就讲到这里,如果有写的不好的中央,请多多指教,我是凶恶的小黑哥,心愿与大家共同进步!!

正文完
 0