ArrayList源码解析[一]

ArrayList源码解析[一]

欢迎转载，转载烦请注明出处，谢谢。

https://www.cnblogs.com/sx-wuyj/p/11177257.html

在工作中集合list集合用的相对来说比较多,而ArrayList可以说是业务端的同学天天都在用.对于ArrayList内部的机制我也是一知半解,所以决定好好看看源码.我是用IEDA去查看源码,复制一份JDK源码,然后用IDEA打开,找到对应的类,设置一个IDEA,这样可以方便你直接在代码内部添加注释.还有一点,千万别直接把你环境配置的JDK直接打开,避免在你查看源码的过程修改了某个地方,影响到你的正常项目运行.

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原理

  我们先看一下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.