JDK源码分析--ArrayList深入理解

x33g5p2x  于2021-12-18 转载在 其他  
字(8.3k)|赞(0)|评价(0)|浏览(217)

一、实现原理

JDK1.8.0_74源码为基础进行分析。

1、基于数组的实现,是一个容量能自动增长的动态数组。

2、ArrayList实现了Serializable接口,因此它支持序列化,能够通过序列化传输,实现了RandomAccess接口,支持快速随机访问,实际上就是通过下标序号进行快速访问,实现了Cloneable接口,能被克隆。

3、随着向ArrayList中不断添加元素,其容量也自动增长。自动增长会带来数据向新数组的重新拷贝,因此,如果可预知数据量的多少,可在构造ArrayList时指定其容量。

二、关键源码

(一)属性

1、默认初始容量

/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;

2、默认的空实例赋值

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

3、顾名思义,含有默认值的空实例。其和EMPTY_ELEMENTDATA有什么区别呢?

其在添加第一个元素时,会默认将Object数组的容量扩展到默认大小,即10;依个人理解,好处就是在添加10以内的元素时不需要频繁扩容;具体在下面讲构造方法时予以说明。

/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

4、实际存放元素的Object数组

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

5、存放元素的数量

/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;

(二)构造方法

1、包含初始容量的构造方法。数组大小为指定容量,如果指定为0,则数组赋值为EMPTY_ELEMENTDATA;**在添加第1个元素时,仅扩展容量为1;**继续添加元素怎么扩容呢,请看“二.(三)”。

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

2、不含初始容量的构造方法。默认赋值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA;在添加第1个元素时,会扩展容量为默认值10。

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

3、构造包含指定元素的列表,不解释。

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

(三)研究下add(E e)方法

源码:

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

讲一下第1行的“扩容”:ensureCapacityInternal(size + 1)

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

这里的“扩容”方法并非是一定有扩容的操作;如果数组为空实例且等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA时,取默认容量10和扩容参数值的最大值;然后执行容量确认方法ensureExplicitCapacity(minCapacity)。

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;//每次add()、remove()、addAll()、removeRange()及clear()方法执行时,它的值都会加1;记录ArrayList结构性变化的次数;在迭代器执行next()方法时,判断了当前的modCount跟初始化Itr时的expectedModCount是否相同,不同则说明列表数据进行了结构性改变,此时就会抛出ConcurrentModificationException。
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)//要“扩容”的值大于当前容量时,执行扩容操作
       grow(minCapacity);
}

特此说明modCount++;//每次add()、remove()、addAll()、removeRange()及clear()方法执行时,它的值都会加1;记录ArrayList结构性变化的次数;在迭代器执行next()方法时,判断了当前的modCount跟初始化Itr时的expectedModCount是否相同,不同则说明列表数据进行了结构性改变,此时就会抛出ConcurrentModificationException。

真正的扩容方法:

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);//大约增加1.5倍
    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);//将原数据复制到扩容后的数组中,赋值给elementData。
}

扩容规律,总结:当添加元素后的需要的容量X大于原容量Y时进行扩容,首先将Y扩大约1.5倍(取整)得到Z,取X和Z中的最大值作为此次扩容的实际容量。

用一个表格来展示(请先弄懂有参和无参构造方法的区别,前面有讲到):

<br>元素个数(size)<br><br>0<br><br>1<br><br>2<br><br>3<br><br>4<br><br>5<br><br>6<br><br>7<br><br>8<br><br>9<br><br>10<br><br>11<br><br>12<br><br>13<br><br>14<br><br>15<br><br>16<br>
<br>new ArrayList()<br><br>0<br><br>10<br><br>10<br><br>10<br><br>10<br><br>10<br><br>10<br><br>10<br><br>10<br><br>10<br><br>10<br><br>15<br><br>15<br><br>15<br><br>15<br><br>15<br><br>22<br>
<br>new ArrayList(0)<br><br>0<br><br>1<br><br>2<br><br>3<br><br>4<br><br>6<br><br>6<br><br>9<br><br>9<br><br>9<br><br>13<br><br>13<br><br>13<br><br>13<br><br>19<br><br>19<br><br>19<br>

(四)Arrays.copyOf(elementData, newCapacity)

Arrays类与ArrayList处在同一个包下,源码中对该类的注释为:该类包含用于操作数组的各种方法(例如排序和搜索)。该类还包含一个静态工厂允许将数组视为列表。

扩容时用到此类的copyOf()方法,源码如下:

public static <T> T[] copyOf(T[] original, int newLength) {
   return (T[]) copyOf(original, newLength, original.getClass());
}
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
               Math.min(original.length, newLength));
    return copy;
}
public static native void arraycopy(Object src,  int  srcPos,
                         Object dest, int destPos,
                         int length);

通过源码可以看到,扩容的原理其实是在创建具有新长度的数组,调用System.arraycopy()方法将原数组中的内容复制到新数组中;System.arraycopy()方法使用native修饰,调用的是系统本地方法;在openJDK中可以看到其实际是调用的是C语言的函数;memmove()函数复制效率高,Java强烈推荐在复制大批量数组元素时使用此方法。

