java源码分析(一):快速掌握ArrayList

今天给大家分析一下java中ArrayList的源码结构,由于此类函数较多,我们只分析重点部分,其余的请大家自行阅读源码.

ArrayList是一个数组结构的集合,也就是说底层存储结构是依赖数组的,那从性能方面讲:这种结构的集合在读取的时候速度非常快,因为有索引,但是修改的操作就比较慢了,这应该是大家都知道的,下面咱们正式来看代码:

首先看一下类结构:

ArrayList使用泛型定义,并且实现了标准的集合接口List,RandomAccess(这个接口需要解释一下,这是个随机访问的接口,他没有任何实现,是一种接口标记的行为,通常是为了提升集合在遍历时的性能,通常在进行集合遍历的时候使用instanceOf RandomAccess 来判断一下是否实现了这个接口,是的话用for循环,否则用迭代器),Cloneable(这个接口没有任何实现,标识当前实现类能够进行复制操作的一种能力,实现此接口的类需要重写clone()方法,但是此处需要注意的是copy操作分为浅拷贝或者深拷贝,这里简单做一下区分,浅拷贝是只把当前对象的属性进行copy,如果对象中有关联其他的对象,则这个对象不会进行copy.深拷贝:将所有属性统统进行copy,但是开销比较大),Serializable 序列化接口,没什么好解释的

分析一下属性:

下面说一下构造方法:

这个构造方法接受一个初始化长度,如果大于0则重新new一个Object数组指定一个长度,赋值给elementData,如果等于零则把elementData的指针指向那个空的默认数组

这个构造方法接收一个Collection的子类,首先调用toArray()将其转换成数组并赋值给elementData,然后进行判断如果长度等于零则直接将elementData的指针指向默认的空数组,如果不等于零则在进行一次判断他的类型是不是Object[],如果不是就进行一次拷贝,这个拷贝方法最后调用System.arraycopy()这个native方法

下面说一下add():

add()方法会先调用ensureCapacityInternal(size+1) 这个方法,参数是当前数组长度+1,ensureCapacityInternal()这个方法接受一个最小容量的数值,就是当前数组长度+1的长度 , 然后会判断当前elementData是否与DEFAULTCAPACITY_EMPTY_ELEMENTDATA这个数组相等,相等则在默认长度和当前长度中挑选一个大的出来,紧接着调用这个方法:

这个操作首先会将modCount做++,这个变量是继承自AdstractList的,至于这个变量的作用,咱们在遍历的时候说, 下面if判断当前的容量 - 当前数组的长度 是否大于0 ,也就是说是否需要扩容,如果大于0就是要扩容,咱们再看看一下grow()方法:

这里我逐行解释:

int oldCapacity = elementData.length; //获取当前数组长度

int newCapacity = oldCapacity + (oldCapacity >> 1); //这是扩容之后的长度

if (newCapacity - minCapacity < 0) //判断新长度减去当前长度是否大于9

newCapacity = minCapacity; //将长度同步

if (newCapacity - MAX_ARRAY_SIZE > 0) //判断新长度是否超出了int的最大长度-8( Integer.MAX_VALUE - 8)

newCapacity = hugeCapacity(minCapacity); //调用hugeCapacity()方法,这个方法返回是这样的 :(minCapacity > Integer.MAX_VALUE - 8) ? Integer.MAX_VALUE : Integer.MAX_VALUE - 8;

最后返回add()方法继续执行 elementData[size++] = e; return true; 到这里这个方法就结束了.但是add()方法可以在置顶位置插入,继续往下看:

这个方法上来会进行一个检查,判断当前要插入的位置是不是会有下标越界,接下来 System.arraycopy(elementData, index, elementData, index + 1,size - index);这个操作会在需要插入的位置上整体往后移动,将这个位置空出来,然后进行赋值.

ArrayList也支持添加一个集合:这个操作比较简单,先进行数组长度的计算以及是否需要扩容,也就是调用ensureCapacityInternal()这个方法,其次是直接进行复制,将集合的内容复制到elementData里

接下来说一下删除操作,这个是根据下标来操作,性能开销就在arraycopy()这个操作上:

首先调用rangeCheck()方法判断下标是否越界,然后modCount做++,elementData()这个方法返回当前index的数据,numMoved 是elementData的长度减去要删除的位置-1,就是index的前一个位置,然后整体数组往前移动一位,这样最后一个位置就空出来了.然后调用elementData[--size] = null; 让GC来回收掉.

再看下根据元素来删除:

这个删除操作就是依赖for循环,在调用fastRemove()这个方法时:

所有的修改操作都会使modCount++,然后这个删除也是将数组往前移动一个位置,最后进行GC回收

最后说一下遍历,出了for循环依次遍历,还有一个迭代器,这个比较麻烦,一步一步说:

这两个方法都会初始化一个ListItr的对象,区别是一个带参数一个不带参数,参数的意思是从什么位置开始进行迭代,下面去看一下ListItr(内部类):

他继承了Itr这个内部类,并且实现了ListIterator这个接口,这个接口的所有方法又Itr和ListIterator这两个内部类一起实现,这里在迭代的时候只需要调用Itr类中的hasNext()方法来判断是否还有后续数据,通常作为while的条件.先看一下hasNext():

游标不能与当前数组长度就返回true,证明还有数据可以迭代.游标会在创建ListItr的时候声明,下面看一下next()这个方法:

这里就要提到modCount这个变量了,他是用来记录操作次数的,那为什么要记录呢.去看一下checkForComodification()这个方法:

之前讲过,每一次对集合的修改操作,都会触发modCount++,所以一旦出现多线程操作,在遍历过程中集合出现了修改操作,if (modCount != expectedModCount)这个操作肯定是不相等了,那就一定会报错了,那应该怎么避免这种情况呢? 答案是:CopyOnWriteArrayList,这个类是具有线程并发特性的,因为他使用了ReentrantLock这个锁,所以同步访问和修改都不会有问题.下面继续说next()这个方法.ListItr()构造方法会有一个赋值游标的操作:cursor = index; 这个index就是从什么位置开始遍历的下标,默认是0,if (i >= size) throw new NoSuchElementException(); 游标必须小于当前数组中元素的个数,否则会报错.

这个同样是判断游标长度是否超出数组下标长度的,然后cursor = i + 1;return (E) elementData[lastRet = i]; 游标往后走,返回取到的数据,这个lastRet 变量的初始值为-1

这样就将核心的几个方法都说完了,由于方法比较多, 写起来篇幅太长,所以只找了一个比较常用的来讲,其他的可以自己去看一下源码,比较易懂

喜欢的请关注一下,有问题欢迎留言或者私信哈.祝生活愉快.