Java集合之ArrayList源码解析(上)

ArrayList

ArrayList是List接口的 可变数组的实现。实现了所有可选列表操作,并允许包括 null 在内的所有元素。除了实现 List接口外,此类还提供一些方法来操作内部用来存储列表的数组的大小。ArrayList继承自 AbstractList<E>,这是一个抽象类对一些基础的list操作做了一些封装.实现了RandomAccess 标记接口,表明可以实现快速随机访问.实现了Cloneable接口的实现表示该容器具有Clone函数操作,Serializable是序列化。

每个ArrayList实例都有一个容量,该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素,其容量也自动增长。自动增长会带来数据向新数组的重新拷贝,因此,如果可预知数据量的大小,就可在构造ArrayList实例时指定其容量。

在添加大量元素前,应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量,这可以减少递增式再分配的数量。

注意,此实现不是同步的。如果多个线程同时访问一个ArrayList实例,而其中至少一个线程从结构上修改了列表,那么它必须保持外部同步。

ArrayList这个数据结构比较简单,总体来说,ArrayList底层结构是数组,他的很多方法都是从数组上面演变而来的。

下面我们先来看一下ArrayList中的一些初始值
//通过ArrayList实现的接口可知,其支持随机访问,能被克隆,支持序列化
publicclassArrayList<E> extendsAbstractList<E>
       implementsList<E>, RandomAccess, Cloneable, java.io.Serializable
{
   //序列版本号
   privatestaticfinallong serialVersionUID = 8683452581122892189L;

  //默认初始容量
   privatestaticfinalint DEFAULT_CAPACITY = 10;

   //空实例的共享空数组实例
   privatestaticfinal Object[] EMPTY_ELEMENTDATA = {};

   //被用于默认大小的空实例的共享数组实例。
   //与EMPTY_ELEMENTDATA的区别是:
   //当我们向数组中添加第一个元素时,知道数组该扩充多少。
   privatestaticfinal Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

   /**
    * Object[]类型的数组,保存了添加到ArrayList中的元素。
    *ArrayList的容量是该Object[]类型数组的长度
    * 当第一个元素被添加时,任何空ArrayList中的elementData
     *== DEFAULTCAPACITY_EMPTY_ELEMENTDATA将会被
    * 扩充到DEFAULT_CAPACITY(默认容量)。
    */
  transient Object[] elementData;
  //没有被私有化是为了简化内部类访问

   // ArrayList的大小(指其所含的元素个数)
   privateint size;
 
 // 记录被修改的次数  
 protectedtransientint modCount = 0;  
 
 // 数组的最大值  
 privatestaticfinalint MAX_ARRAY_SIZE = Integer.MAX_VALUE – 8  

}

elementData 是”Object[] 类型的数组”,它保存了添加到ArrayList中的元素。实际上,elementData是个动态数组,我们能通过构造函数 ArrayList(intinitialCapacity)来执行它的初始容量为initialCapacity;如果通过不含参数的构造函数ArrayList()来创建ArrayList,则elementData的容量默认是10。elementData数组的大小会根据ArrayList容量的增长而动态的增长。

构造函数

ArrayList提供了三种方式的构造器。可以构造一个默认初始容量为10的空列表、构造一个指定初始容量的空列表以及构造一个包含指定collection的元素的列表。

这些元素按照该collection的迭代器返回的顺序排列的。

// 构造一个指定初始容量的空列表
publicArrayList(int initialCapacity){
 if (initialCapacity > 0) {
   this.elementData = new Object[initialCapacity];
 } elseif (initialCapacity == 0) {
   this.elementData = EMPTY_ELEMENTDATA;
 } else {              
 // 如果给定的初始容量为负值
   thrownew IllegalArgumentException(“Illegal Capacity: “+
                      initialCapacity);
 }
}

