189 8069 5689

JDK源码分析（3）之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 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
可以看到在序列化的时候是把elementData里面的元素逐个取出来放到ObjectOutputStream里面的；而在反序列化的时候也是把元素逐个拿出来放回到elementData里面的；
这样繁琐的操作，其中最重要的一个好处就是节省空间，因为elementData的大小是大于ArrayList中实际元素个数的。所以没必要将elementData整个序列化。
二、构造函数
ArrayList的构造函数主要就是要初始化elementData和size，但是其中有一个还有点意思
public ArrayList(Collection 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 6260652private static void test04() {
  List list = Arrays.asList("111", "222", "333");
  System.out.println(list.getClass());
  Object[] objects = list.toArray();
  System.out.println(objects.getClass());
}

打印：class java.util.Arrays$ArrayListclass [Ljava.lang.String;
这里可以看到objects的class居然是[Ljava.lang.String，同时这里的ArrayList是java.util.Arrays.ArrayList
// java.util.Arrays.ArrayListpublic static  List asList(T... a) {  return new ArrayList<>(a);
}private static class ArrayList extends AbstractList  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 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整体来看就是一个更加安全和方便的数组，但是他的插入和删除操作也实在是蛋疼，对于这一点其实可以通过树或者跳表来解决。
            
            
                        

            本文题目：JDK源码分析（3）之ArrayList相关            

            网站地址：http://cdxtjz.com/article/ihdpie.html

其他资讯