老猿说说-ArrayList

作者: JIU_LV | 来源:发表于2020-10-09 11:55 被阅读0次

1 概述

ArrayList 整体架构比较简单，就是一个数组结构
比如：长度为10的数组，从1开始计数，index表示数组的下标，从0开始计数，

elementData表示数组本身，源码中除了这两个概念，还有以下三个基本概念：

DEFAULT_CAPACITY表示数组的初始大小，默认是10,这个数字要记住；
size表示当前数组的大小，类型int,没有使用volatile修饰，非线程安全的；
modCount统计当前数组被修改的版本次数，数组结构有变动，就会+1。

类注释

看源码，首先要看类注释，我们看看类注释上面都说了什么，如下：

允许 put null值，会自动扩容；
size、isEmpty、get、set、add等方法时间复杂度都是O(1);
除了上述注释中提到的4点，初始化、扩容的本质、迭代器等问题也经常被问，接下来我们从源码出发，——解析。

2 源码解析

2.1 初始化

我们有三种初始化办法：无参数直接初始化、指定大小初始化、指定初始数据初始化，源码如

private static final ObjectD DEFAULTCAPACITY_EMPTY_ELEMENTDATA = 0;
  //无参数直接初始化，数组大小为空
  public ArrayList(){
    this.elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  }
  //指定初始数据初始化
  public ArrayList(Collection<? extends E> c){
      //elementData是保存数组的容器，默认为null
      elementData=c.toArray();
      //如果给定的集合（c)数据有值
      if((size=elementData.length)!=0){
        //c.toArray might(incorrectly)not return Object[](see 6260652)
        //如果集合元素类型不是Object类型，我们会转成Object
      if(elementData.getClass()!=Object[].class){
        elementData=Arrays.copyOf(elementData,size,Object].class);
      }
    }else{
      //给定集合（c)无值，则默认空数组
      this.elementData=EMPTY_ELEMENTDATA
    }
  }
}

除了源码的中文注释，我们补充两点：

ArrayList无参构造器初始化时，默认大小是空数组，并不是大家常说的10,10是在第一次add的时候扩容的数组值。
指定初始数据初始化时，我们发现一个这样子的注释see6260652,这是Java的一个
bug,意思是当给定集合内的元素不是Object类型时，我们会转化成Object的类型。一般情
况下都不会触发此bug,只有在下列场景下才会触发：ArrayList初始化之后（ArrayList元素非Object类型）,再次调用toArray方法，得到Object数组，并且往Object数组赋值时，
官方查看文档地址：https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652,问题在Java9中被解决。

2.2 新增和扩容实现

新增就是往数组中添加元素，主要分成两步

判断是否需要扩容，如果需要执行扩容操作；
直接赋值。

两步源码体现如下：

public boolean add(E e){
  //确保数组大小是否足够，不够执行扩容，size为当前数组的大小
  ensureCapacitylnternal(size+1);//Increments modCount!!
  //直接赋值，线程不安全的
  elementData[size++]=e;
  return true;
}

我们先看下扩容（ensureCapacitylnternal)的源码：

private void ensureCapacitylnternal(int minCapacity){
  //如果初始化数组大小时，有给定初始值，以给定的大小为准，不走if逻辑
  if(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
    minCapacity=Math.max(DEFAULT_CAPACITY,minCapacity);
  }
  //确保容积足够
  ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity){
  //记录数组被修改
  modCount++;
  //如果我们期望的最小容量大于目前数组的长度，那么就扩容
  if(minCapacity-elementData.length>0)
    grow(minCapacity);
}

//扩容，并把现有数据拷贝到新的数组里面去
private void grow(int minCapacity){
  int oldCapacity = elementData.length;
  //oldCapacity>>1是把oldCapacity除以2的意思
  int newCapacity=oldCapacity+(oldCapacity>>1);
  //如果扩容后的值<我们的期望值，扩容后的值就等于我们的期望值
  if(newCapacity-minCapacity<0)
    newCapacity = minCapacity;
  //如果扩容后的值>jvm所能分配的数组的最大值，那么就用Integer的最大值
  if(newCapacity-MAX_ARRAY_SIZE>0)
    elementData=Arrays.copyOf(elementData,newCapacity);
}

