Java中ArrayList类的源码解析

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

成都创新互联从2013年成立，是专业互联网技术服务公司，拥有项目成都网站制作、成都网站设计网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元富蕴做网站,已为上家服务,为富蕴各地企业和个人服务,联系电话:18982081108

1：ArrayList结构图

2：关于Collection和List的区别

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

public interface Collection extends Iterable {
 int size();
 boolean contains(Object o);
 Iterator iterator();
 Object[] toArray();
  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 extends Collection { 
 int size();
 boolean isEmpty();
 Iterator iterator();
 Object[] toArray();
  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 listIterator();
 ListIterator listIterator(int index);
 List subList(int fromIndex, int toIndex);
}

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

3：Iterable接口

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

public interface Iterable {
 Iterator iterator();
}

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

public interface Iterator {
 boolean hasNext();
 E next();
 void remove();
}

那么我们主要看ArrayList是如何实现迭代器Iterator的。Iterator的实现在AbstractList这个抽象类中的一个私有类Itr中。我们看看具体实现

private class Itr implements Iterator {
 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

关于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 subList(int fromIndex, int toIndex) {
 return (this instanceof RandomAccess ?
  new RandomAccessSubList(this, fromIndex, toIndex) :
  new SubList(this, fromIndex, toIndex));
 }

class SubList extends AbstractList {
 private AbstractList l;
 private int offset;
 private int size;
 private int expectedModCount;
 SubList(AbstractList 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 list = new ArrayList();
 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方法都必须等待，直到获取同步锁才可以继续进行，这样一来性能大大降低。

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

网站标题：Java中ArrayList类的源码解析
文章分享：http://chengdu.cdxwcx.cn/article/ghjcgp.html

甜橘子，专注成都网站制作网站设计与营销型网站建设与优化

首页

网站建设

网站制作案例

解决方案

网站设计报价

网站制作动态

关于我们

联系我们

成都网站建设设计将想法与焦点和您一起共享

Java中ArrayList类的源码解析

其他资讯

服务器安全审核的范围包括服务器安全测试的设备包括

php导出数据时间太长 php导出数据库

火绒安全能装服务器火绒显示安全服务异常怎么办

阿里云服务器便宜阿里云服务器贵吗

腾讯云服务器安装workerman 腾讯云服务器安装win10

甜橘子，专注成都网站制作网站设计与营销型网站建设与优化

成都网站建设设计 将想法与焦点和您一起共享

Java中ArrayList类的源码解析

其他资讯

服务器安全审核的范围包括 服务器安全测试的设备包括

php导出数据时间太长 php导出数据库

火绒安全能装服务器 火绒显示安全服务异常怎么办

阿里云服务器便宜 阿里云服务器贵吗

腾讯云服务器安装workerman 腾讯云服务器安装win10

成都网站建设设计将想法与焦点和您一起共享

服务器安全审核的范围包括服务器安全测试的设备包括

火绒安全能装服务器火绒显示安全服务异常怎么办

阿里云服务器便宜阿里云服务器贵吗