// 构造一个默认初始容量为10的空列表
publicArrayList(){  
//这里并没有初始化,jdk 1.8之后是在进行add操作后初始化
 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 构造一个包含指定collection的元素的列表,
//这些元素按照该collection的迭代器返回的顺序排列的
publicArrayList(Collection<? extends E> c){
 elementData = c.toArray();
 if ((size = elementData.length) != 0) {
   // c.toArray()可能不会正确地返回一个 Object[]数组,
   //那么使用Arrays.copyOf()方法
   if (elementData.getClass() != Object[].class)
     elementData = Arrays.copyOf(elementData, size, Object[].class);
 } else {    
 // 如果指定的collection为空
   this.elementData = EMPTY_ELEMENTDATA;
 }
}

使用无参构造器,默认初始容量为什么是10?
  1. 初始时:this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; size = 0;
  2. 向数组中添加第一个元素时,add(E e)方法中调用了ensureCapacityInternal(size + 1)方法,即ensureCapacityInternal(1);
  3. 在ensureCapacityInternal(int minCapacity)方法中,minCapacity=DEFAULT_CAPACITY=10,然后再调用ensureExplicitCapacity(minCapacity)方法,即ensureExplicitCapacity(10);
  4. 在ensureExplicitCapacity(minCapacity)方法中调用grow(minCapacity)方法,即grow(10),此处为真正具体的数组扩容的算法,在此方法中,通过elementData = Arrays.copyOf(elementData, 10)具体实现了elementData数组初始容量为10的构造。


添加元素

// 在数组末尾加上一个元素
publicbooleanadd(E e){
 ensureCapacityInternal(size + 1);  
 // 进行扩容检查
 elementData[size++] = e;
 returntrue;
}

// 在数组的指定位置添加元素
publicvoidadd(int index, E element){
 rangeCheckForAdd(index);  
 // 检查index是否越界

 ensureCapacityInternal(size + 1);  
 // 进行扩容检查
 
 // 对数据进行复制操作,空出index位置,并插入element,
 //将源数组中从index位置开始后的size-index个元素统一后移一位
 System.arraycopy(elementData, index, elementData, index + 1,
          size – index);
 elementData[index] = element;
 size++;    
 // 元素个数加1
}

// 按照指定collection集合的迭代器所返回的元素顺序,
//将该collection中的所有元素添加到列表的尾部
publicbooleanaddAll(Collection<? extends E> c){
 Object[] a = c.toArray();      
 // 将collection转换为数组类型
 int numNew = a.length;        
 // collection中的元素个数
 ensureCapacityInternal(size + numNew);  
 // 进行扩容检查
 System.arraycopy(a, 0, elementData, size, numNew);    
 // 将数组a[0,…,numNew-1]复制到数组elementData[size,…,size+numNew-1]
 size += numNew;
 return numNew != 0;
}

// 按照指定collection集合的迭代器所返回的元素顺序,
//将该collection中的所有元素添加到列表的指定位置
publicbooleanaddAll(int index, Collection<? extends E> c){
 rangeCheckForAdd(index);    
 // 检查index是否越界

 Object[] a = c.toArray();
 int numNew = a.length;
 ensureCapacityInternal(size + numNew);  
 // 进行扩容检查

 // 将数组elementData[index,…,index+numMoved-1]复制到
 //elementData[index+numMoved,…,index+2*numMoved-1]
   //将源数组中从index位置开始的后numMoved个元素统一后移numNew位
 int numMoved = size – index;
 if (numMoved > 0)    
   System.arraycopy(elementData, index, elementData, index + numNew,
            numMoved);

 // 将数组a[0,…,numNew-1]复制到数组elementData[index,…,
 //index+numNew-1]完成数据的插入          
 System.arraycopy(a, 0, elementData, index, numNew);
 size += numNew;
 return numNew != 0;

}

扩容相关

// 用于自定义设置ArrayList的容量
publicvoidensureCapacity(int minCapacity){
 int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
   ? 0
   : DEFAULT_CAPACITY;

 if (minCapacity > minExpand) {
   ensureExplicitCapacity(minCapacity);
 }
}

// 进行扩容检查
privatevoidensureCapacityInternal(int minCapacity){
 //第一次add操作初始化,如果为空ArrayList,那么初始化容量为10
 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
   minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
 }
 //判断是否需要扩容
 ensureExplicitCapacity(minCapacity);
}

