今天学习下 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,没有空余 |
扩容机制如下:
newCapacity
增加原来一半,即如果原来是10,则新的大小为15; newCapacity
依旧不能满足 add
进来的元素总个数 minCapacity
,则将列表大小改为和 minCapacity
一样大;即如果扩大一半后 newCapacity
为15,但 add
进来的总元素个数 minCapacity
为20,则15明显不能存储20个元素,那么此时就将 newCapacity
大小扩大到20,刚刚好存储20个元素; 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
方法。
谢谢阅读,欢迎评论,共同探讨~