黑马程序员技术交流社区

标题: ArrayList源码解析 [打印本页]

作者: 曹老师 时间: 2017-11-15 14:06
标题: ArrayList源码解析
ArrayList源码解析

今天来介绍下ArrayList，ArrayList继承了AbstractList，实现了List。ArrayList在工作中经常用到，所以要弄懂这个类是极其重要的。
构造图如下:
蓝色线条：继承
绿色线条：接口实现
file:///C:\Users\PC\AppData\Local\Temp\ksohtml\wps9B74.tmp.jpg

正文ArrayList简介ArrayList定义

1	public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList 是一个数组队列，相当于 动态数组。与Java中的数组相比，它的容量能动态增长。它继承于AbstractList，实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口。

ArrayList 继承了AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。
ArrayList 实现了RandmoAccess接口，即提供了随机访问功能。RandmoAccess是java中用来被List实现，为List提供快速访问功能的。在ArrayList中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。稍后，我们会比较List的“快速随机访问”和“通过Iterator迭代器访问”的效率。

ArrayList 实现了Cloneable接口，即覆盖了函数clone()，能被克隆。

ArrayList 实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。

和Vector不同，ArrayList中的操作不是线程安全的！所以，建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或者CopyOnWriteArrayList。

ArrayList属性

顾名思义哈，ArrayList就是用数组实现的List容器，既然是用数组实现，当然底层用数组来保存数据啦

1
2
3
4

// 保存ArrayList中数据的数组
private transient Object[] elementData;
// ArrayList中实际数据的数量
private int size;

ArrayList包含了两个重要的对象：elementData 和 size。

(1) elementData 是”Object[]类型的数组”，它保存了添加到ArrayList中的元素。实际上，elementData是个动态数组，我们能通过构造函数 ArrayList(int initialCapacity)来执行它的初始容量为initialCapacity；如果通过不含参数的构造函数ArrayList()来创建ArrayList，则elementData的容量默认是10。elementData数组的大小会根据ArrayList容量的增长而动态的增长，具体的增长方式，请参考源码分析中的ensureCapacity()函数。

(2) size 则是动态数组的实际大小。

ArrayList构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// ArrayList带容量大小的构造函数。
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
// 新建一个数组
this.elementData = new Object[initialCapacity];
}

// ArrayList构造函数。默认容量是10。
public ArrayList() {
this(10);
}

// 构造一个包含指定元素的list，这些元素的是按照Collection的迭代器返回的顺序排列的
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}

· 第一个构造方法使用提供的initialCapacity来初始化elementData数组的大小。

· 第二个构造方法调用第一个构造方法并传入参数10，即默认elementData数组的大小为10。

· 第三个构造方法则将提供的集合转成数组返回给elementData（返回若不是Object[]将调用Arrays.copyOf方法将其转为Object[]）。

API方法摘要

file:///C:\Users\PC\AppData\Local\Temp\ksohtml\wps9B75.tmp.jpg

ArrayList源码解析(基于JDK1.6.0_45)增加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

/**
   * 添加一个元素
   */
public boolean add(E e) {
   // 进行扩容检查
   ensureCapacity( size + 1);  // Increments modCount
   // 将e增加至list的数据尾部，容量+1
      elementData[size ++] = e;
      return true;
}

/**
   * 在指定位置添加一个元素
   */
public void add(int index, E element) {
      // 判断索引是否越界，这里会抛出多么熟悉的异常。。。
      if (index > size || index < 0)
         throw new IndexOutOfBoundsException(
            "Index: "+index+", Size: " +size);

   // 进行扩容检查
   ensureCapacity( size+1);  // Increments modCount
   // 对数组进行复制处理，目的就是空出index的位置插入element，并将index后的元素位移一个位置
   System. arraycopy(elementData, index, elementData, index + 1,
                  size - index);
   // 将指定的index位置赋值为element
      elementData[index] = element;
   // list容量+1
      size++;
}
/**
   * 增加一个集合元素
   */
public boolean addAll(Collection<? extends E> c) {
   //将c转换为数组
   Object[] a = c.toArray();
      int numNew = a.length ;
   //扩容检查
   ensureCapacity( size + numNew);  // Increments modCount
   //将c添加至list的数据尾部
      System. arraycopy(a, 0, elementData, size, numNew);
   //更新当前容器大小
      size += numNew;
      return numNew != 0;
}
/**
   * 在指定位置，增加一个集合元素
   */
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

   // 计算需要移动的长度（index之后的元素个数）
      int numMoved = size - index;
   // 数组复制，空出第index到index+numNum的位置，即将数组index后的元素向右移动numNum个位置
      if (numMoved > 0)
         System. arraycopy(elementData, index, elementData, index + numNew,
                        numMoved);

   // 将要插入的集合元素复制到数组空出的位置中
      System. arraycopy(a, 0, elementData, index, numNew);
      size += numNew;
      return numNew != 0;
}

