JDK-ArrayList源码分析

ArrayList源码解析

ArrayList是List的一种实现，是为存放不定长数据而设计的一种集合类，是List接口的一种实现方案。 底层使用数组实现，当数组中数据达到数组的最大容量时，会自动扩大容量至原来的1.5倍或至容纳所有元素的最小的容量。

ArrayList特点：

• 底层使用的是数组

• 随机查询效率极快

• 尾部追加效率高，头部追加效率低

• 线程不安全

• 值可重复，也可以为null

这是一个标记性接口，接口内部没有定义任何内容，在这里，仅仅作为一个标记，标明该类可以被序列化，具体的实现交由jvm来做。

序列化的作用 序列化的对象方便与传输或者是保存到文件(对象的持久化)。

1、方便网络传输。尤其是在套接字中传输对象时使用。

2、可以持久化保存对象的状态（各个属性值）。

对象输入/输出流

ObjectInputStream(InputStream in) 构造一个对象输入流，调用其readObject(Object obj) 可以读入一个对象。

ObjectOutputStream(OutputStream out) 构造一个对象输出流，调用其writeObject(Object obj) 可以写出一个对象。

代码演示

 public class ArrayListTest {
     public static void main(String[] args) {
 ​
        ArrayList list=new ArrayList<>();
        for(int i=1;i<1000;i++){
            list.add(i);
        }
         try {
             //将list序列化
             ObjectOutputStream objectOutputStream = new ObjectOutputStream(new FileOutputStream("D:/hello.txt"));
             objectOutputStream.writeObject(list);
             objectOutputStream.close();
             //反序列化
             ObjectInputStream objectInputStream = new ObjectInputStream(new FileInputStream("D:/hello.txt"));
             ArrayList arrayList= (ArrayList) objectInputStream.readObject();
             objectInputStream.close();
             //反序列化后的结果进行输出
             for (Integer integer : arrayList) {
                 System.out.println(integer);
             }
         } catch (FileNotFoundException e) {
             e.printStackTrace();
         } catch (IOException e) {
             e.printStackTrace();
         } catch (ClassNotFoundException e) {
             e.printStackTrace();
         }
 ​
     }
 }

标记性接口，接口内部没有任何属性与方法。只有实现这个接口后，然后在类中重写Object中的clone方法，然后通过类调用clone方法才能克隆成功，如果不实现这个接口，则会抛出CloneNotSupportedException(克隆不被支持)异常。

什么是clone？

clone就是创建一个对象的副本，该副本与源对象具有相同的状态 与 属性值，当然还有属性与方法。

克隆分为浅克隆与深克隆

简单概括：如果被克隆的对象内部的属性值，是另一个对象的引用，那么在克隆时，

浅克隆，克隆的只是对象的引用。

深克隆，将会把这个属性值引用的对象也克隆下来。

ArrayList中的拷贝是浅拷贝，下面用代码验证一下。

 public class ArrayListTest2 {
     public static void main(String[] args) {
         ArrayList list=new ArrayList<>();
         //创建一个Studnet对象Anna
         Student anna = new Student("Anna");
 ​
         list.add(anna);
 ​
         //克隆这个list集合
         ArrayList listClone = (ArrayList)list.clone();
         //输出看看效果
         System.out.println("list: "+list);
         System.out.println("listClone: "+listClone);
         //判断这个集合的地址是否相等。
         System.out.println("list的地址与listClone的地址相同吗: "+(list==listClone));
 ​
         //修改list中的对象属性
         list.get(0).setName("jack");
         //查看list 与 listClone 中的元素变化
         System.out.println("list: "+list);
         System.out.println("listClone: "+listClone);
         //说明list 与 listClone 中储存的都是 对象的引用。也说明ArrayList的拷贝是浅拷贝
     }
 }

还是一个标记性接口。表示这个类可以实现快速随机访问。

集合的工具类Collections中的binarySearch方法很好地解释RandomAccess接口的作用。

 public static 
 int binarySearch(List> list, T key) {
     if (list instanceof RandomAccess || list.size() 
源码中表示，如果该List是RandomAccess的子类，则执行Collections.indexedBinarySearch(list, key);方法，否则执行Collections.iteratorBinarySearch(list, key);方法。
 
这两个方法有什么区别呢
 
 private static 
 int indexedBinarySearch(List> list, T key) {
     int low = 0;
     int high = list.size()-1;
 ​
     while (low <= high) {
         int mid = (low + high) >>> 1;
         Comparable midVal = list.get(mid);
         int cmp = midVal.compareTo(key);
 ​
         if (cmp < 0)
             low = mid + 1;
         else if (cmp > 0)
             high = mid - 1;
         else
             return mid; // key found
     }
     return -(low + 1);  // key not found
 }
 ​
 private static 
 int iteratorBinarySearch(List> list, T key)
 {
     int low = 0;
     int high = list.size()-1;
     ListIterator> i = list.listIterator();
 ​
     while (low <= high) {
         int mid = (low + high) >>> 1;
         Comparable midVal = get(i, mid);
         int cmp = midVal.compareTo(key);
 ​
         if (cmp < 0)
             low = mid + 1;
         else if (cmp > 0)
             high = mid - 1;
         else
             return mid; // key found
     }
     return -(low + 1);  // key not found
 }
 
上述两个方法的源码表示，实现了RandomAccess接口的List使用索引遍历，而未实现RandomAccess接口的List使用迭代器遍历。 而不同的数据结构，用这两种遍历方式的效率也不一样。下面用ArrayList和LinkedList来探寻这两种遍历方式的效率如何。
 
 public class ListTest {
     public static void main(String[] args) {
         ArrayList arrayList=new ArrayList();
         LinkedList linkedList=new LinkedList<>();
         for(int i=1;i<10000;i++){
             arrayList.add(i);
             linkedList.add(i);
         }
 ​
         System.out.println("ArrayList的for循环花费时间："+ArrayListFor(arrayList));
         System.out.println("ArrayList的Iterator循环花费时间："+ArrayListIterator(arrayList));
         System.out.println("LinkedList的for循环花费时间："+LinkedListFor(linkedList));
         System.out.println("LinkedList的Iterator循环花费时间："+LinkedListIterator(linkedList));
 ​
     }
 ​
     public static long ArrayListFor(ArrayList list){
         long start = System.currentTimeMillis();
         for(int i=0;i 
结果如图：
 
 
 
字段 
 
 private static final int DEFAULT_CAPACITY = 10;
 ​
 
 private static final Object[] EMPTY_ELEMENTDATA = {};
 ​
 
 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 ​
 
 transient Object[] elementData; // non-private to simplify nested class access
 ​
 
 private int size;
 
elementData为什么要被transient 修饰？？？
 
在ArrayList中有两个方法，private void writeObject(java.io.ObjectOutputStream s) 和private void readObject(java.io.ObjectInputStream s)，这两个方法是用来让ArrayList自己控制自己的序列化。
 
 
 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()
     //写入size
     s.writeInt(size);
 ​
     // Write out all elements in the proper order.
     //写入ArrayList中的元素，可以看到，这里写入的是实际存储元素的大小，而非实际容量。
     for (int i=0; i