//判断是否需要扩容
privatevoidensureExplicitCapacity(int minCapacity){
 //modCount这个参数运用到了 fail-fast 机制
 modCount++;
 
 if (minCapacity – elementData.length > 0)
   grow(minCapacity);   // 扩容
}

// 扩容
privatevoidgrow(int minCapacity){
 int oldCapacity = elementData.length;
 //newCapacity为以前的1.5倍
 int newCapacity = oldCapacity + (oldCapacity >> 1);
 if (newCapacity – minCapacity < 0)
   newCapacity = minCapacity;
 //判断容量是否到达long int 最大临界值
 if (newCapacity – MAX_ARRAY_SIZE > 0)
   newCapacity = hugeCapacity(minCapacity);
 // 对数组进行复制处理
 elementData = Arrays.copyOf(elementData, newCapacity);
}

// 检查是否超过最大容量 0x7fffffff ,是否抛出异常
privatestaticinthugeCapacity(int minCapacity){
 if (minCapacity < 0) // overflow
   thrownew OutOfMemoryError();
 return (minCapacity > MAX_ARRAY_SIZE) ?
   Integer.MAX_VALUE :
   MAX_ARRAY_SIZE;
}

删除元素

// 删除指定位置的元素
public E remove(int index){
 rangeCheck(index);    
 //数组越界检查
 modCount++;
 E oldValue = elementData(index);
 int numMoved = size – index – 1;      
 //计算数组需要复制的数量
 if (numMoved > 0)  
 //将index后的数据都向前移一位
   System.arraycopy(elementData, index+1, elementData, index,
            numMoved);

 elementData[–size] = null;  
 //help  GC
 return oldValue;
}

// 删除指定内容的元素(只删除第一个匹配成功的)
publicbooleanremove(Object o){
 if (o == null) {
   for (int index = 0; index < size; index++)
     if (elementData[index] == null) {
       fastRemove(index);
       returntrue;
     }
 } else {
   for (int index = 0; index < size; index++)
     if (o.equals(elementData[index])) {
       fastRemove(index);
       returntrue;
     }
 }
 returnfalse;
}

//找到对应的元素后,删除。删除元素后的元素都向前移动一位
privatevoidfastRemove(int index){
 modCount++;
 int numMoved = size – index – 1;
 if (numMoved > 0)    
 // 将index后面的元素整体向前移动一位
   System.arraycopy(elementData, index+1, elementData, index,
            numMoved);
 elementData[–size] = null;
 // help GC
}

//清空ArrayList,将全部的元素设为null
publicvoidclear(){
 modCount++;

 for (int i = 0; i < size; i++)    
 // help  GC
   elementData[i] = null;

 size = 0;
}

//删除ArrayList中从fromIndex到toIndex(区间–左闭右开)之间所有的元素
protectedvoidremoveRange(int fromIndex, int toIndex){
 modCount++;
 int numMoved = size – toIndex;  
 //需向前移动的元素的个数
 System.arraycopy(elementData, toIndex, elementData, fromIndex,
          numMoved);

 // help GC
 int newSize = size – (toIndex-fromIndex);
 for (int i = newSize; i < size; i++) {
   elementData[i] = null;
 }
 size = newSize;
}

//删除ArrayList中包含在指定容器c中的所有元素
publicbooleanremoveAll(Collection<?> c){
 Objects.requireNonNull(c);  
 //检查指定的对象c是否为空
 return batchRemove(c, false);
}

//移除ArrayList中不包含在指定容器c中的所有元素,
//与removeAll(Collection<?> c)正好相反
publicbooleanretainAll(Collection<?> c){
 Objects.requireNonNull(c);    
 //检查指定的对象c是否为空
 return batchRemove(c, true);
}