/**
   * 数组容量检查，不够时则进行扩容
   */
public void ensureCapacity( int minCapacity) {
      modCount++;
   // 当前数组的长度
      int oldCapacity = elementData .length;
   // 最小需要的容量大于当前数组的长度则进行扩容
      if (minCapacity > oldCapacity) {
         Object oldData[] = elementData;
      // 新扩容的数组长度为旧容量的1.5倍+1
         int newCapacity = (oldCapacity * 3)/2 + 1;
      // 如果新扩容的数组长度还是比最小需要的容量小，则以最小需要的容量为长度进行扩容
         if (newCapacity < minCapacity)
            newCapacity = minCapacity;
         // minCapacity is usually close to size, so this is a win:
         // 进行数据拷贝，Arrays.copyOf底层实现是System.arrayCopy()
         elementData = Arrays.copyOf( elementData, newCapacity);
   }
}

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

/**
   * 根据索引位置删除元素
   */
public E remove( int index) {
   // 数组越界检查
   RangeCheck(index);

      modCount++;
   // 取出要删除位置的元素，供返回使用
   E oldValue = (E) elementData[index];
   // 计算数组要复制的数量
      int numMoved = size - index - 1;
   // 数组复制，就是将index之后的元素往前移动一个位置
      if (numMoved > 0)
         System. arraycopy(elementData, index+1, elementData, index,
                        numMoved);
   // 将数组最后一个元素置空（因为删除了一个元素，然后index后面的元素都向前移动了，所以最后一个就没用了），好让gc尽快回收
   // 不要忘了size减一
      elementData[--size ] = null; // Let gc do its work

      return oldValue;
}

/**
   * 根据元素内容删除，只删除匹配的第一个
   */
public boolean remove(Object o) {
   // 对要删除的元素进行null判断
   // 对数据元素进行遍历查找，知道找到第一个要删除的元素，删除后进行返回，如果要删除的元素正好是最后一个那就惨了，时间复杂度可达O(n) 。。。
      if (o == null) {
         for (int index = 0; index < size; index++)
            // null值要用==比较
            if (elementData [index] == null) {
               fastRemove(index);
               return true;
            }
   } else {
         for (int index = 0; index < size; index++)
            // 非null当然是用equals比较了
            if (o.equals(elementData [index])) {
               fastRemove(index);
               return true;
            }
      }
      return false;
}

/*
   * Private remove method that skips bounds checking and does not
   * return the value removed.
   */
private void fastRemove(int index) {
      modCount++;
   // 原理和之前的add一样，还是进行数组复制，将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
}

/**
   * 数组越界检查
   */
private void RangeCheck(int index) {
      if (index >= size )
         throw new IndexOutOfBoundsException(
            "Index: "+index+", Size: " +size);
}

增加和删除方法到这里就解释完了，代码是很简单，主要需要特别关心的就两个地方：1.数组扩容，2.数组复制，这两个操作都是极费效率的，最惨的情况下(添加到list第一个位置，删除list最后一个元素或删除list第一个索引位置的元素)时间复杂度可达O(n)。

还记得上面那个坑吗（为什么提供一个可以指定容量大小的构造方法）？看到这里是不是有点明白了呢，简单解释下：如果数组初试容量过小，假设默认的10个大小，而我们使用ArrayList的主要操作时增加元素，不断的增加，一直增加，不停的增加，会出现上面后果？那就是数组容量不断的受挑衅，数组需要不断的进行扩容，扩容的过程就是数组拷贝System.arraycopy的过程，每一次扩容就会开辟一块新的内存空间和数据的复制移动，这样势必对性能造成影响。那么在这种以写为主（写会扩容，删不会缩容）场景下，提前预知性的设置一个大容量，便可减少扩容的次数，提高了性能。
file:///C:\Users\PC\AppData\Local\Temp\ksohtml\wps9B95.tmp.png
file:///C:\Users\PC\AppData\Local\Temp\ksohtml\wps9B96.tmp.png
上面两张图分别是数组扩容和数组复制的过程，需要注意的是，数组扩容伴随着开辟新建的内存空间以创建新数组然后进行数据复制，而数组复制不需要开辟新内存空间，只需将数据进行复制。

上面讲增加元素可能会进行扩容，而删除元素却不会进行缩容，如果在已删除为主的场景下使用list，一直不停的删除而很少进行增加，那么会出现什么情况？再或者数组进行一次大扩容后，我们后续只使用了几个空间，会出现上面情况？当然是空间浪费啦啦啦，怎么办呢？

