Java中ArrayList类的源码解析

前言：在前面我们提到数据结构的。那么今天我们详细看下java源码是如何实现线性表的，这一篇主要讲解顺序表arraylist链式表下一篇在提及。

1：arraylist结构图

2：关于collection和list的区别

最好的比对就是查看他们的源码我们先看collection的所有接口

public interface collection<e> extends iterable<e> {
 int size();
 boolean contains(object o);
 iterator<e> iterator();
 object[] toarray();
 <t> t[] toarray(t[] a);
 boolean add(e e);
 boolean remove(object o);
 boolean containsall(collection<?> c);
 boolean addall(collection<? extends e> c);
 boolean retainall(collection<?> c);
 void clear(); 
 boolean equals(object o);
 int hashcode();
}

在看list接口

public interface list<e> extends collection<e> { 
 int size();
 boolean isempty();
 iterator<e> iterator();
 object[] toarray();
 <t> t[] toarray(t[] a);
 boolean add(e e);
 boolean remove(object o);
 boolean containsall(collection<?> c);
 boolean addall(collection<? extends e> c);
 boolean addall(int index, collection<? extends e> c);
 boolean removeall(collection<?> c);
 boolean retainall(collection<?> c);
 void clear();
 boolean equals(object o);
 int hashcode();
 e get(int index);
 e set(int index, e element);
 void add(int index, e element);
 e remove(int index);
 int indexof(object o); 
 int lastindexof(object o);
 listiterator<e> listiterator();
 listiterator<e> listiterator(int index);
 list<e> sublist(int fromindex, int toindex);
}

由于list是继承collection，所有具有collection所有的功能，从collection接口中我们也可以看出，collection不具有索引，不可以取元素的值，而list取可以，list是具有索引的，这样一来在获取元素方面远远好于collection。

3：iterable接口

从arraylist中我们可以看出，最顶端的接口就是iterable这个接口，这个是一个迭代器，接口如下

public interface iterable<t> {
 iterator<t> iterator();
}

这个接口主要是返回一个对象，这个对象是iterator，那么我们在看看iterator接口里面的方法

public interface iterator<e> {
 boolean hasnext();
 e next();
 void remove();
}

那么我们主要看arraylist是如何实现迭代器iterator的。iterator的实现在abstractlist这个抽象类中的一个私有类itr中。我们看看具体实现

