《看不懂你打我系列》之 —— 极简ArrayList

偏执的太偏执、 2023-06-06 07:47 19阅读 0赞

# 要点 #

*  基本实现
 *  扩容机制
 *  数组拷贝

# 基本实现 #

*  内部使用了`Object [] elementData` 来存储元素，这是一个**缓冲数组**，其末尾一般会余留一些空位给待插入的元素。
 *  注意到`elementData`是被`transient`关键字修饰的，被`transient`修饰的字段，不会参与对象的序列化。对`ArrayList`进行序列化，我们调用其实例方法`writeObject()`，其会依次序列化`elementData`中存在的元素；而不是直接序列化整个数组（这会导致`elementData`预留的空位也被序列化，从而浪费了空间和时间）。
 *  由于采用了数组实现，所以`ArrayList`天然支持随机访问，并且它实现了标记接口 `RandomAccess`，在进行遍历时，可以通过判断集合是否实现了`RandomAccess`来选择更优的遍历方式，若是，优先采用普通for循环，否则，采用`Iterator`迭代器
 *  在不确定的情况下，对于size非常大的`List`，千万不要使用普通for循环进行遍历；若List底层使用链表实现（`LinkedList`），普通for循环每次获得下标为`i`的元素，都得把前面`i-1`的位置再遍历一遍，性能极差

# 扩容机制 #

*  插入元素之前，会调用`ensureInternalCapacity(int minCapacity)`方法确保容量足够，容量不足时将进行扩容（调用`grow(int minCapacity)`）
 *  创建`ArrayList`对象时，若使用无参构造函数，则首次插入元素时，将扩容至`DEFAULT_CAPACITY`（10）；若指定了初始容量为0，则首次插入元素时，将扩容至1
 *  随后的每次扩容，都会先尝试扩容至当前容量的1.5倍
 *  留意到`ArrayList` 内部有一个方法`ensureCapacity()`，而`ArrayList`内部没有地方调用它。显然，这个方法是留给用户调用的。在我们明确的知道即将插入大量的元素时，可以先调用该方法，以**避免频繁的扩容**

# 数组拷贝 #

在扩容的代码里，会频繁地看见`Arrays.copyOf()` 这个方法的调用，这个方法会执行对源数组的拷贝，生成一个新的副本数组。在`Arrays.copyOf()`方法内部，实际是调用了`System.arraycopy()`来完成的。不同点在于：`Arrays.copyOf()` 会生成一个新的数组，完成拷贝后返回；而`System.arraycopy()` 则需要将目标数组作为入参传递进去。注意这里的数组拷贝都是**浅拷贝**，拷贝后的数组和原数组中的元素引用的是相同的内存区域，这在扩容时并没有什么问题。但是在我们自己开发时，要尤为注意。若要执行**深拷贝**，则需要使数组元素实现`Clonable` 接口，并覆写`clone()`方法，拷贝时遍历原数组，并依次对每个元素调用`clone()`方法生成新的对象，再将新对象插入到拷贝数组