// 根据complement的值删除元素
privatebooleanbatchRemove(Collection<?> c, boolean complement){
 final Object[] elementData = this.elementData;
 int r = 0, w = 0;    
 //读写双指针  w是重新存元素时的索引,r是原来的索引
 boolean modified = false;
 try {
   //遍历数组,并检查这个集合是否包含对应的值,
      //移动要保留的值到数组前面,w最后值为要保留的元素的数量
   //简单点:若保留,就将相同元素移动到前段;若删除,就将不同元素移动到前段
   for (; r < size; r++)
     if (c.contains(elementData[r]) == complement)  
     //判断指定容器c中是否含有elementData[r]元素
       elementData[w++] = elementData[r];
 }finally {//确保异常抛出前的部分可以完成期望的操作,
       //而未被遍历的部分会被接到后面
   //r!=size表示可能出错了:c.contains(elementData[r])抛出异常
   if (r != size) {
     System.arraycopy(elementData, r,elementData, w,size – r);
     w += size – r;
   }
   //如果w==size:表示全部元素都保留了,
   //所以也就没有删除操作发生,
   //所以会返回false;反之,返回true,并更改数组
   //而w!=size的时候,即使try块抛出异常,也能正确处理异常抛出前的操作,
   //因为w始终为要保留的前段部分的长度,数组也不会因此乱序
   if (w != size) {
     for (int i = w; i < size; i++)
       elementData[i] = null;
     modCount += size – w;//改变的次数
     size = w;  
     //新的大小为保留的元素的个数
     modified = true;
   }
 }
 return modified;

}


removeAll和retainAll方法:实现删除或保留ArrayList中包含Collection c中的的元素。

这两个方法都用到batchRemove方法(boolean complement使得batchRemove方法得到了重用)

下面以removeAll为例,分析batchRemove(c, false)

遍历elementData
如果集合c中包含elementData的元素e,则c.contains(elementData[r])为true,if不成立,if结束;如果c不包含elementData的元素e,则if成立,将此元素e赋值给elementData[w++] (即elementData保留了c中没有的元素,也就是删除了c中存在的所有元素。)

执行finally
finally是不管try中结果如何都会执行的。if(r!=size),则将elementData未参加比较的元素arraycopy到elementData后面;新索引w加上刚arraycopy的数目;if (w != size),此时w还不等于size,则将w后的元素移除.只有执行了if (w != size)(事实上只要c中含有elementData的元素,w肯定不等于size),才令modified = true,才说明remove成功,返回true,否则返回false。

ArrayList中还有一个用于节约数组内存空间,缩小容量的方法
// 因为容量常常会大于实际元素的数量。内存紧张时,
//可以调用该方法删除预留的位置,调整容量为元素实际数量。
// 如果确定不会再有元素添加进来时也可以调用该方法来节约空间
publicvoidtrimToSize(){
 modCount++;
 // length是数组长度,size表示数组内元素个数  
   // size<length那么就说明数组内有空元素,进行缩小容量操作  
 if (size < elementData.length) {
   elementData = (size == 0) ?
   EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size);
 }
}

去掉预留元素的位置。返回一个新数组,新数组不含null,数组的size和elementData.length相等,以节省空间。此函数可避免size很小但elementData.length很大的情况。

ArrayList会每次增长会预申请多一点空间,1.5倍,这样就会出现当size() = 10的时候,ArrayList已经申请了15空间, trimToSize就是删除多余的5,只留10。

或许有人会有疑问:
调用Arrays.copyOf复制size长度的元素到elementData,而且由源码看应该是从0复制到size处,那么如果我之前调用过add(int index, E element)呢?比如,list={1,2,3,null,null,4,null,null},如果调用trimToSize返回的应该是list={1,2,3,null}(因为size=4)。其实上面这种情况不会发生的,因为调用add(int index, E element)时,会检查index的合法性,所以list的元素肯定是相邻的,而不会出现上述这种中间出现null的情况。

本站所有文章均来自互联网,如有侵权,请联系站长删除。极客文库 » Java集合之ArrayList源码解析(上)
分享到:
赞(0)

评论抢沙发

评论前必须登录!