private class itr implements iterator<e> {
 int cursor = 0;
 int lastret = -1;
 int expectedmodcount = modcount;
 public boolean hasnext() {
  return cursor != size();
 }

cursor：记录即将调用索引的位置

lastret：最后一个元素的索引

int expectedmodcount = modcount;目的是为了验证modcount后面会单独说下。

判断这个集合是否存在最后一个元素，通过cursor != size();size表示数组的长度，因为数组中元素索引从0开始，所以当最后一个索引等于数组长度的时候说明已经到数组的尾部了。

public e next() {
  checkforcomodification();
 try {
 e next = get(cursor);
 lastret = cursor++;
 return next;
 } catch (indexoutofboundsexception e) {
 checkforcomodification();
 throw new nosuchelementexception();
 }
 }

final void checkforcomodification() {
 if (modcount != expectedmodcount)
 throw new concurrentmodificationexception();
 }

modcount：记录所有数组数据结构变动的次数，包括添加、删除、更改等，为了避免并发时候，当多个线程同时操作时候，某个线程修改了数组结构，而另一个线程恰恰读取这个数组，这样一来就会产生错误。所以在这段代码中加入了modcount != expectedmodcount，比如a线程对数据结构修改一次，那么modcount比如+1，而expectedmodcount并没有发生变化，所以这样就会抛出异常。

public void remove() {
 if (lastret == -1)
 throw new illegalstateexception();
  checkforcomodification();
 try {
 abstractlist.this.remove(lastret);
 if (lastret < cursor)
  cursor--;
 lastret = -1;
 expectedmodcount = modcount;
 } catch (indexoutofboundsexception e) {
 throw new concurrentmodificationexception();
 }
 }

我们刚刚说了lastret记录的是最后一个元素，所以删除的时候直接按照索引删除即可，因为modcount会减一，所以重新对expectedmodcount 进行赋值，避免遍历时候产生错误。而且把lastred在次赋初始值。

4：分析arraylist

刚刚目的是为了更加连接arraylist做个铺垫，arraylist和我们以前数据结构中提到的顺序表一样，采用object[] 数组进行存储元素，用size来记录元素的元素的个数。

/**
 * the array buffer into which the elements of the arraylist are stored.
 * the capacity of the arraylist is the length of this array buffer.
 */
 private transient object[] elementdata;
 /**
 * the size of the arraylist (the number of elements it contains).
 *
 * @serial
 */
 private int size;

关于transient，一旦变量被transient修饰，变量将不再是对象持久化的一部分，那么为啥采用transient修饰呢，由于elementdata本身是一个缓存数组，通常会预留一些容量，当容量不够时然后进行扩充，比如现在elementdata容量是10，但是只有5个元素，数组中的最后五个元素是没有实际意义的，不需要储存，所以arraylist的设计者将elementdata设计为transient，然后在writeobject方法中手动将其序列化，并且只序列化了实际存储的那些元素，而不是整个数组。我们看下writeobject方法

private void writeobject(java.io.objectoutputstream s)
 throws java.io.ioexception{
 // write out element count, and any hidden stuff
 int expectedmodcount = modcount;
 s.defaultwriteobject();
 // write out array length
 s.writeint(elementdata.length);
 // write out all elements in the proper order.
 for (int i=0; i<size; i++)
  s.writeobject(elementdata[i]);
 if (modcount != expectedmodcount) {
  throw new concurrentmodificationexception();
 }
 }

关于arraylist的初始化。arraylist的设计者采用3种方式初始化。（默认数组容量是10）

public arraylist(int initialcapacity) {
 super();
 if (initialcapacity < 0)
  throw new illegalargumentexception("illegal capacity: "+
initialcapacity);
 this.elementdata = new object[initialcapacity];
 }
 public arraylist() {
 this(10);
 }
 public arraylist(collection<? extends e> c) {
 elementdata = c.toarray();
 size = elementdata.length;
 // c.toarray might (incorrectly) not return object[] (see 6260652)
 if (elementdata.getclass() != object[].class)
 elementdata = arrays.copyof(elementdata, size, object[].class);
 }

trimtosize方法，这个方法可能我们好多人用的少，其实意义蛮大的，它主要把没用的容量去除掉，这样一来可以减少内存的开销