三、应用技巧

1、元素个数确定或可预知范围时,可使用有参构造方法构造实例列表。ArrayList的频繁扩容对时间和空间都会有较大的效率影响。

2、为了避免空间浪费,在对List操作完成后可以执行trimToSize()方法,将其处理成刚好填满的状态,即容量大小为元素个数。(需要注意的是,这里不会处理掉值为null的元素)

四、其他知识

1、线程不安全。因此多线程环境下请使用如下列表:

(1)使用Collections的以下方法返回线程安全的ArrayList类

public static <T> List<T> synchronizedList(List<T> list) {
    return (list instanceof RandomAccess ?
         new SynchronizedRandomAccessList<>(list) :
         new SynchronizedList<>(list));
 }

(2)使用concurrent并发包下的CopyOnWriteArrayList类

2、Fail-Fast机制。

ArrayList采用了快速失败的机制,通过记录modCount参数来实现。在面对并发的修改时,迭代器很快就会完全失败。是对不支持并发操作的快速响应。

3、ArrayList基于数组实现,可以通过下标索引直接查找到指定位置的元素,因此查找效率高,但每次插入或删除元素,就要大量地移动元素,插入删除元素的效率低。

4、ArrayList自己实现了序列化和反序列化的方法,通过实现 private void writeObject(java.io.ObjectOutputStream s)和 private void readObject(java.io.ObjectInputStream s) 方法来对自身被transient修饰的属性进行序列化和反序列化。

五、知识延伸:几种列表实现的泛解

需要对比的列表实现:ArrayList、Vector、CopyOnWriteArrayList、Collections.synchronizedList(list)

(一)ArrayList

非线程安全,在一个线程遍历,另一个线程修改时,会报ConcurrentModificationException异常。除此之外,由于未做同步处理,可能导致数据不一致。

(二)Vector

线程安全,同样采用数组实现。其实现线程安全的的方式是在方法上添加synchronized关键字,这种方式严重影响执行效率,因此不推荐使用。

(三)Collections.synchronizedList

这个方法的源码见四.1.(1)。我们这里讨论的是ArrayList,而ArrayList实现了RandomAccess接口,因此通过Collections的这个方法返回的是SynchronizedRandomAccessList类的实例。

SynchronizedRandomAccessList继承于SynchronizedList,SynchronizedList继承于SynchronizedCollection;在SynchronizedCollection中有2个成员变量,如下:

final Collection<E> c;  // Backing Collection

final Object mutex;     // Object on which to synchronize

Collection<E> c为实际的集合;Object mutex 用于同步加锁,在每个方法中通过对mutex的加锁,达到操作c线程安全的目的。

(四)CopyOnWriteArrayList

先看源码,成员变量有2个:

/** The lock protecting all mutators */

final transient ReentrantLock lock = new ReentrantLock();

/** The array, accessed only via getArray/setArray. */

private transient volatile Object[] array;

1、关键字transient,被修饰属性不参与默认序列化,其序列化的实现通过writeObject方法和readObject方法实现。

2、使用ReentrantLock重入锁,实现线程安全。

官方说明:一个可重入的互斥锁定 Lock,它具有与使用 synchronized 方法和语句所访问的隐式监视器锁定相同的一些基本行为和语义,但功能更强大。ReentrantLock 将由最近成功获得锁定,并且还没有释放该锁定的线程所拥有。当锁定没有被另一个线程所拥有时,调用 lock 的线程将成功获取该锁定并返回。如果当前线程已经拥有该锁定,此方法将立即返回。可以使用 isHeldByCurrentThread() 和 getHoldCount() 方法来检查此情况是否发生。

3、来自网上的一段解释

CopyOnWriteArrayList:CopyOnWriteArrayList这是一个ArrayList的线程安全的变体,其原理大概可以通俗的理解为:初始化的时候只有一个容器,很常一段时间,这个容器数据、数量等没有发生变化的时候,大家(多个线程),都是读取(假设这段时间里只发生读取的操作)同一个容器中的数据,所以这样大家读到的数据都是唯一、一致、安全的,但是后来有人往里面增加了一个数据,这个时候CopyOnWriteArrayList 底层实现添加的原理是先copy出一个容器(可以简称副本),再往新的容器里添加这个新的数据,最后把新的容器的引用地址赋值给了之前那个旧的的容器地址,但是在添加这个数据的期间,其他线程如果要去读取数据,仍然是读取到旧的容器里的数据。

(五)CopyOnWriteArrayList和Collections.synchronizedList性能说明

CopyOnWriteArrayList,发生修改时候做copy,新老版本分离,保证读的高性能,适用于以读为主,读操作远远大于写操作的场景中使用,比如缓存。而Collections.synchronizedList则可以用在CopyOnWriteArrayList不适用,但是有需要同步列表的地方,读写操作都比较均匀的地方。

相关文章