1
2
3
4
5
6
7
8
9
10
11

/**
   * 将底层数组的容量调整为当前实际元素的大小，来释放空间。
   */
public void trimToSize() {
      modCount++;
   // 当前数组的容量
      int oldCapacity = elementData .length;
   // 如果当前实际元素大小小于当前数组的容量，则进行缩容
      if (size < oldCapacity) {
         elementData = Arrays.copyOf( elementData, size );
   }

更新

1
2
3
4
5
6
7
8
9
10
11
12
13
14

/**
   * 将指定位置的元素更新为新元素
   */
public E set( int index, E element) {
   // 数组越界检查
   RangeCheck(index);

   // 取出要更新位置的元素，供返回使用
   E oldValue = (E) elementData[index];
   // 将该位置赋值为行的元素
      elementData[index] = element;
   // 返回旧元素
      return oldValue;
}

查找

1
2
3
4
5
6
7
8

/**
   * 查找指定位置上的元素
   */
public E get( int index) {
   RangeCheck(index);

      return (E) elementData [index];
}

是否包含

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

/**
   * Returns <tt>true</tt> if this list contains the specified element.
   * More formally, returns <tt>true</tt> if and only if this list contains
   * at least one element <tt>e</tt> such that
   * <tt>(o==null ? e==null : o.equals(e))</tt>.
   *
   * @param o element whose presence in this list is to be tested
   * @return <tt> true</tt> if this list contains the specified element
   */
public boolean contains(Object o) {
      return indexOf(o) >= 0;
}

/**
   * Returns the index of the first occurrence of the specified element
   * in this list, or -1 if this list does not contain the element.
   * More formally, returns the lowest index <tt>i</tt> such that
   * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
   * or -1 if there is no such index.
   */
public int indexOf(Object o) {
      if (o == null) {
         for (int i = 0; i < size; i++)
            if (elementData ==null)
               return i;
   } else {
         for (int i = 0; i < size; i++)
            if (o.equals(elementData ))
               return i;
   }
      return -1;
}

/**
   * Returns the index of the last occurrence of the specified element
   * in this list, or -1 if this list does not contain the element.
   * More formally, returns the highest index <tt>i</tt> such that
   * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
   * or -1 if there is no such index.
   */
public int lastIndexOf(Object o) {
      if (o == null) {
         for (int i = size-1; i >= 0; i--)
            if (elementData ==null)
               return i;
   } else {
         for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData ))
               return i;
   }
      return -1;
}

contains主要是检查indexOf，也就是元素在list中出现的索引位置也就是数组下标，再看indexOf和lastIndexOf代码是不是很熟悉，没错，和public boolean remove(Object o) 的代码一样，都是元素null判断，都是循环比较，不多说了。。。但是要知道，最差的情况（要找的元素是最后一个）也是很惨的。。。

容量判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/**
   * Returns the number of elements in this list.
   *
   * @return the number of elements in this list
   */
public int size() {
      return size ;
}

/**
   * Returns <tt>true</tt> if this list contains no elements.
   *
   * @return <tt> true</tt> if this list contains no elements
   */
public boolean isEmpty() {
      return size == 0;
}

由于使用了size进行计数，发现list大小获取和判断真的好容易。

总结：
(01) ArrayList 实际上是通过一个数组去保存数据的。当我们构造ArrayList时；若使用默认构造函数，则ArrayList的默认容量大小是10。
(02) 当ArrayList容量不足以容纳全部元素时，ArrayList会重新设置容量：新的容量=“(原始容量x3)/2 + 1”。
(03) ArrayList的克隆函数，即是将全部元素克隆到一个数组中。
(04) ArrayList实现java.io.Serializable的方式。当写入到输出流时，先写入“容量”，再依次写入“每一个元素”；当读出输入流时，先读取“容量”，再依次读取“每一个元素”。

ArrayList遍历方式

ArrayList支持3种遍历方式
(01) 第一种，通过迭代器遍历。即通过Iterator去遍历。

1
2
3
4
5

Integer value = null;
Iterator iter = list.iterator();
while (iter.hasNext()) {
value = (Integer)iter.next();
}

(02) 第二种，随机访问，通过索引值去遍历。
由于ArrayList实现了RandomAccess接口，它支持通过索引值去随机访问元素。

1
2
3
4
5

Integer value = null;
int size = list.size();
for (int i=0; i<size; i++) {
value = (Integer)list.get(i);
}

(03) 第三种，for循环遍历。如下：

1
2
3
4