注解应该比较详细，我们需要注意的四点是：

扩容的规则并不是翻倍，是原来容量大小+容量大小的一半，直白来说，扩容后的大小是原
来容量的1.5倍；
ArrayList中的数组的最大值是Integer.MAX_VALUE,超过这个值，JVM就不会给数组分配
内存空间了。
新增时，并没有对值进行严格的校验，所以ArrayList是允许null值的。

从新增和扩容源码中，下面这点值得我们借鉴：

源码在扩容的时候，有数组大小溢出意识，就是说扩容后数组的大小下界不能小于0,上界不能大于Integer的最大值，这种意识我们可以学习

扩容完成之后，赋值是非常简单的，直接往数组上添加元素即可：elementData[size++]=e
也正是通过这种简单赋值，没有任何锁控制，所以这里的操作是线程不安全的

2.3 扩容的本质

扩容是通过这行代码来实现的：Arrays.copyOf(elementData,newCapacity);这行代码描述的
本质是数组之间的拷贝，扩容是会先新建一个符合我们预期容量的新数组，然后把老数组的数据
拷贝过去，我们通过System.arraycopy方法进行拷贝，此方法是native的方法，源码如下：

/**
*@param src 被拷贝的数组
*@param srcPos 从数组那里开始
*@param dest 目标数组
*@param destPos从目标数组那个索引位置开始拷贝
*@param length 拷贝的长度
*此方法是没有返回值的，通过dest的引用进行传值
*/
public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,int length);

我们可以通过下面这行代码进行调用，newElementData表示新的数组：

System.arraycopy(elementData,0,newElementData,0,Math.min(elementData.length,newCapcity));

2.4 删除

ArrayList删除元素有很多种方式，比如根据数组索引删除、根据值删除或批量删除等等，原理
和思路都差不多，我们选取根据值删除方式来进行源码说明：

public boolean remove(Object o) {
  //如果要删除的值是null,找到第一个值是null的删除
  if(o==null){
    for(int index=0;index<size;index++)
      if(elementData[index]==null){
        fastRemove(index)
        return true
      }
  }else{
    //如果要删除的值不为null,找到第一个和要删除的值相等的删除
    for(int index=0;index<size;index++)
      //这里是根据 equals来判断值相等的，相等后再根据索引位置进行删除
      if(o.equals(elementData[index]){
        fastRemove(index)
        return true;
      }
  }
  return false
}

我们需要注意的两点是：

新增的时候是没有对null进行校验的，所以删除的时候也是允许删除null值的；
找到值在数组中的索引位置，是通过equals来判断的，如果数组元素不是基本类型，需要我们关注equals的具体实现。

上面代码已经找到要删除元素的索引位置了，下面代码是根据索引位置进行元素的删除：

private void fastRemove(int index){
  //记录数组的结构要发生变动了
  nodCount++;
  //numMoved表示删除index位置的元素后，需要从index后移动多少个元素到前面去
  //减1的原因，是因为size从1开始算起，index从0开始算起
  int numMoved=size-index-1;
  if(numMoved>0)
    //从index+1位置开始被拷贝，拷贝的起始位置是index,长度是numMoved
    System.arraycopy(elementData, index+1, elementData, index, numMoved);
  //数组最后一个位置赋值null,帮助GC
  elementData[--size] = null;
}

从源码中，我们可以看出，某一个元素被删除后，为了维护数组结构，我们都会把数组后面的元素往前移动

2.5 迭代器

如果要自己实现迭代器，实现java.util.lterator类就好了，ArrayList也是这样做的，我们来看下迭代器的几个总要的参数

int cursor;//迭代过程中，下一个元素的位置，默认从0开始。
int lastRet=-1;//新增场景：表示上一次迭代过程中，索引的位置；删除场景：为-1。
int expectedModCount=modCount;//expectedModCount表示迭代过程中，期望的版本号

迭代器一般来说有三个方法

hasNext 还有没有值可以迭代
next 如果有值可以迭代，迭代的值是多少
remove 删除当前迭代的值

我们来分别看下三个方法的源码：

hasNext

public boolean hasNext0{
  return cursor!=size;//cursor表示下一个元素的位置，size表示实际大小，如果两者相等，说明已经到末尾
}

public E next(){
  //迭代过程中，判断版本号有无被修改，有被修改，抛ConcurrentModificationException异常
  checkForComodification();
  //本次迭代过程中，元素的索引位置
  int i=cursor;
  if(i>=size)
    throw new NoSuchElementException();
  Object[] elementData = Array List. this. elementData;
  if(i>=elementData.length)
    throw new ConcurrentModificationException0;
  //下一次迭代时，元素的位置，为下一次迭代做准备
  cursor=i+1;
  //返回元素值
  return (E)elementData[lastRet=i];
}
  //版本号比较
final void checkForComodification(){
  if(modCount!=expectedModCount)
    throw new ConcurrentModificationException0;
}

从源码中可以看到，next方法就干了两件事情，第一是检验能不能继续迭代，第二是找到迭代的值，并为下一次迭代做准备（cursor+1)。

