• 原创
  • 后端开发
  • ArrayList源码(一)

    2020.03.20 13:56发布

    6024人阅读

    0人评论

    自己学习ArrayList源码的一些心得记录..


    1.1 ArrayList的体系



    • Iterable : iterable接口里定义了返回iterator的方法,相当于对iterator的封装,同时实现了iterable接口的类可以支持for each循环;

    • Collction : 集合框架中的根接口,下面有三大子接口.List Set Queue;

    • AbstractCollection: 实现了Collection的一些接口,同时也定义了一些抽象方法交给子类实现.

    • List : List接口定义了一些公用的接口,比如 toArray() size() add()等接口;


    • AbstractList :AbstractList 是一个抽象类,实现了List接口,是隶属于Java集合框架中的根接口 Collection 的分支


      1.2 ArrayList构造方法.




        /**
    * 有参构造 int类型 集合的大小
    */

    public ArrayList(int initialCapacity) {
    //如果参数大于0,缓冲数组的大小就为该参数
    if (initialCapacity > 0) {
    this.elementData = new Object[initialCapacity];
    //如果参数等于0,创建一个空的实例数组
    } else if (initialCapacity == 0) {
    this.elementData = EMPTY_ELEMENTDATA;
    } else {
    //异常为非法容量 + 参数
    throw new IllegalArgumentException("Illegal Capacity: "+
    initialCapacity);
    }
    }

    /**
    * Constructs an empty list with an initial capacity of ten.
    * 无参构造
    */

    public ArrayList() {
    //缓冲数组为空的默认大小的共享实例
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    //有参构造 参数为任意类或者E的子类
    //任意类或者E的子类,孙子类等collection都可以构造一个ArrayList出来
    public ArrayList(Collection<? extends E> c) {
    //转为缓存数组
    elementData = c.toArray();
    //将数组的长度赋值给size,如果数组长度不等于0
    if ((size = elementData.length) != 0) {
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    //缓存数组的class不等于object类型数组的class
    if (elementData.getClass() != Object[].class)
    //copyOf方法:返回一个数组
    elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
    // replace with empty array.
    //替换为一个空的数组
    this.elementData = EMPTY_ELEMENTDATA;
    }
    }

    以上就是ArrayList的构造方法,注释是我自己一行一行写出来的,可能会有所误解,欢迎批评指正.


    1.3 arrayList常用的方法



    • add() : 向集合内部添加元素,这个方法其实是Collection接口中定义的,AbstractCollection抽象类中实现这个方法,ArrayList中重写了这个方法.如果直接调用AbstractCollection中的add方法,那么只会抛出一个不支持操作的异常.需要注意一点就是add()一共有两个,但是其中一个是有boolean的返回值,另一个是void并没有返回值.


    boolean返回值add(),元素添加是为最后一位.


        public boolean add(E e) {
    ensureCapacityInternal(size + 1); // Increments modCount!!
    elementData[size++] = e;
    return true;
    }

    首先看一下 ensureCapacityInternal(size + 1)这个方法


        private void ensureCapacityInternal(int minCapacity) {

    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    //max方法为一个三元运算,参数类型为int类型,(a >= b) ? a : b;
    //size+1 大于等于 初始值 返回初始值10
    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
    }
    又调用了ensureExplicitCapacity()方法

    private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    //需要的大小大于底层数组的大小
    if (minCapacity - elementData.length > 0)
    grow(minCapacity);
    }
    继续调用了grow()方法,这个方法很关键,先看源码

    private void grow(int minCapacity) {
    //数组长度赋值给oldCapacity
    int oldCapacity = elementData.length;
    //oldCapacity >> 1 相当于 oldCapacity / 2
    //newCapacity 为数组长度的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //newCapacity小于minCapacity
    if (newCapacity - minCapacity < 0)
    //minCapacity赋值于newCapacity
    newCapacity = minCapacity;
    //newCapacity大于MAX_ARRAY_SIZE
    if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
    //通过copyOf方法返回一个数组
    elementData = Arrays.copyOf(elementData, newCapacity);
    }

    整体来说 如果size+1小于10,那么minCapacity就是10,10就是默认大小.如果大于10,那么minCapacity则为size+1.


    minCapacity-lementData.length 如果size+1比底层数组小,那么可以继续向默认数组中添加元素.如果size+1大于底层数组,就调用grow()进行扩容.


    grow()这个方法就是arrayList自动扩容的方法.newCapacity为数组的1.5倍,先判断newCapacity是否小于
    minCapacity,也就是size+1
    如果小于那么将minCapacity赋值于newCapacity.


    再判断newCapacity是否大于MAX_ARRAY_SIZE,关于MAX_ARRAY_SIZE下面有代码.



    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;



    如果大于就调用hugeCapacity()方法


        private static int hugeCapacity(int minCapacity) {
    //minCapacity 小于 0 报错
    if (minCapacity < 0) // overflow
    throw new OutOfMemoryError();
    //minCapacity大于MAX_ARRAY_SIZE吗?
    //大于返回Integer.MAX_VALUE
    //小于返回MAX_ARRAY_SIZE
    return (minCapacity > MAX_ARRAY_SIZE) ?
    Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
    }

    最后将elementData,也就是底层数组.lenth变为newCapacity.
    总结起来说,arrayList的扩容机制其实就修改底层数组的大小.
    继续回头add()方法往下看:



    elementData[size++] = e;



    这个其实很好理解了,e就是你要添加的那个新的元素,size++就是新元素在底层数组中的位置.



    return true;
    最后返回一个 true 添加成功



    void add(),


        public void add(int index, E element) {
    //校验index
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1); // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
    size - index);
    elementData[index] = element;
    size++;
    }


    rangeCheckForAdd(index);



     private void rangeCheckForAdd(int index) {
    //如果index大于size或者index小于0 就抛出异常
    if (index > size || index < 0)
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }


    ensureCapacityInternal(size + 1);



    这个在前面有说过,就不在细说,可以去看一下前面add()带返回值的那个解析.



    System.arraycopy(elementData, index, elementData, index + 1,size - index);



    调用System提供的arraycopy(),这是一个静态native方法,native这里不进行说明,可以百度进行查看.这个方法就是现数组之间的复制。


        elementData:底层数组.
    index:数组要复制的起始位置.
    elementData:复制后的数组.
    index + 1:数组放置的起始位置.
    size - index:复制的长度


    elementData[index] = element;



    将要添加的元素放入指定的位置.



    size++



    将集合的长度+1.


    由于arrayList源码较为庞大,暂且先写一部分,后续会继续更新.


    以上博文个人手写,如果有错,希望各位大佬多多体谅,欢迎批评指正.

    举报文章

  • 收藏博客:

  • 分享至:
  • 添加评论

    请先登录再评论...

    登录

    评论列表(条评论)

    没有更多评论了