今天学习下 ArrayList 的源代码, 不同于其他人写的博客, 很多都是翻译源代码中的注释, 然后直接贴到文章中去. 小编打算换一种书写风格, 带着问题看源码可能收获会更大, 本文将围绕着下面几个问题展开讨论.
一, 问题产生
1, 为什么 ArrayList 集合中存储元素的容器声明为
- transient Object[] elementData;
- ?
2, 既然 ArrayList 可以自动扩容, 那么它的扩容机制是怎样实现的?
3, 调用 ArrayList 的 iterator() 返回的迭代器是怎样的?
4, 采用 ArrayList 的迭代器遍历集合时, 对集合执行相关修改操作时为什么会抛出
ConcurrentModificationException
, 我们该如何避免?
5, 当集合扩容或者克隆时免不了对集合进行拷贝操作, 那么 ArrayList 的数组拷贝是怎么实现的?
6,ArrayList 中的序列化机制
小编对 ArrayList 源码大概浏览了之后, 总结出以上几个问题, 带着这些问题, 让我们一起翻开源码解决吧!
二, 问题解答
1, 为什么 ArrayList 集合中存储元素的容器声明为
- transient Object[] elementData;
- ?
ArrayList 是一个集合容器, 既然是一个容器, 那么肯定需要存储某些东西, 既然需要存储某些东西, 那总得有一个存储的地方吧! 就好比说你需要装一吨的水, 总得有个池子给你装吧! 或者说你想装几十毫升水, 总得那个瓶子或者袋子给你装吧! 区别就在于不同大小的水, 我们需要的容器大小也不相同而已!
既然 ArrayList 已经支持泛型了, 那么为什么 ArrayList 源码的容器定义为什么还要定义成下面的 Object[] 类型呢?
transient Object[] elementData;
其实无论你采用
transient E[] elementData;
的方式声明, 或者是采用
transient Object[] elementData;
声明, 都是允许的, 差别在于前者要求我们我们在具体实例化 elementData 时需要做一次类型转换, 而这次类型转换要求我们程序员保证这种转换不会出现任何错误. 为了提醒程序员关注可能出现的类型转换异常, 编译器会发出一个
Type safety: Unchecked cast from String[] to E[]
警告, 这样讲不知道会不会很懵比, 下面的代码告诉你:
- public class MyList<E> {
- // 声明数组, 类型为 E[]
- E[] DATAS;
- // 初始化数组, 必须做一次类型转换
- public MyList(int initialCapacity) {
- DATAS = (E[]) new Object[initialCapacity];
- }
- public E getDATAS(int index) {
- return DATAS[index];
- }
- public void setDATAS(E[] dATAS) {
- DATAS = dATAS;
- }
- }
上面的代码在 1 处我们声明了 E[] 数组, 具体类型取决于你传入 E 的实际类型, 但是要注意, 当你对 DATAS 进行初始化时, 你不能像下面这样初始化:
E[] DATAS = new E[10]; // 这句代码将报错
也就是说, 泛型数组是不能具体化的, 也就是不能通过 new 泛型 [size]; 的方式进行具体化, 那么怎么解决呢? 有两种方式:
1, 进行前面说的做一次转换, 但不推荐
就像上面代码所展示的, 我们可以初始化成 Object[] 类型之后再转换成 E[], 但前提是你得保证这次转换不会出现任何错误, 通常我们不建议这样子写!
2, 直接声明为 Object[]
这种方式也是 ArrayList 源码的定义方式, 那么我们来看看 ArrayList 是怎么初始化的:
- public ArrayList(int initialCapacity) {
- if (initialCapacity> 0) {
- // 此处直接 new Object[], 不会出现任何错误
- this.elementData = new Object[initialCapacity];
- } else if (initialCapacity == 0) {
- this.elementData = EMPTY_ELEMENTDATA;
- } else {
- throw new IllegalArgumentException("Illegal Capacity:"+
- initialCapacity);
- }
- }
但是有一点还需要注意, 但你调用 ArrayList 的 toArray 方法将集合转换为对象数组时, 有可能出现意想不到的结果, 具体可参考小编的另外一篇博文.
[ArrayList 其实也有双胞胎, 但区别还是挺大的!]
总结: 总的来说, 我们要知道泛型数组是不能具体化的, 以及其解决办法! 你可能会很好奇我为什么没有讲 transient, 这个小编放到下面序列化反序列化时讲.
2, 既然 ArrayList 可以自动扩容, 那么它的扩容机制是怎样实现的?
有时候, 我们得保证当增加水的时, 原来的容器也可以装入新的的水而不至于溢出, 也就是 ArrayList 的自动扩容机制. 我们可以想象, 假如列表大小为 10, 那么正常情况下只能装 10 个元素, 我们很好奇在此之后调用 add() 方法时底层做了什么神奇的事, 所以我们看看 add() 方法是怎么实现的:
- // 增加一个元素
- public boolean add(E e) {
- // 确保内部容量大小, size 指的是当前列表的实际元素个数
- ensureCapacityInternal(size + 1);
- elementData[size++] = e;
- return true;
- }
从上面方法可以看出先判断内部容量是否足够满足 size + 1 个元素, 如果可以, 就直接
elementData[size++] = e;
, 否则就需要扩容, 那么怎么扩容呢? 我们到
ensureCapacityInternal()
方法看看, 这里有一点很重要, 请记住下面的参数:
minCapacity 永远代表增加之后实际的总元素个数
newCapacity 永远表示列表能够满足存储 minCapacity 个元素列表所需要扩容的大小
- // 校验内部容量大小
- private void ensureCapacityInternal(int minCapacity) {
- ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
- }
- // 这个方法只有首次调用时会用到, 不然默认返回 minCapacity
- private static int calculateCapacity(Object[] elementData, int minCapacity) {
- // 这里如果成立, 表示该 ArrayList 是刚刚初始化, 还没有 add 进任何元素
- if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
- return Math.max(DEFAULT_CAPACITY, minCapacity);
- }
- return minCapacity;
- }
- // 扩容判断
- private void ensureExplicitCapacity(int minCapacity) {
- modCount++;
- // 判断是否需要扩容, elementData.length 表示列表的空间总大小, 不是列表的实际元素个数, size 才是列表的实际元素个数
- if (minCapacity - elementData.length> 0)
- grow(minCapacity);
- }
上面会判断集合是否刚刚初始化, 即还没有调用过 add() 方法, 如果成立, 则将集合默认扩容至 10,DEFAULT_CAPACITY 的值为 10, 取最大值. 最后一个方法的 grow() 成立的条件是容器的元素大于 10 且没有可用空间, 即需要扩容了, 我们再看看 grow() 方法:
- private void grow(int minCapacity) {
- // 获取旧的列表大小
- int oldCapacity = elementData.length;
- // 扩容之后的新的容器大小, 默认增加一半 ..............................1
- int newCapacity = oldCapacity + (oldCapacity>> 1);
- // 如果扩容一半之后还不足, 则新的容器大小等于 minCapacity.............................2
- if (newCapacity - minCapacity <0) newCapacity = minCapacity;
- // 如果新的容器大小比 MAX_ARRAY_SIZE 还大,
- if (newCapacity - MAX_ARRAY_SIZE> 0) newCapacity = hugeCapacity(minCapacity);
- // 数组拷贝操作
- elementData = Arrays.copyOf(elementData, newCapacity);
- }
- // 最大不能超过 Integer.MAX_VALUE
- 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, 减为一半, 2 处可能调用 addAll() 方法时成立.
下面我们列举几种情况:
ID | 情况描述 | 调用 add()? | 调用 addAll(size)? + size 大小 | 执行结果 |
---|---|---|---|---|
1 | 列表刚初始化 | 是 | 否 | 初始化一个长度为 10 的列表,即容器扩容至 10 个单位 |
2 | 列表实际元素个数为 10,实际大小也为 10,此时调用 add 操作 | 是 | 否 | 容器扩容至 15,容器元素个数为 11,即有 4 个位置空闲 |
3 | 列表实际元素个数为 10,元素个数也为 10,此时调用 addAll 操作 | 否 | 是 + 5 | 容器扩容至 15,没有空余 |
4 | 列表实际元素个数为 5,元素个数为 5,此时调用 addAll() 操作 | 否 | 是 + 10 | 容器扩容至 15,没有空余 |
总结:
扩容机制如下:
1, 先默认将列表大小 newCapacity 增加原来一半, 即如果原来是 10, 则新的大小为 15;
2, 如果新的大小 newCapacity 依旧不能满足 add 进来的元素总个数 minCapacity, 则将列表大小改为和 minCapacity 一样大; 即如果扩大一半后 newCapacity 为 15, 但 add 进来的总元素个数 minCapacity 为 20, 则 15 明显不能存储 20 个元素, 那么此时就将 newCapacity 大小扩大到 20, 刚刚好存储 20 个元素;
3, 如果扩容后的列表大小大于
2147483639
, 也就是说大于
Integer.MAX_VALUE - 8
, 此时就要做额外处理了, 因为实际总元素大小有可能比 Integer.MAX_VALUE 还要大, 当实际总元素大小 minCapacity 的值大于 Integer.MAX_VALUE, 即大于
2147483647
时, 此时 minCapacity 的值将变为负数, 因为 int 是有符号的, 当超过最大值时就变为负数
小编认为, 上面第 3 点也体现了一种智慧, 即当一样东西有可能出错时, 我们应该提前对其做处理, 而不要等到错误发生时再对其进行处理. 也就是我们运维要做监控的目的.
3, 调用 ArrayList 的 iterator() 返回的迭代器是怎样的?
我们都知道所有集合都是 Collection 接口的实现类, 又因为 Collection 继承了 Iterable 接口, 因此所有集合都是可迭代的. 我们常常会采用集合的迭代器来遍历集合元素, 就像下面的代码:
- ArrayList<String> list = new ArrayList<>();
- list.add("a");
- list.add("b");
- // 获取集合的迭代器对象
- Iterator<String> iter = list.iterator();
- while (iter.hasNext()) {
- String item = iter.next();
- System.err.println(item);
- }
我们可以通过调用集合的 iterator() 方法获取集合的迭代器对象, 那么在 ArrayList 中, iterator() 方法是怎么实现的呢?
- public Iterator<E> iterator() {
- return new Itr();
- }
超级简单, 原来是新建了一个叫 Itr 的对象那么这个 Itr 又是什么呢? 打开源码我们发现 Itr 类其实是 ArrayList 的一个内部类, 定义如下:
- private class Itr implements Iterator<E> {
- int cursor; // index of next element to return
- int lastRet = -1; // index of last element returned; -1 if no such
- int expectedModCount = modCount;......................... 1
- Itr() {}
- public boolean hasNext() {...}// 具体实现被我删除了
- public E next() {...}
- public void remove() {...}
- public void forEachRemaining(Consumer<? super E> consumer) {...}
- final void checkForComodification() {...}
- }
该迭代器实现了 Iterator 接口并实现了相关方法, 提供我们对集合的遍历能力. 总结: ArrayList 的迭代器默认是其内部类实现, 实现一个自定义迭代器只需要实现 Iterator 接口并实现相关方法即可. 而实现 Iterable 接口表示该实现类具有像 for-each loop 迭代遍历的能力.
4, 采用 ArrayList 的迭代器遍历集合时, 对集合执行相关修改操作时为什么会抛出
ConcurrentModificationException
, 我们该如何避免?
上面第 3 小节我们查看了 ArrayList 迭代器的源代码, 我们都知道, 如果在迭代的过程中调用非迭代器内部的 remove 或者 clear 方法将会抛出
ConcurrentModificationException
异常, 那到底是为什么呢? 我们一起来看看. 首先这里设计两个很重要的变量, 一个是 expectedModCount, 另一个是 modCount,expectedModCount 在集合内部迭代器中定义, 就像上面第三小节源码 1 处所示, modCount 在 AbstractList 中定义. 就像第三小节 1 处所看到的, 默认两者是相等的, 即
expectedModCount = modCount
, 只有当其不想等的情况下就会抛出异常. 真的是不想等就抛异常吗? 我们来看看迭代器内部的 next 方法:
- public E next() {
- // 在迭代前会对两个变量进行检查
- checkForComodification();
- int i = cursor;
- if (i>= size)
- throw new NoSuchElementException();
- Object[] elementData = ArrayList.this.elementData;
- if (i>= elementData.length)
- throw new ConcurrentModificationException();
- cursor = i + 1;
- return (E) elementData[lastRet = i];
- }
- // 具体检查
- final void checkForComodification() {
- if (modCount != expectedModCount)
- throw new ConcurrentModificationException();
- }
可以看出确实是当它们两者之间不想等时就报错, 问题来了, 那么什么时候会导致它们不想等呢? 不急, 我们来看看 ArrayList 的 remove 方法:
- public E remove(int index) {
- rangeCheck(index);
- // 这里会修改 modCount 的值
- modCount++;
- E oldValue = elementData(index);
- int numMoved = size - index - 1;
- if (numMoved> 0)
- System.arraycopy(elementData, index+1, elementData, index,
- numMoved);
- elementData[--size] = null; // clear to let GC do its work
- return oldValue;
- }
可以看出当调用 remove() 方法时确实是修改了 modCount 的值, 导致报错. 那我们怎么做才能不报错有想在迭代过程中增加或者删除数据呢? 答案是使用迭代器内部的 remove() 方法.
总结:
迭代器迭代集合时不能对被迭代集合进行修改, 原因是 modCount 和 expectedModCount 两个变量值不想等导致的!
5, 当集合扩容或者克隆时免不了对集合进行拷贝操作, 那么 ArrayList 的数组拷贝是怎么实现的?
在 ArrayList 中对集合的拷贝是通过调用 Arrays 的 copyOf 方法实现的, 具体如下:
- public static <T> T[] copyOf(T[] original, int newLength) {
- return (T[]) copyOf(original, newLength, original.getClass());.................2
- }
- public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
- // 在创建新数组对象之前会先对传入的数据类型进行判定
- @SuppressWarnings("unchecked")
- T[] copy = ((Object)newType == (Object)Object[].class)
- ? (T[]) new Object[newLength]
- : (T[]) Array.newInstance(newType.getComponentType(), newLength);
- System.arraycopy(original, 0, copy, 0,
- Math.min(original.length, newLength));
- return copy;
- }
最后还调用了 System 的 arraycopy 方法.
6,ArrayList 中的序列化机制
第一小节我们知道 ArrayList 存储数据的定义方式为:
transient Object[] elementData;
我们会觉得非常奇怪, 这是一个集合存储元素的核心, 却声明为 transient, 是不是就说就不序列化了? 这不科学呀! 其实集合存储的数据还是会序列化的, 具体我们看看 ArrayList 中的 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 size as capacity for behavioural compatibility with clone()
- s.writeInt(size);
- // 这个地方做一个序列化操作
- for (int i=0; i<size; i++) {
- s.writeObject(elementData[i]);
- }
- if (modCount != expectedModCount) {
- throw new ConcurrentModificationException();
- }
- }
从上面的代码中我们可以看出 ArrayList 其实是有对 elementData 进行序列化的, 只不过这样做的原因是因为 elementData 中可能会有很多的 null 元素, 为了不把 null 元素也序列化出去, 所以自定义了 writeObject 和 readObject 方法.
谢谢阅读, 欢迎评论, 共同探讨~
来源: https://juejin.im/post/5b2c5eefe51d4558c0442e95