纸上学来终究浅，只有自己实操了才能理解的更深刻

问题

平时工作中 ArrayList 经常会用到，但是没细想底层实现原理。比如这里抛出几个问题：

  1. 添加、删除元素的时候，具体是怎么实现的？
  2. 初始化的时候数组大小是多少，扩容机制？
  3. 如果让你来实现的话，你会怎么做？

分析源码

看源码，首先要看类注释，我们看看类注释上面都说了什么，如下：

  • 允许 put null 值，会自动扩容
  • size、isEmpty、get、set、add等方法时间复杂度都是O(1)
  • 是非线程安全的，多线程情况下，推荐使用线程安全类： Collections#syschronizedList
  • 增强 for 循环，或者使用迭代器迭代过程中，如果数字组大小被改线，会 fastfail (快速失败)，抛出异常

add(int index，E element)

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* 在指定的位置插入元素
*/
public void add(int index, E element) {
    // 添加元素前 检查，指定下标不能为 0 ，不能大于数组长度
    rangeCheckForAdd(index);
	// 检查数组是否需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

思路

核心是 System.arraycopy(elementData, index, elementData, index + 1,size - index); 上面是思路，比如在下标为 1 也就是 b 的位置插入 d，那么起始的位置下标就是 1，目标位置下标就是起始位置+1，需要移动的步数就是数组的长度减去起始位置的下标。类似的删除也是同样的逻辑，只不过删除操作，会把最后一个元素置为 null，等待GC来清理。

ensureCapacityInternal(int minCapacity)

我们来看下 ensureCapacityInternal 源码：

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
private void ensureCapacityInternal(int minCapacity) {
  //如果初始化数组大小时，有给定初始值，以给定的大小为准，不走 if 逻辑
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  //确保容积足够
  ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
  //记录数组被修改
  modCount++;
  // 如果我们期望的最小容量大于目前数组的长度，那么就扩容
  if (minCapacity - elementData.length > 0)
    grow(minCapacity);
}
//扩容，并把现有数据拷贝到新的数组里面去
private void grow(int minCapacity) {
  int oldCapacity = elementData.length;
  // oldCapacity >> 1 是把 oldCapacity 除以 2 的意思
  int newCapacity = oldCapacity + (oldCapacity >> 1);

  // 如果扩容后的值 < 我们的期望值，扩容后的值就等于我们的期望值
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;

  // 如果扩容后的值 > jvm 所能分配的数组的最大值，那么就用 Integer 的最大值
  if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
 
  // 通过复制进行扩容
  elementData = Arrays.copyOf(elementData, newCapacity);
}

另外一点，ArrayList 无参构造器初始化时，默认大小是空数组，并不是10,10是在第一次 add 的时候扩容的数组值。

动手简单实现

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
**
 * 简单实现ArrayList
 * Created by eru on 2020/4/4.
 */
public class MyList<T> {

    /**
     * 数组长度
     */
    private int size;
    /**
     * 存储元素的数组
     */
    private Object[] myList;
    /***
     * 默认初始化的为空的数组
     */
    private static final Object[] DEFAULT_EMPTY_LIST = {};

    public MyList() {
        myList = DEFAULT_EMPTY_LIST;
    }

    /**
     * 构造指定大小的数组
     * @param capacity 容量
     */
    public MyList(int capacity) {
        if (capacity == 0){
            myList = DEFAULT_EMPTY_LIST;
        }else if (capacity > 0){
            myList = new Object[capacity];
        }else{
            throw new RuntimeException("myList init capacity must more than 0");
        }
    }

    /**
     * 添加一个元素
     * @param e 元素
     * @return 成功与否
     */
    public boolean add(T e){
        // 1. 检查数组是否需要扩容
        ensureCapacity(size + 1);
        // 2. 添加元素
        myList[size++] = e;
        return true;
    }

    /**
     * 检查是否需要扩容
     * @param minCapacity 容量
     */
    private void ensureCapacity(int minCapacity) {
        if (minCapacity - myList.length > 0){
            int oldCapacity = myList.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0){
                newCapacity = minCapacity;
            }
            myList = Arrays.copyOf(myList, newCapacity);
        }

    }

    /**
     * 数组长度
     * @return 数组长度
     */
    public int length(){
        return size;
    }

    /**
     * 删除元素
     * @param index 指定小标
     * @return 被删除的元素
     */
    public T remove(int index){
        T oldValue = get(index);
        if (index == -1){
            throw new RuntimeException("该元素不存在");
        }
        int numRemoved = size - index - 1;
        System.arraycopy(myList, index + 1, myList, index, numRemoved);
        myList[--size] = null; // 最后一位元素是需要删除的，等待GC回收
        return oldValue;
    }

    /**
     * 获取指定下标的元素
     * @param index 下标
     * @return 对应下标的元素
     */
    public T get(int index){
        return (T)myList[index];
    }


    /**
     * 用于测试，打印数组中所有的元素
     */
    public void printElement(){
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(myList[i]);
            if (i != size - 1){
                sb.append(",");
            }
        }
        sb.append("]");
        System.out.println(sb.toString());

    }

    /**
     * 指定下标 添加元素
     * @param index 下标
     * @param val 添加的元素
     */
    public void add(int index, T val){
        checkAdd(index);
        ensureCapacity(size + 1);
        System.arraycopy(myList, index, myList, index + 1, size - index);

        myList[index] = val;
        size++;
    }

    /**
     * 添加指定元素的时候 做检验
     * @param index 下标
     */
    private void checkAdd(int index) {
        if (index > size || index < 0){
            throw new IndexOutOfBoundsException("Index: " + index + "Size: " + size);
        }
    }

}