Integer value = null;
for (Integer integ:list) {
value = integ;
}

下面通过一个实例，比较这3种方式的效率，实例代码(ArrayListRandomAccessTest.java)如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

import java.util.*;
import java.util.concurrent.*;

/*
* @desc ArrayList遍历方式和效率的测试程序。
*
* @author skywang
*/
public class ArrayListRandomAccessTest {

public static void main(String[] args) {
      List list = new ArrayList();
      for (int i=0; i<100000; i++)
         list.add(i);
      //isRandomAccessSupported(list);
      iteratorThroughRandomAccess(list) ;
      iteratorThroughIterator(list) ;
      iteratorThroughFor2(list) ;

}

private static void isRandomAccessSupported(List list) {
      if (list instanceof RandomAccess) {
         System.out.println("RandomAccess implemented!");
      } else {
         System.out.println("RandomAccess not implemented!");
      }

}

public static void iteratorThroughRandomAccess(List list) {

      long startTime;
      long endTime;
      startTime = System.currentTimeMillis();
      for (int i=0; i<list.size(); i++) {
         list.get(i);
      }
      endTime = System.currentTimeMillis();
      long interval = endTime - startTime;
      System.out.println("iteratorThroughRandomAccess：" + interval+" ms");
}

public static void iteratorThroughIterator(List list) {

      long startTime;
      long endTime;
      startTime = System.currentTimeMillis();
      for(Iterator iter = list.iterator(); iter.hasNext(); ) {
         iter.next();
      }
      endTime = System.currentTimeMillis();
      long interval = endTime - startTime;
      System.out.println("iteratorThroughIterator：" + interval+" ms");
}

public static void iteratorThroughFor2(List list) {

      long startTime;
      long endTime;
      startTime = System.currentTimeMillis();
      for(Object obj:list)
         ;
      endTime = System.currentTimeMillis();
      long interval = endTime - startTime;
      System.out.println("iteratorThroughFor2：" + interval+" ms");
}
}

运行结果：

1
2
3

iteratorThroughRandomAccess：3 ms
iteratorThroughIterator：8 ms
iteratorThroughFor2：5 ms

由此可见，遍历ArrayList时，使用随机访问(即，通过索引序号访问)效率最高，而使用迭代器的效率最低！

ArrayList示例

本文通过一个实例(ArrayListTest.java)，介绍 ArrayList 中常用API的用法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

import java.util.*;

/*
* @desc ArrayList常用API的测试程序
* @author skywang
* @email kuiwu-wang@163.com
*/
public class ArrayListTest {

public static void main(String[] args) {

      // 创建ArrayList
      ArrayList list = new ArrayList();

      // 将“”
      list.add("1");
      list.add("2");
      list.add("3");
      list.add("4");
      // 将下面的元素添加到第1个位置
      list.add(0, "5");

      // 获取第1个元素
      System.out.println("the first element is: "+ list.get(0));
      // 删除“3”
      list.remove("3");
      // 获取ArrayList的大小
      System.out.println("Arraylist size=: "+ list.size());
      // 判断list中是否包含"3"
      System.out.println("ArrayList contains 3 is: "+ list.contains(3));
      // 设置第2个元素为10
      list.set(1, "10");

      // 通过Iterator遍历ArrayList
      for(Iterator iter = list.iterator(); iter.hasNext(); ) {
         System.out.println("next is: "+ iter.next());
      }

      // 将ArrayList转换为数组
      String[] arr = (String[])list.toArray(new String[0]);
      for (String str:arr)
         System.out.println("str: "+ str);

      // 清空ArrayList
      list.clear();
      // 判断ArrayList是否为空
      System.out.println("ArrayList is empty: "+ list.isEmpty());
}
}

运行结果：

1
2
3
4
5
6
7
8
9
10
11
12

the first element is: 5
Arraylist size=: 4
ArrayList contains 3 is: false
next is: 5
next is: 10
next is: 2
next is: 4
str: 5
str: 10
str: 2
str: 4
ArrayList is empty: true

总结ArrayList和LinkedList的区别

1. ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。

2. 对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。

3. 对于新增和删除操作add和remove，LinkedList比较占优势，因为ArrayList要移动数据。

ArrayList和Vector的区别

1. Vector和ArrayList几乎是完全相同的,唯一的区别在于Vector是同步类(synchronized)，属于强同步类。因此开销就比ArrayList要大，访问要慢。正常情况下,大多数的Java程序员使用ArrayList而不是Vector,因为同步完全可以由程序员自己来控制。

2. Vector每次扩容请求其大小的2倍空间，而ArrayList是1.5倍。

3. Vector还有一个子类Stack.

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2