ArrayList 的源码其实比较简单, 所以我并没有跟着源码对照翻译, 文本只是抽取了一些我觉得有意思或一些有疑惑的地方分析的.
一, 成员变量
- private static final int DEFAULT_CAPACITY = 10; // 默认容量
- private static final Object[] EMPTY_ELEMENTDATA = {
- }; // 空实例的空数组对象
- private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
- }; // 也是空数组对象, 用于计算添加第一个元素时要膨胀多少
- transient Object[] elementData; // 存储内容的数组
- private int size; // 存储的数量
其中 elementData 被声明为了 transient, 那么 ArrayList 是如何实现序列化的呢?
查看 writeObject 和 readObject 的源码如下:
- 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);
- // Write out all elements in the proper order.
- for (int i=0; i<size; i++) {
- s.writeObject(elementData[i]);
- }
- if (modCount != expectedModCount) {
- throw new ConcurrentModificationException();
- }
- }
- private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
- elementData = EMPTY_ELEMENTDATA;
- // Read in size, and any hidden stuff
- s.defaultReadObject();
- // Read in capacity
- s.readInt(); // ignored
- if (size> 0) {
- // be like clone(), allocate array based upon size not capacity
- int capacity = calculateCapacity(elementData, size);
- SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
- ensureCapacityInternal(size);
- Object[] a = elementData;
- // Read in all elements in the proper order.
- for (int i=0; i<size; i++) {
- a[i] = s.readObject();
- }
- }
- }
可以看到在序列化的时候是把 elementData 里面的元素逐个取出来放到 ObjectOutputStream 里面的; 而在反序列化的时候也是把元素逐个拿出来放回到 elementData 里面的;
这样繁琐的操作, 其中最重要的一个好处就是节省空间, 因为 elementData 的大小是大于 ArrayList 中实际元素个数的. 所以没必要将 elementData 整个序列化.
二, 构造函数
ArrayList 的构造函数主要就是要初始化 elementData 和 size, 但是其中有一个还有点意思
- public ArrayList(Collection<? extends E> c) {
- elementData = c.toArray();
- if ((size = elementData.length) != 0) {
- // c.toArray might (incorrectly) not return Object[] (see 6260652)
- if (elementData.getClass() != Object[].class)
- elementData = Arrays.copyOf(elementData, size, Object[].class);
- } else {
- // replace with empty array.
- this.elementData = EMPTY_ELEMENTDATA;
- }
- }
可以看到在 Collection.toArray()之后又判断了他的 Class 类型是不是 Object[].class, 这个也注释了是一个 bug, 那么在什么情况下会产生这种情况呢?
- // test 6260652
- private static void test04() {
- List<String> list = Arrays.asList("111", "222", "333");
- System.out.println(list.getClass());
- Object[] objects = list.toArray();
- System.out.println(objects.getClass());
- }
打印:
- class java.util.Arrays$ArrayList
- class [Ljava.lang.String;
这里可以看到 objects 的 class 居然是[Ljava.lang.String, 同时这里的 ArrayList 是 java.util.Arrays.ArrayList
- // java.util.Arrays.ArrayList
- public static <T> List<T> asList(T... a) {
- return new ArrayList<>(a);
- }
- private static class ArrayList<E> extends AbstractList<E>
- implements RandomAccess, java.io.Serializable {
- private final E[] a;
- ArrayList(E[] array) {
- a = Objects.requireNonNull(array);
- }
- ...
- }
从以上例子可以看到, 由于直接将外部数组的引用直接赋值给了 List 内部的数组, 所以 List 所持有的数组类型是未知的. 之前讲过数组是协变的, 不支持泛型, 所以只有值运行时再知道数组的具体类型, 所以导致了以上的 bug; 难怪《Effective Java》里面讲数组的协变设计, 不是那么完美.
三, 常用方法
由于 ArrayList 是基于数组的, 所以他的 API 基本都是基于 System.arraycopy()实现的;
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
可以看到这是一个 native 方法, 并且 JVM 有对这个方法做特殊的优化处理,
- private static void test05() {
- int[] s1 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
- int[] s2 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
- System.arraycopy(s1, 3, s2, 6, 2);
- System.out.println(Arrays.toString(s1));
- System.out.println(Arrays.toString(s2));
- }
打印:
- [1, 2, 3, 4, 5, 6, 7, 8, 9]
- [1, 2, 3, 4, 5, 6, 4, 5, 9]
- private static void test06() {
- int[] s1 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
- int[] s2 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
- System.arraycopy(s1, 3, s2, 6, 5);
- System.out.println(Arrays.toString(s1));
- System.out.println(Arrays.toString(s2));
- }
- // 抛出异常 `java.lang.ArrayIndexOutOfBoundsException`
- private static void test07() {
- int[] s1 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
- int[] s2 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
- System.arraycopy(s1, 8, s2, 5, 3);
- System.out.println(Arrays.toString(s1));
- System.out.println(Arrays.toString(s2));
- }
- // 抛出异常 `java.lang.ArrayIndexOutOfBoundsException`
从上面的测试可以了解到:
System.arraycopy()就是将源数组的元素复制到目标数组中,
如果源数组和目标数组是同一个数组, 就可以实现数组内元素的移动,
源数组和目标数组的下标越界, 都会抛出
- ArrayIndexOutOfBoundsException
- .
同时在 ArrayList 进行数组操作的时候都会进行安全检查, 包括下标检查和容量检查
- // 容量检查
- 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;
- if (minCapacity> minExpand) {
- ensureExplicitCapacity(minCapacity);
- }
- }
四, 迭代方式
1. 随机访问
由于 ArrayList 实现了 RandomAccess 接口, 它支持通过索引值去随机访问元素.
- for (int i=0, len = list.size(); i <len; i++) {
- String s = list.get(i);
- }
2. 迭代器遍历
这其实就是迭代器模式
- Iterator iter = list.iterator();
- while (iter.hasNext()) {
- String s = (String)iter.next();
- }
3. 增强 for 循环遍历
这其实是一个语法糖
- for (String s : list) {
- ...
- }
4. 增强 for 循环遍历的实现
对于 ArrayList
- public void test_List() {
- List<String> list = new ArrayList<>();
- list.add("a");
- list.add("b");
- for (String s : list) {
- System.out.println(s);
- }
- }
使用 javap -v 反编译
- Code:
- stack=2, locals=4, args_size=1
- ...
- 27: invokeinterface #7, 1 // InterfaceMethod java/util/List.iterator:()Ljava/util/Iterator;
- 32: astore_2
- 33: aload_2
- 34: invokeinterface #8, 1 // InterfaceMethod java/util/Iterator.hasNext:()Z
- ...
这里可以很清楚的看到, 其实是通过 Iterator 迭代器实现的
对于 Array
- public void test_array() {
- String[] ss = {"a", "b"};
- for (String s : ss) {
- System.out.println(s);
- }
- }
使用 javap -v 反编译
- Code:
- stack=4, locals=6, args_size=1
- 0: iconst_2
- 1: anewarray #2 // class java/lang/String
- 4: dup
- 5: iconst_0
- 6: ldc #3 // String a
- 8: aastore
- 9: dup
- 10: iconst_1
- 11: ldc #4 // String b
- 13: aastore
- 14: astore_1
- 15: aload_1
- 16: astore_2
- 17: aload_2
- 18: arraylength
- 19: istore_3
- 20: iconst_0
- 21: istore 4 // 将一个数值从操作数栈存储到局部变量表
- 23: iload 4 // 将局部变量加载到操作栈
- 25: iload_3
- 26: if_icmpge 49
- 29: aload_2
- 30: iload 4
- 32: aaload
- 33: astore 5
- 35: getstatic #5 // Field java/lang/System.out:Ljava/io/PrintStream;
- 38: aload 5
- 40: invokevirtual #6 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
- 43: iinc 4, 1
- 46: goto 23
- 49: return
这里只能到导致看到是在做一些存取操作, 但也不是很清楚, 所以可以直接反编译成 java 代码
- public void test_array() {
- String[] ss = new String[]{"a", "b"};
- String[] var2 = ss;
- int var3 = ss.length;
- for(int var4 = 0; var4 < var3; ++var4) {
- String s = var2[var4];
- System.out.println(s);
- }
- }
现在就能很清楚的看到其实是通过随机存储 (下标访问) 的方式实现的;
五, fail-fast 机制
fail-fast 是说当并发的对容器内容进行操作时, 快速的抛出 ConcurrentModificationException; 但是这种快速失败操作无法得到保证, 它不能保证一定会出现该错误, 但是快速失败操作会尽最大努力抛出 ConcurrentModificationException 异常. 所以我们程序的正确性不能完全依赖这个异常, 只应用于 bug 检测.
- protected transient int modCount = 0;
- private void checkForComodification() {
- if (ArrayList.this.modCount != this.modCount)
- throw new ConcurrentModificationException();
- }
在 ArrayList 的 Iterator 和 SubList 中, 每当进行内存操作时, 都会先使用 checkForComodification 来检测内容是否已修改.
总结
ArrayList 整体来看就是一个更加安全和方便的数组, 但是他的插入和删除操作也实在是蛋疼, 对于这一点其实可以通过树或者跳表来解决.
来源: https://www.cnblogs.com/sanzao/p/10156117.html