ArrayList源码分析

  • Z时代
  • 2024-01-10
  • 分类：综合

coding

简介

List接口的可变大小数组实现（动态数组）。允许null值。此类与Vector大致等效，但它是不同步的。
所有的操作大致是线性的，加入一个元素需要O(1)时间，加入n个元素需要O(n)时间。
此实现未同步。如果多个线程同时访问ArrayList实例，并且至少有一个线程在结构上修改了该列表，则必须在外部进行同步。
可以这样构造同步集合：Collections.synchronizedList(new ArrayList(…)) 或者使用Vector
迭代器支持快速失败。

类继承关系


Serializable (标志接口) 可以被序列化网络传输
RandomAccess(标志接口)可以随机访问 并且for循环遍历优于迭代器
Cloneable(标志接口)能被克隆
继承AbstractList 抽象类 实现List接口

属性

//默认容量
privatestaticfinalint DEFAULT_CAPACITY =10;
//当size=0的时候设置元素
privatestaticfinal Object[] EMPTY_ELEMENTDATA ={};
//用以实例化默认创建的实例
privatestaticfinal Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA ={};
//存储元素的数组
transient Object[] elementData;
//集合中包含多少元素
privateint size;
//最大容量
privatestaticfinalint MAX_ARRAY_SIZE = Integer.MAX_VALUE -8;

构造方法

publicArrayList(){
//初始化元素为空数组
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
publicArrayList(int initialCapacity){
if(initialCapacity >0){
//如果传入容量大于0 创建一个对应长度的数组
this.elementData =newObject[initialCapacity];
}elseif(initialCapacity ==0){
//如果传入容量为0 使用默认数组初始化
this.elementData = EMPTY_ELEMENTDATA;
}else{
thrownewIllegalArgumentException("Illegal Capacity: "+ initialCapacity);
}
}
publicArrayList(Collection<?extendsE> c){
//将传入集合元素放入自己数据
   elementData = c.toArray();
//设置size 并检查长度(这一行做了赋值比较 很妙)
if((size = elementData.length)!=0){
// 转换类型 c.toArray 返回的可能不是Object[]类型
if(elementData.getClass()!= Object[].class)
           elementData = Arrays.copyOf(elementData, size, Object[].class);
}else{
// 如果传入为空 将数据设置为空数组
this.elementData = EMPTY_ELEMENTDATA;
}
}

常用方法解析

添加

publicbooleanadd(E e){
//使容量够用
ensureCapacityInternal(size +1);
    elementData[size++]= e;//将元素插入最后
returntrue;
}
publicvoidadd(int index, E element){
ensureCapacityInternal(size +1);//增加容量
//将index之后数据往后移动一位
    System.arraycopy(elementData, index, elementData, index +1, size - index);
    elementData[index]= element;//设置index位置为传入数据
    size++;//增加数量
}
/** * 这下面都是对容量进行增加的判断 */
privatevoidensureCapacityInternal(int minCapacity){
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//计算容量
privatestaticintcalculateCapacity(Object[] elementData,int minCapacity){
//如果元素为空数组 为默认容量和传入的容量中大的那个
if(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
//确认容量大小
privatevoidensureExplicitCapacity(int minCapacity){
    modCount++;//增加操作次数
// 如果传入的容量大于数组实际大小 就要增加数组大小了
if(minCapacity - elementData.length >0)
grow(minCapacity);
}
//增加容量
privatevoidgrow(int minCapacity){
int oldCapacity = elementData.length;
//默认扩充为原来的1.5倍
int newCapacity = oldCapacity +(oldCapacity >>1);
//如果扩充1.5倍小于传入的容量 那么就使用传入的容量
if(newCapacity - minCapacity <0)
        newCapacity = minCapacity;
//如果容量大于最大允许容量 确定使用integet最大值还是使用最大数组容量
if(newCapacity - MAX_ARRAY_SIZE >0)
        newCapacity =hugeCapacity(minCapacity);
// 将数组数据复制到新的数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}
//巨大容量处理
privatestaticinthugeCapacity(int minCapacity){
if(minCapacity <0)thrownewOutOfMemoryError();
//如果容量大于MAX_ARRAY_SIZE 使用int最大值 否则使用max array
return(minCapacity > MAX_ARRAY_SIZE)?Integer.MAX_VALUE:MAX_ARRAY_SIZE;
}

添加多个

publicbooleanaddAll(Collection<?extendsE> c){
  	Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);// 扩充长度
    System.arraycopy(a,0, elementData, size, numNew);//复制集合到后面
    size += numNew;//修正长度
return numNew !=0;
}

获取

public E get(int index){
returnelementData(index);
}
E elementData(int index){
return(E) elementData[index];//返回数组中指定位置的数据
}

是否包含

publicbooleancontains(Object o){
returnindexOf(o)>=0;
}
//从前往后找到第一个相同元素
publicintindexOf(Object o){
//传入为空 找第一个空数据
if(o == null){
for(int i =0; i < size; i++)
if(elementData[i]==null)return i;
}else{
for(int i =0; i < size; i++)
if(o.equals(elementData[i]))return i;
}
return-1;
}

移除

public E remove(int index){
    modCount++;
    E oldValue =elementData(index);
//将index之后的数据依次往前移动一位
int numMoved = size - index -1;
if(numMoved >0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size]= null;// 将最后一位置空 这样垃圾回收器才能回收 并修正size 
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;
}

交集

publicbooleanretainAll(Collection<?> c){
    Objects.requireNonNull(c);//验证集合非空
returnbatchRemove(c,true);
}
//批量删除数据 complemet为true 删除c中包含的数据 false 删除c中不包含的数据
privatebooleanbatchRemove(Collection<?> c,boolean complement){
final Object[] elementData =this.elementData;
int r =0, w =0;//定义两个指针 读和写
boolean modified =false;
try{
//遍历本集合 元素包含在c中 就放入本集合 否则跳过
for(; r < size; r++)
if(c.contains(elementData[r])== complement)
                elementData[w++]= elementData[r];
}finally{
// 正常来说r最后是等于size的，除非c.contains()抛出了异常
if(r != size){
//把未读的元素都拷贝到写指针之后
            System.arraycopy(elementData, r, elementData, w, size - r);
            w += size - r;
}
if(w != size){
// 读指针后面的数据清空
for(int i = w; i < size; i++)
                elementData[i]= null;
            modCount += size - w;
            size = w;
            modified =true;
}
}
return modified;
}

总结

内部采用Object类型数组存储数据; 初始化时为空数组
当长度不够的时候; 默认扩容原来一半的空间; 不会缩容
随机访问元素快 直接通过下标就能获取到数据 时间复杂度O(1)
插入和删除尾部数据比较快 平均复杂度O(1)
插入和删除中间元素效率差 删除后要将后边数据放到依次前移 平均O(n)
一般的可以认为: 遍历查询快 增加删除慢

以上是 ArrayList源码分析 的全部内容， 来源链接： utcz.com/z/509893.html

回到顶部