 public void trimtosize() {
 modcount++;
 int oldcapacity = elementdata.length;
 if (size < oldcapacity) {
  elementdata = arrays.copyof(elementdata, size);
 }

ensurecapacity方法，我们知道数组如果满了就会进行扩容，这个方法就是扩容的。

public void ensurecapacity(int mincapacity) {
 modcount++;
 int oldcapacity = elementdata.length;
 if (mincapacity > oldcapacity) {
 object olddata[] = elementdata;
 int newcapacity = (oldcapacity * 3)/2 + 1;
  if (newcapacity < mincapacity)
 newcapacity = mincapacity;
  // mincapacity is usually close to size, so this is a win:
  elementdata = arrays.copyof(elementdata, newcapacity);
 }

modcount就是增加因子，记录操作数组结构的次数，首先和容量进行比对，如果不够了进行扩容。这是java1.6版本的就是在原来的基础上扩容1.5倍。1.7采用>>1也就是所有元素像右边移动一位然后加上原来的容量。其中

indexof方法，这个方法是获取元素索引。通过索引然后进行查询元素

public int indexof(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;
 }

从中我们也可以看出arraylist是支持null的插入的。同样采用的是循环遍历来进行查找，时间复杂的为n。

contains方法，验证数组是否包含某元素，直接通过indexof验证返回值即可

public boolean contains(object o) {
 return indexof(o) >= 0;
 }

lastindexof方法，和indexof相对，indexof是从前往后，lastindexof是从后面往前查找如下

public int lastindexof(object o) {
 if (o == null) {
 for (int i = size-1; i >= 0; i--)
 if (elementdata[i]==null)
  return i;
 } else {
 for (int i = size-1; i >= 0; i--)
 if (o.equals(elementdata[i]))
  return i;
 }
 return -1;
 }

toarray方法，就是把list转换成数组形式

public object[] toarray() {
 return arrays.copyof(elementdata, size);
 }

get和set方法，这个就很简单了大家看下就行

public e get(int index) {
 rangecheck(index);
 return (e) elementdata[index];
 }
 public e set(int index, e element) {
 rangecheck(index);
 e oldvalue = (e) elementdata[index];
 elementdata[index] = element;
 return oldvalue;
 }

rangecheck方法是进行验证的，查询的索引不可以超过数组的长度如下

 private void rangecheck(int index) {
 if (index >= size)
 throw new indexoutofboundsexception(
 "index: "+index+", size: "+size);
 }

add(e e)添加一个元素，这个采用尾插入，先验证容量，size+1是加入1个元素后长度，看原来数组容量是否够。

 public boolean add(e e) {
 ensurecapacity(size + 1); // increments modcount!!
 elementdata[size++] = e;
 return true;
 }

add(int index, e element)按照索引进行插入，第一个还是一样进行扩容，然后把索引index后面的元素全部向后面移一位。system.arraycopy(elementdata, index, elementdata, index + 1,
             size - index);的意思就是将elementdata的第index个元素移到第index+1个元素上，长度为size-index。

public void add(int index, e element) {
 if (index > size || index < 0)
 throw new indexoutofboundsexception(
 "index: "+index+", size: "+size);
 ensurecapacity(size+1); // increments modcount!!
 system.arraycopy(elementdata, index, elementdata, index + 1,
  size - index);
 elementdata[index] = element;
 size++;
 }

addall(collection<? extends e> c)

public boolean addall(collection<? extends e> c) {
 object[] a = c.toarray();
 int numnew = a.length;
 ensurecapacity(size + numnew); // increments modcount
 system.arraycopy(a, 0, elementdata, size, numnew);
 size += numnew;
 return numnew != 0;
 }

首先把集合c转换成a数组，然后计算要进行添加的数组长度，其它的基本和添加元素一致。arraycopy(object src, int srcpos,object dest, int destpos,int length)

参数次数依次 源数组，源数组起始位置，目标数组，目标数组起始位置，复制数组元素数目。

addall(int index, collection<? extends e> c)把数组插入到指定位置

public boolean addall(int index, collection<? extends e> c) {
 if (index > size || index < 0)
 throw new indexoutofboundsexception(
 "index: " + index + ", size: " + size);
 object[] a = c.toarray();
 int numnew = a.length;
 ensurecapacity(size + numnew); // increments modcount
 int nummoved = size - index;
 if (nummoved > 0)
 system.arraycopy(elementdata, index, elementdata, index + numnew,
   nummoved);
 system.arraycopy(a, 0, elementdata, index, numnew);
 size += numnew;
 return numnew != 0;
 }

首先判断是是否越界，然后和上面的基本一样，就是进行扩容判断，然后index后面的值进行后移包括index，然后留下的空间插入集合a。所以2次进行复制元素。

e remove(int index)和add相对，删除这个元素然后把index后面的元素往前面移一位size - index - 1其中-1是因为index这个元素会被删除，会少一位元素。

public e remove(int index) {
 rangecheck(index);
 modcount++;
 e oldvalue = (e) elementdata[index];
 int nummoved = size - index - 1;
 if (nummoved > 0)
 system.arraycopy(elementdata, index+1, elementdata, index,
   nummoved);
 elementdata[--size] = null; // let gc do its work
 return oldvalue;
 }

remove(object o)这个就需要先进性验证然后找到这个元素的位置最后进行删除

public boolean remove(object o) {
 if (o == null) {
  for (int index = 0; index < size; index++)
 if (elementdata[index] == null) {
  fastremove(index);
  return true;
 }
 } else {
 for (int index = 0; index < size; index++)
 if (o.equals(elementdata[index])) {
  fastremove(index);
  return true;
 }
 }
 return false;
 }

private void fastremove(int index) {
 modcount++;
 int nummoved = size - index - 1;
 if (nummoved > 0)
  system.arraycopy(elementdata, index+1, elementdata, index,
    nummoved);
 elementdata[--size] = null; // let gc do its work
 }

clear就是把所有的原素置空

public void clear() {
 modcount++;
 // let gc do its work
 for (int i = 0; i < size; i++)
 elementdata[i] = null;
 size = 0;
 }

sublist方法，我们知道arraylist是有这个方法，在arraylist源码并不存在，因为是继承abstractlist而来的

 public list<e> sublist(int fromindex, int toindex) {
 return (this instanceof randomaccess ?
  new randomaccesssublist<e>(this, fromindex, toindex) :
  new sublist<e>(this, fromindex, toindex));
 }

class sublist<e> extends abstractlist<e> {
 private abstractlist<e> l;
 private int offset;
 private int size;
 private int expectedmodcount;
 sublist(abstractlist<e> list, int fromindex, int toindex) {
 if (fromindex < 0)
  throw new indexoutofboundsexception("fromindex = " + fromindex);
 if (toindex > list.size())
  throw new indexoutofboundsexception("toindex = " + toindex);
 if (fromindex > toindex)
  throw new illegalargumentexception("fromindex(" + fromindex +
      ") > toindex(" + toindex + ")");
 l = list;
 offset = fromindex;
 size = toindex - fromindex;
 expectedmodcount = l.modcount;
 }

从代码中我们可以看出这个一个基本内部类的实现，sublist只是去list中的一段数据。但是关于sublist我们要注意几个事项。

第一：如果我们改变了list的数值，那么你获取的sublist中的值也随之改变，原因如下

 public e get(int index) {
 rangecheck(index);
 checkforcomodification();
 return l.get(index+offset);
 }

因为获取的还是以前list中的数据。同样如果修改sublist获取的数值，list同样改变，

第二：如果改变了list结构，可能导致sublist的不可用，因为这些修改已然基于原来的list，他们共同用一个list数组。

public void add(int index, e element) {
 if (index<0 || index>size)
  throw new indexoutofboundsexception();
 checkforcomodification();
 l.add(index+offset, element);
 expectedmodcount = l.modcount;
 size++;
 modcount++;
 }

5：关于list删除错误分析

list在采用循环删除的时候会报concurrentmodificationexception异常，那么我们来看看具体原因，先看一段代码

list<string> list = new arraylist<string>();
 list.add("a");
 list.add("b");
 list.add("c");
 list.add("d");
 list.add("e");
 for (string str:list){
  list.remove(str);
 }

由于foreach遍历最终会for (iterator it=iterator;iterators.hasnext();)模式那么所以获取元素的时候必然会用到迭代器中的next方法，next方法我们前面说了会有if(modcount!= expectedmodcount)throw new concurrentmodificationexception()验证。因为调用remove(t x)方法时候modcount会+1,所以2次比较就会出现不一致。

正确写法如下

 iterator iterator=list.iterator();
 while (iterator.hasnext()){
  iterator.next();
  iterator.remove();
 }

为啥迭代器中remove就可以呢，是由于在remove代码中有expectedmodcount = modcount这句代码。

6：arraylist是线程安全吗

线程不安全就是指多个线程同时操作造成脏读，错读情况，很明显arraylist是非线程安全的，比如说arraylist现在只有一个值后，如果a，b2个线程同时删除这个值，a线程判断得到size=1,而此时时间片段到，cpu调用b线程执行发现size也是1，开始删除操作，然后a继续进行发现arraylist已经空了就会报异常。或者添加等等。但是vector是线程安全的，因为里面所有方法都加入了synchronized，这样造成的结果就是所有线程执行arraylist方法都必须等待，直到获取同步锁才可以继续进行，这样一来性能大大降低。

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持！