remove

public void remove(){
  //如果上一次操作时，数组的位置已经小于0了，说明数组已经被删除完了
  if(lastRet<0)
    throw new IllegalStateException();
  checkForComodification();
  try {
    ArrayList.this.remove(lastRet);
    cursor=lastRet;
    //-1表示元素已经被删除，这里也防止重复删除
    lastRet=-1;
    //删除元素时modCount的值已经发生变化，在此赋值给expectedModCount
    //这样下次迭代时，两者的值是一致的了
    expectedModCount=modCount;
  } catch (IndexOutOfBoundsException ex){
    throw new ConcurrentModificationException();
  }
}

这里我们需要注意的两点是：

lastRet=-1的操作目的，是防止重复删除操作
删除元素成功，数组当前modCount就会发生变化，这里会把expectedModCount重新
赋值，下次迭代时两者的值就会一致了

2.6 时间复杂度

从我们上面新增或删除方法的源码解析，对数组元素的操作，只需要根据数组索引，直接新增和
删除，所以时间复杂度是O(1)

2.7 线程安全

我们需要强调的是，只有当ArrayList作为共享变量时，才会有线程安全问题，当ArrayList是
方法内的局部变量时，是没有线程安全的问题的
ArrayList有线程安全问题的本质，是因为ArrayList自身的elementData、size、modConut
在进行各种操作时，都没有加锁，而且这些变量的类型并非是可见（volatile)的，所以如果多
个线程对这些变量进行操作时，可能会有值被覆盖的情况。
类注释中推荐我们使用Collections#synchronizedList来保证线程安全，SynchronizedList是
通过在每个方法上面加上锁来实现，虽然实现了线程安全，但是性能大大降低，具体实现源码：

public boolean add(E e){
  synchronized(mutex){//synchronized是一种轻量锁，mutex表示一个当前SynchronizedList
    return c.add(e);
  }
}

总结

本文从ArrayList整体架构出发，落地到初始化、新增、扩容、删除、迭代等核心源码实现，我
们发现ArrayList其实就是围绕底层数组结构，各个API都是对数组的操作进行封装，让使用者
无需感知底层实现，只需关注如何使用即可。

老猿说说-ArrayList

1 概述

类注释

2 源码解析

2.1 初始化

2.2 新增和扩容实现

2.3 扩容的本质

2.4 删除

2.5 迭代器

hasNext

next

remove

2.6 时间复杂度

2.7 线程安全

总结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

JDK