ArrayList再探究

1.概述

1.问题引出

在上一篇文章,主要讲述了为什么ArrayList是线程不安全的,ArrayList为什么是线程不安全的
在源码的探究上,也仅仅是到了这个层面:

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

甚至连ensureCapacityInternal(size + 1);这个方法都没有往下看,仅仅是知道了这个方法可以在进行add操作时可以确保容量,但是一直还存在一个问题,在不指定数组容量大小时,构造函数源码是这样的:

 /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

DEFAULTCAPACITY_EMPTY_ELEMENTDATA;是ArrayList的一个成员变量,是这样婶定义的:

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

那么我的疑问就是如果不指定容量的话,那么仅仅是将DEFAULTCAPACITY_EMPTY_ELEMENTDATA;赋值给elementData数组,数组的容量怎么就是10了呢?

2.长度和容量

这里需要注意区分二者之间的概念,我们所说的size()方法,是elementData数组实际存在元素的个数,从上面的add方法源码我们也可以看到,每增加一个元素,都要进行size++的操作,而size()方法是这样的:

 /**
     * Returns the number of elements in this list.
     *
     * @return the number of elements in this list
     */
    public int size() {
        return size;
    }

而容量一定是不小于size的,是我们创建数组时指定的空间大小

2.构造函数

在看源码之前我们先来明确几个概念,不然容易懵逼:

  • initialCapacity:数组初始容量
  • minCapacity:想要插入当前元素所必须保证的最小容量
  • modCount:记录列表被修改的次数,每一次add,remove操作都会进行modCount++,这个成员变量主要在多线程中使用,我们知道ArrayList是线程不安全的,如果一个线程正在对列表使用迭代器进行迭代,另一个线程要是进行修改列表,就会引发安全性问题,这就用到了modCount

1. ArrayList(int initialCapacity)

