List实现类ArrayList笔记整理

发表于 | 分类于 |

ArrayList

 日常开发过程中List接口的使用非常频繁，有序且元素可重复，有三个实现类；分别是 ArrayList、LinkedList、Vector。
比较常用的还是前两者，ArrayList的特点是随机访问数据速度比较快。时间复杂度为 O(1) ，但是当数据量很大的时，ArrayList的增删速度明显要低于 LinkedList的，时间复杂度为 O(n)。主要的继承关系为：

mfCkgU.png

 ArrayList底层的实现，总结来说就是用到了可扩容的数组结构，并且实现了标记接口RandomAccess(这个接口没有具体的实现，ArrayList可以被随机访问任意下标的元素，实现RandomAccess接口，有点打上tag的意思，某些后续操作会根据这个tag作出不同的处理)。

ArrayList的结构与常量

 源码中(JDK1.8)实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class ArrayList<E> extends AbstractList<E>
    //继承关系与实现的接口
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
  //Default initial capacity 默认的数组长度即容量
private static final int DEFAULT_CAPACITY = 10;
  //Shared empty array instance used for empty instances 用于空实例的共享空数组实例
private static final Object[] EMPTY_ELEMENTDATA = {};
  //默认大小共享数组实例，与EMPTY_ELEMENTDATA区分
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  //元素容器
transient Object[] elementData;
  //数组的长度及实际元素的个数
private int size; ...}

从几个常量可以看出，ArrayList底层本质上就是扩容数组，默认的容量的为10，并且区分了容量为0的共享数组，扩容需要区别对待。

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//有参构造函数，可以指定底层的数组容量
public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
          //指定空间大小
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
          //为零时，使用空数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
          //异常抛出
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

默认的构造函数：

1
2
3
4
5
//Constructs an empty list with an initial capacity of ten.
//构造一个初始容量为10空列表(默认的容量为10)
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

扩容机制

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
public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;
            //如果为默认的容量则 minExpand 赋值为10，否则直接置0
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

private void ensureExplicitCapacity(int minCapacity) {
           modCount++;

           // overflow-conscious code
           if (minCapacity - elementData.length > 0)
           //这里判断是否需要扩容
               grow(minCapacity);
       }

private void grow(int minCapacity) {
           // overflow-conscious code
           //原始的数组容量
           int oldCapacity = elementData.length;
           //新的容量 >> 右移运算符 n>>1 相当于 n除以2；即扩大为原来的1.5倍
           int newCapacity = oldCapacity + (oldCapacity >> 1);
           //保证不能够小于 minCapacity
           if (newCapacity - minCapacity < 0)
                   newCapacity = minCapacity;
                   //扩容后的新容器如果超过最大值 MAX_ARRAY_SIZE 则执行
           if (newCapacity - MAX_ARRAY_SIZE > 0)
           //最大能支持的容量
                   newCapacity = hugeCapacity(minCapacity);
               // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
        }

private static int hugeCapacity(int minCapacity) {
                if (minCapacity < 0) // overflow
                    throw new OutOfMemoryError();
                return (minCapacity > MAX_ARRAY_SIZE) ?
                    Integer.MAX_VALUE :
                    MAX_ARRAY_SIZE;
        }

底层定义的数组最大值：

1
2
3
4
5
6
7
/**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

对于为什么定义为 Integer.MAX_VALUE - 8; 而不是直接为 Integer.MAX_VALUE; 注释里给出了解释，
stackoverflow 上也作了解释。

总结：ArrayList在增加元素的时候，会检查容量是否满足，对于DEFAULTCAPACITY_EMPTY_ELEMENTDATA扩容后变为原来容量的1.5倍。最大能取值为Integer.MAX_VALUE。例如minCapacity大小为Integer.MAX_VALUE - 7比MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8大，根据代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
minCapacity = Integer.MAX_VALUE - 7;
//则 newCapacity = (Integer.MAX_VALUE - 7) * 1.5;远大于 MAX_ARRAY_SIZE
if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
 elementData = Arrays.copyOf(elementData, newCapacity);

 private static int hugeCapacity(int minCapacity) {
                 if (minCapacity < 0) // overflow
                     throw new OutOfMemoryError();
      // minCapacity = Integer.MAX_VALUE - 7 大于  MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
                 return (minCapacity > MAX_ARRAY_SIZE) ?
                 //这里扩容后容量就会取到最大值 Integer.MAX_VALUE
                     Integer.MAX_VALUE : MAX_ARRAY_SIZE;     
         }

增加元素

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
91
92
//Appends the specified element to the end of this list.
//增加一个元素到列表的末尾，增加之前判断容量是否满足条件
public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
          //如果是默认大小的数组 当所需容量小于10时 仍取10
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
          //扩容逻辑
        ensureExplicitCapacity(minCapacity);
    }

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }


        //指定位置插入元素
public void add(int index, E element) {
          if (index > size || index < 0)
              throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

          ensureCapacityInternal(size + 1);  // Increments modCount!!
          //这里用到了native 的方法
          System.arraycopy(elementData, index, elementData, index + 1,
                           size - index);
          elementData[index] = element;
          size++;
      }

@FastNative
public static native void arraycopy(Object src,  int  srcPos,
                                             Object dest, int destPos,
                                             int length);
```    

#### 删除元素
```Java
public E remove(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    modCount++;
    E oldValue = (E) elementData[index];

    int numMoved = size - index - 1;
    //主要判断了被删除的是不是最后一个元素，如果不是copy数组，与增加刚好相反
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

//删除某个元素(指定)
public boolean remove(Object o) {
  //因为可以包含 null对象，这里作了处理
     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;
 }

//清空操作，遍历元素置为null
public void clear() {
     modCount++;
     // clear to let GC do its work
     //代码习惯，利于GC回收，提高性能，也是日后需要注意的地方
     for (int i = 0; i < size; i++)
         elementData[i] = null;
     size = 0;
 }

修改元素

1
2
3
4
5
6
7
8
9
public E set(int index, E element) {
    //修改元素比较简单，底层是数组，只是检查了是否越界，替换原值
     if (index >= size)
         throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

     E oldValue = (E) elementData[index];
     elementData[index] = element;
     return oldValue;
 }

查找元素

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
//常用方法，根据索引获得对应的值 O(1)
public E get(int index) {
       if (index >= size)
           throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

       return (E) elementData[index];
   }

//某个指定元素的位置
public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

public int indexOf(Object o) {
        //还是对空元素做了处理，在使用的时候上层开发，也要考虑到这个问题，得到了这个元素，恰好这个元素为 null
        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;
    }

//如果删除了元素，很显然为了节省空间，改变了删除前的数组大小以满足要求
public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
        //与扩容不同的是，这里直接返回为元素个数为容量大小
    }

思考

ArrayList的底层实现还是很容易理解的，显然ArrayList的底层使用的是数组结构，随机访问的时间复杂度为O(1)，但是通过源码可以看出，如果元素量过大，频繁的增删，性能上是吃不消的(增删，主要考虑到扩容，拷贝数据，时间复杂度为O(n))。平时开发过程中应该根据情况而定，要求随机访问但不会频繁的增删，性能上影响不会很大。区别于链表结构，增删快，查找慢的特点。

这个功能是摆设，看看就好～～～