• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

ArrayList源码分析笔记

JAVA相关 pgrightwu 1205次浏览 0个评论

ArrayList源码分析笔记

先贴出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;

    /**
     * 用于空实例的共享空数组实例.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 共享的空数组实例,用于默认大小的空实例。我们将此与EMPTY_ELEMENTDATA区别开来,
       以了解添加第一个元素时需要膨胀多少。
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 存储ArrayList的元素的数组缓冲区。 ArrayList的容量是此数组缓冲区的长度。添加第
       一个元素时,任何具有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空
       ArrayList都将扩展为DEFAULT_CAPACITY。
     */
    transient Object[] elementData; 

    /**
     * ArrayList的大小(它包含的元素数).
     *
     * @serial
     */
    private int size;

以上属性注释都已经被翻译成中文,通过这些注释,我们大概能了解到的一些有价值的信息

  • ArrayList底层数据结构是一个Object数组

  • ArrayList的默认初始化容量为10

  • 一个空的ArrayList集合在添加第一个元素时被扩容为10

  • ArrayList的大小是通过一个名为size的int变量存储的

源码继续往下看,先看ArrayList的构造函数

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);
        }
    }

    /**
     * 通过这里可以看出,当调用ArrayList的无参构造函数时,这个ArrayList的Object数组被初始化为			   DEFAULTCAPACITY_EMPTY_ELEMENTDATA=10
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    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;
        }
    }

可以看到ArrayList一共有三个构造函数,一个无参构造,两个有参构造。

当我们在创建一个Arraylist集合时,如果不指定容量,也就是调用无参构造函数,那么这个Arraylist会被初始化为10.

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

另外注意到另外两个有参构造,一个参数为int initialCapacity,也就是我们指定的初始化容量,这里对这个initialCapacity进行了一些简单的验证

public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {//initialCapacity > 0
            this.elementData = new Object[initialCapacity];//将一个容量为initialCapacity的新Object数组赋给elementData。
        } else if (initialCapacity == 0) {//initialCapacity==0
            this.elementData = EMPTY_ELEMENTDATA;//将EMPTY_ELEMENTDATA这个空object赋给elementData
        } else {//其他情况,也就是小于0,直接抛异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

另一个有参构造

    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();//将Collection集合转化为数组,然后赋给elementData这个object数组
        if ((size = elementData.length) != 0) {//如果这个集合长度不为0
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)//如果集合转化后的数组不是Object数组
                elementData = Arrays.copyOf(elementData, size, Object[].class);//转化为Object数组
        } else {//其他情况,也就是elementData的长度为0嘛
            // 替换为EMPTY_ELEMENTDATA空的数组
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

可以看到这个构造函数,它是直接把一个Collection丢了进去,这也就是说,在new一个ArrayList时我们可以把一个Collection集合放到参数列表中。

接下来再来看ArrayList的add方法

 /**
     * 将元素添加到列表的末尾
     *
     * @param e 要被追加到list中的元素
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;//将元素e添加到数组中,下标为size++,其实也就是size,然后添加后size+1,
        return true;
    }

这里就两行代码,调用ensureCapacityInternal这个方法,并且参数为size+1。点进去看下ensureCapacityInternal()这个方法

/*
	通过这个方法我们可以看出,当我们第一次调用add方法的时候,elementData数组的size为0,那么size+1就为1,所以minCapacity也为1,这里先通过一个if判断,判断minCapacity是不是一个空的object数组,如果是的话,minCapacity就取DEFAULT_CAPACITY和minCapacity的最大值,也就是10嘛
*/
private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
    //判断完之后进入了这个方法,同时参数为minCapacity,如果是第一次调用add方法的话参数为minCapacity就是默认大小10,不是第一次调用的话,就是size+1,
        ensureExplicitCapacity(minCapacity);
    }


    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
//这个grow()就是扩容函数,现在minCapacity的话,还是一样的分析,如果第一次调用add方法的话就是10,同时elementData.length为0,不是第一次调用的话minCapacity就是size+1,elementData.length也就是数组的长度为size
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

读完这一段源码,可以得出以下结论

  • 当我们创建ArrayList时,如果不指定ArrayList的大小,那么第一次调用add方法时,底层会调用扩容方法grow()对Arraylist进行扩容
  • 当ArrayList里面已经存满了元素的时候,再调用add方法,此时会底层会调用grow方法进行扩容,比如ArrayList的大小为10,里面也已经有10个元素了,当我们再调用add方法向里面添加元素的时候,此时Arraylist会触发扩容。

接下来我们再来看下grow方法,了解一些Arraylist到底是怎么样扩容的

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
    	//如果数组当前长度+数组当前长度/2 < 数组当前元素个数+1
        if (newCapacity - minCapacity < 0)
         //就把数组当前元素个数+1赋给newCapacity
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 最后我们可以看到,这里进行了一个复制操作,将elementData里面的元素,复制到一个新的长度为newCapacity的Object数组,然后再把它赋给elementData
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

这段代码应该很清晰吧,grow方法传进来的参数就是上面minCapacity,第一次调用add方法时是10,其他时候调用时是size+1(当前存储元素个数+1)

这里简单来说就是将elementData当前长度给oldCapacity,然后newCapacity = oldCapacity + oldCapacity >> 1(左移操作,相当于除于2),如果oldCapacity = 10的话,newCapacity = 10 +(10/2),也就是15。通过以上代码,不难看出,ArrayList的扩容方法实际上就是将底层Object数组复制到了一个新的长度更长的数组里面去,而这个新数组的长度是原来的数组长度+原来数组长度的二分之一,其实就可以说了扩容了1.5倍。

通过对以上源码进行分析,我们可以得出以下结论了

总结:

  • ArrayList底层数据数据结构是一个Object类型的数组
  • ArrayList的默认初始化容量为10
  • 当我们在创建ArrsyList时不指定ArrsyList初始大小,第一次调用add方法时扩容为初始化大小10
  • ArrayList的大小是通过一个名为size的int变量存储的
  • ArrayList有一个构造函数允许Collection集合作为参数,并且会将这个Collection集合转化为数组
  • ArrayList在添加第elementData.length+1个元素时会发生扩容,比如数组长度为10,在添加第11个元素时扩容
  • ArrayList扩容大小为原来的1.5倍,底层实现是通过原来数组长度+原来数组长度左移1位完成,而不是直接通过乘法


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明ArrayList源码分析笔记
喜欢 (0)

您必须 登录 才能发表评论!

加载中……