这个构造方法用来创建一个指定容量大小的数组

 /**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    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);
        }
    }

这里需要区分一下EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA,通过上面的源码我们可以知道,当initialCapacity为0时,直接将EMPTY_ELEMENTDATA赋值给elementData,而EMPTY_ELEMENTDATA的定义是:

  /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

这种做法我个人看来非常不好,因为没有后面calculateCapacity()方法照顾,在创建好列表之后,后面执行add()操作时候扩容次数太多了,数组复制过程开销是很大的

但是DEFAULTCAPACITY_EMPTY_ELEMENTDATA可就不一样了,在下一个构造方法中讲

2.ArrayList()

用于构造一个默认初始容量为10的列表

 /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

DEFAULTCAPACITY_EMPTY_ELEMENTDATA的不同之处在于,在进行确保数组容量的ensureCapacityInternal(size + 1);中,如果见到这个变量会受到“额外”的照顾:

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

在这个 calculateCapacity方法中,如果发现elementData这个引用变量和DEFAULTCAPACITY_EMPTY_ELEMENTDATA指向的是同一数组,也就是同一块内存区域,那么在下面进行特殊照顾,直接返回Math.max(DEFAULT_CAPACITY, minCapacity);

那么我们再进行深一步的思考,什么情况下,DEFAULT_CAPACITY比较大,什么情况下minCapacity比较大呢?

  • DEFAULT_CAPACITY较大:首先创建好列表之后,如果使用add()方法进行第一次增加元素,那么这时候minCapicity = size + 1;size为0,那么minCapacity为1,此时一定DEFAULT_CAPACITY比较大
  • minCapicity比较大:但是当使用了addAll()方法时,
public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

minCapicity = size + numNew,此时如果nunmNew比较大,就会出现minCapicity更大的情况

  • 注意上面的比较情况肯定只会出现一次:当默认初始容量为10的列表创建好之后,进行第一次插入的情况,如果再出现插入的情况,那么calculateCapacity会直接返回minCapacity,因为此时这个列表经过grow(int minCapacity)方法之后,就已经不再是“应届生”,不会再进行上面那个所谓的Math.MAX比较了,所以这样来看,calculateCapacity方法只是起到了一个筛选“应届生”的作用

3.ArrayList(Collection<? extends E> c)

 /**
     * 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;
        }
    }

3.细节与总结

1.elementData的去序列化

首先我们来看elementData数组的定义:

/**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

为什么要加transient关键字呢?

我们知道transient这个关键字是去序列化的,那么这个对象数组中存储的不正是有意义的数据,为啥要去序列化呢?很好理解,因为数组中容量通常是不小于数组实际元素的,如果要是对整个数组进行序列化,那么后面空闲容量中没有意义的数据也就被序列化了,这些是不应该被存储的,所以ArrayList类实现了Serializable接口,实现了writeObject方法进行序列化,这样就可以只序列化有用的数据

private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // Write out element count, and any hidden stuff
        int expectedModCount = modCount;
        s.defaultWriteObject();

        // Write out size as capacity for behavioural compatibility with clone()
        s.writeInt(size);

        // Write out all elements in the proper order.
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }

        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

2.列表进行扩容的过程

我们以创建一个默认容量大小为10的列表并进行add()操作为例,来看一下列表扩容的过程

  • 调用ArrayList()构造方法,将elementData赋值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA

  • 创建列表实例,调用add()方法

  • 调用ensureCapacityInternal(size + 1);方法对容量进行确认

  • ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    

其中calculateCapacity用于特殊处理

  • private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
    
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
  • 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);
    }
    

由此可知,每次扩容大小为原来的1.5倍

其中hugeCapacity()方法:

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

检查新容量是否超出了ArrayList所定义的最大容量,若超出了,则调用hugeCapacity()来比较minCapacity和MAX_ARRAY_SIZE,如果minCapacity大于最大容量,则新容量则为ArrayList定义的最大容量,否则,新容量大小则为minCapacity。

还有一点需要注意的是,容量拓展,是创建一个新的数组,然后将旧数组上的数组copy到新数组,这是一个很大的消耗,所以在我们使用ArrayList时,最好能预计数据的大小,在第一次创建时就申请够内存。

3.JDK版本比较

以上源代码全部出自我的JDK1.8,1.7版本都是这样的,但是和之前的JDK1.6版本是有一些不同的,

我们来看,1.6中进行扩容是这样婶的:

/** 
       * Increases the capacity of this <tt>ArrayList</tt> instance, if 
       * necessary, to ensure that it can hold at least the number of elements 
       * specified by the minimum capacity argument. 
       * 
       * @param   minCapacity   the desired minimum capacity 
       */  
      public void ensureCapacity(int minCapacity) {  
      modCount++;  
      int oldCapacity = elementData.length;  
      if (minCapacity > oldCapacity) {  
         Object oldData[] = elementData;  
         int newCapacity = (oldCapacity * 3)/2 + 1;  
             if (newCapacity < minCapacity)  
         newCapacity = minCapacity;  
             // minCapacity is usually close to size, so this is a win:  
             elementData = Arrays.copyOf(elementData, newCapacity);  
     }  
     }  

从代码上,我们可以看出区别:

第一:在容量进行扩展的时候,1.6采用将容量乘1.5倍并加1,而jdk1.7是利用位运算,从效率上,jdk1.7之后的版本就要快于jdk1.6。

第二:在算出newCapacity时,其没有和ArrayList所定义的MAX_ARRAY_SIZE作比较,为什么没有进行比较呢,原因是jdk1.6没有定义这个MAX_ARRAY_SIZE最大容量,也就是说,其没有最大容量限制的,但是jdk1.7之后做了一个改进,进行了容量限制。

参考文章:

https://www.iteye.com/blog/zhh9106-2152419

https://blog.csdn.net/jdsjlzx/article/details/52675726

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://hadoo666.top/archives/arraylist再探究md