ArrayList源码解析

goodbye
1,352 阅读13分钟

ArrayList源码解析

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

ArrayList特点：

  • 底层使用的是数组
  • 随机查询效率极快
  • 尾部追加效率高，头部追加效率低
  • 线程不安全
  • 值可重复，也可以为null

ArrayList的继承关系

Serializable 接口

这是一个标记性接口，接口内部没有定义任何内容，在这里，仅仅作为一个标记，标明该类可以被序列化，具体的实现交由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<Integer> 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<Integer> arrayList= (ArrayList<Integer>) 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();
         }
 ​
     }
 }

Cloneable接口

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

什么是clone？

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

克隆分为浅克隆与深克隆

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

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

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

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

 public class ArrayListTest2 {
     public static void main(String[] args) {
         ArrayList<Student> 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的拷贝是浅拷贝
     }
 }

RandomAccess接口

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

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

 public static <T>
 int binarySearch(List<? extends Comparable<? super T>> list, T key) {
     if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
         return Collections.indexedBinarySearch(list, key);
     else
         return Collections.iteratorBinarySearch(list, key);
 }

源码中表示，如果该List是RandomAccess的子类，则执行Collections.indexedBinarySearch(list, key);方法，否则执行Collections.iteratorBinarySearch(list, key);方法。

这两个方法有什么区别呢

 private static <T>
 int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {
     int low = 0;
     int high = list.size()-1;
 ​
     while (low <= high) {
         int mid = (low + high) >>> 1;
         Comparable<? super T> 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 <T>
 int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key)
 {
     int low = 0;
     int high = list.size()-1;
     ListIterator<? extends Comparable<? super T>> i = list.listIterator();
 ​
     while (low <= high) {
         int mid = (low + high) >>> 1;
         Comparable<? super T> 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<Integer> arrayList=new ArrayList();
         LinkedList<Integer> 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<list.size();i++){
             list.get(i);
         }
         long end = System.currentTimeMillis();
         return end-start;
     }
     public static long ArrayListIterator(ArrayList list){
         long start = System.currentTimeMillis();
         Iterator iterator = list.iterator();
         while(iterator.hasNext()){
             iterator.next();
         }
         long end = System.currentTimeMillis();
         return end-start;
     }
     public static long LinkedListFor(LinkedList list){
         long start = System.currentTimeMillis();
         for(int i=0;i<list.size();i++){
             list.get(i);
         }
         long end = System.currentTimeMillis();
         return end-start;
     }
     public static long LinkedListIterator(LinkedList list){
         long start = System.currentTimeMillis();
         Iterator iterator = list.iterator();
         while(iterator.hasNext()){
             iterator.next();
         }
         long end = System.currentTimeMillis();
         return end-start;
     }
 ​
 ​
 }

结果如图：

字段

 /**
  * Default initial capacity.
  *  默认初始化容量
  */
 private static final int DEFAULT_CAPACITY = 10;
 ​
 /**
  * Shared empty array instance used for empty instances.
  * static修饰的空数组，当指定默认初始化容量为0时，赋值给elementData，避免了重复创建空数组
  */
 private static final Object[] EMPTY_ELEMENTDATA = {};
 ​
 /**
  * Shared empty array instance used for default sized empty instances. We
  * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
  * first element is added.
  * static修饰的空数组，当调用无参构造方法时，赋值给elementData，主要作用为，在添加第一个元素前，
  *标记该ArrayList是由无参构造方法创建的，便于将容量初始化为DEFAULT_CAPACITY = 10，同时也避免了重复创建空数组
  */
 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 ​
 /**
  * The array buffer into which the elements of the ArrayList are stored.
  * The capacity of the ArrayList is the length of this array buffer. Any
  * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
  * will be expanded to DEFAULT_CAPACITY when the first element is added.
  * 集合中真正存储元素的容器
  */
 transient Object[] elementData; // non-private to simplify nested class access
 ​
 /**
  * The size of the ArrayList (the number of elements it contains).
  * 集合中元素的个数
  * @serial
  */
 private int size;

elementData为什么要被transient 修饰？？？

在ArrayList中有两个方法，private void writeObject(java.io.ObjectOutputStream s) 和private void readObject(java.io.ObjectInputStream s)，这两个方法是用来让ArrayList自己控制自己的序列化。

 /**
  * Save the state of the <tt>ArrayList</tt> instance to a stream (that
  * is, serialize it).
  *
  * @serialData The length of the array backing the <tt>ArrayList</tt>
  *             instance is emitted (int), followed by all of its elements
  *             (each an <tt>Object</tt>) in the proper order.
  */
 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<size; i++) {
         s.writeObject(elementData[i]);
     }
 ​
     if (modCount != expectedModCount) {
         throw new ConcurrentModificationException();
     }
 }
 ​
 /**
  * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
  * deserialize it).
  */
 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();
         }
     }
 }

这样做的目的其实是，ArrayList的底层是数组，而这个数组是动态变化的。它通常会预留一些容量，等容量不足时再扩充容量。所以其中会有大量未被使用的容量，如果对这些容量也进行序列化，无疑是一种浪费。

构造方法

 /**
  * Constructs an empty list with the specified initial capacity.
  *
  * @param  initialCapacity  the initial capacity of the list
  * @throws IllegalArgumentException if the specified initial capacity
  *         is negative
  * 创建指定初始化容量的ArrayList
  */
 public ArrayList(int initialCapacity) {
     if (initialCapacity > 0) {
         this.elementData = new Object[initialCapacity];
     } else if (initialCapacity == 0) {
         this.elementData = EMPTY_ELEMENTDATA;
     } else {
         throw new IllegalArgumentException("Illegal Capacity: "+
                                            initialCapacity);
     }
 }
 ​
 /**
  * Constructs an empty list with an initial capacity of ten.
  * 创建一个初始容量为10的空数组。
  * 刚创建的时候是空的，也就是DEFAULTCAPACITY_EMPTY_ELEMENTDATA这个空数组，在添加第一个元素时，会被扩容为默认初始容量 DEFAULT_CAPACITY = 10，
  */
 public ArrayList() {
     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
 }
 ​
 /**
  * Constructs a list containing the elements of the specified
  * collection, in the order they are returned by the collection's
  * iterator.
  * 创建新的集合，把传入的集合中的元素，作为本集合的元素。
  * @param c the collection whose elements are to be placed into this list
  * @throws NullPointerException if the specified collection is null
  */
 public ArrayList(Collection<? extends E> c) {
     elementData = c.toArray();
     if ((size = elementData.length) != 0) {
         // c.toArray might (incorrectly) not return Object[] (see 6260652)
         /**
         * c.toArray 可能返回的不是 Object[] 类型 ？？？？
         * 可是Collection接口中明明定义的是    Object[] toArray();
         * 原来是，子类重写父类时，可以重写父类中方法的返回值。get！！
         * 所以这里如果elementData不是Object[]类型的话，就需要重新拷贝为Object[]类型
         */
         if (elementData.getClass() != Object[].class)
             elementData = Arrays.copyOf(elementData, size, Object[].class);
     } else {
         // replace with empty array.
         this.elementData = EMPTY_ELEMENTDATA;
     }
 }

常用方法

public boolean add(E e) 向ArrayList末尾添加一个元素

 //添加一个元素
 public boolean add(E e) {
         ensureCapacityInternal(size + 1);  // Increments modCount!!
         elementData[size++] = e;
         return true;
     }
 //这一步是确保集合的容量足够用来添加元素
     private void ensureCapacityInternal(int minCapacity) {
         ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
     }
 //计算所需容量的大小
     private static int calculateCapacity(Object[] elementData, int minCapacity) {
         /**
         *如果是通过调用无参构造函数创建的集合，elementData 就会被设为DEFAULTCAPACITY_EMPTY_ELEMENTDATA，
         *这一步就是通过DEFAULTCAPACITY_EMPTY_ELEMENTDATA来判断，该集合是不是通过无参构造方法创建的，
         *如果是，那么所需容量大小最小被设为minCapacity=10，这就是为什么说ArrayList的默认初始容量为10
         */
         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
             return Math.max(DEFAULT_CAPACITY, minCapacity);
         }
         return minCapacity;
     }
 //保证集合容量足够大的关键步骤，如果集合容量不够大，就进行扩容
     private void ensureExplicitCapacity(int minCapacity) {
         //modCount 是操作数，用来纪录这个集合被操作的次数。
         modCount++;
 ​
         // overflow-conscious code
         if (minCapacity - elementData.length > 0)
             grow(minCapacity);
     }
 //扩容算法的具体实现，每次扩容至原容量的1.5倍，如果最小要求的容量大于原容量的1.5倍，就扩容至最小要求的容量
     private void grow(int minCapacity) {
         // overflow-conscious code
         int oldCapacity = elementData.length;
         int newCapacity = oldCapacity + (oldCapacity >> 1);
         if (newCapacity - minCapacity < 0)
             newCapacity = minCapacity;
         if (newCapacity - MAX_ARRAY_SIZE > 0)
             newCapacity = hugeCapacity(minCapacity);
         // minCapacity is usually close to size, so this is a win:
         elementData = Arrays.copyOf(elementData, newCapacity);
     }

执行流程

add
ensureCapacityInternal
确保容量足够大
走够大
不够大
ensureExplicitCapacity
容量不足时，扩展容量
calculateCapacity
计算所需的最小容量
无操作
grow
扩容
elementData[size++] = e
末尾添加元素

get(int index) 获取指定索引位置的元素

 public E get(int index) {
     //检查索引是否越界
     rangeCheck(index);
     //返回元素
     return elementData(index);
 }
 ​
 private void rangeCheck(int index) {
     if (index >= size)
         throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 }
 ​
 E elementData(int index) {
     return (E) elementData[index];
 }

执行流程

  1. 检查下标是否越界
  2. 返回元素

remove(int index)删除指定索引位置的元素

 public E remove(int index) {
     //检查下标是否越界
     rangeCheck(index);
     //操作数自增
     modCount++;
     E oldValue = elementData(index);
     //纪录下需要移动的元素个数
     int numMoved = size - index - 1;
     //移动的元素等于0时，就不需要移动
     if (numMoved > 0)
         //移动数组元素
         System.arraycopy(elementData, index+1, elementData, index,
                          numMoved);
     //数组最末尾的元素置空，以便GC将它回收，同时size--
     elementData[--size] = null; // clear to let GC do its work
 ​
     return oldValue;
 }
     //检查下标是否越界
     private void rangeCheck(int index) {
         if (index >= size)
             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
     }
     //取出元素
     E elementData(int index) {
         return (E) elementData[index];
     }

执行流程

  1. 检查下标是否越界
  2. 将index后面的元素集体前移一个位置
  3. size--

remove(Object o)删除指定元素值的元素

 //删除指定元素
 public boolean remove(Object o) {
     //因为null不能调用equals方法，所以要和其他非null元素分开处理
     if (o == null) {
         for (int index = 0; index < size; index++)
             if (elementData[index] == null) {
                 fastRemove(index);
                 return true;
             }
     } else {
         for (int index = 0; index < size; index++)
             if (o.equals(elementData[index])) {
                 fastRemove(index);
                 return true;
             }
     }
     return false;
 }
 ​
  private void fastRemove(int index) {
      //操作数++
         modCount++;
      //计算要移动的元素个数
         int numMoved = size - index - 1;
      //移动的元素等于0时，就不需要移动
         if (numMoved > 0)
             System.arraycopy(elementData, index+1, elementData, index,
                              numMoved);
         elementData[--size] = null; // clear to let GC do its work
     }

执行流程

  1. 找到该元素的下标
  2. 将该元素后面的元素集体向前移动一个位置
  3. size--

contains(Object o)是否包含某个元素

 //是否包含某个元素
 public boolean contains(Object o) {
     //如果找到这个元素，说明该元素存在。
     return indexOf(o) >= 0;
 }
 //查找元素在集合中的下标
     public int indexOf(Object o) {
         if (o == null) {
             for (int i = 0; i < size; i++)
                 if (elementData[i]==null)
                     return i;
         } else {
             for (int i = 0; i < size; i++)
                 if (o.equals(elementData[i]))
                     return i;
         }
         return -1;
     }

执行流程

  1. 遍历数组

retainAll(Collection c)求两个集合的交集

 public boolean retainAll(Collection<?> c) {
     //要求参数c不能为null
     Objects.requireNonNull(c);
     //batchRemove(c, true)代表取交集，batchRemove(c, false)代表取并集
     return batchRemove(c, true);
 }
 ​
 private boolean batchRemove(Collection<?> c, boolean complement) {
         final Object[] elementData = this.elementData;
     //r表示读的下标，w表示写的下标
         int r = 0, w = 0;
         boolean modified = false;
         try {
             //遍历自己的elementData，complement的值为true，表示取交集，值为false，表示取差集
             for (; r < size; r++)
                 if (c.contains(elementData[r]) == complement)
                     //从第一个元素位置重新写入元素
                     elementData[w++] = elementData[r];
         } finally {
             // Preserve behavioral compatibility with AbstractCollection,
             // even if c.contains() throws.
             //如果没有读完，就因为抛出异常而退出了，这里有补救措施
             if (r != size) {
                 //将没读完的元素添加到元素末尾
                 System.arraycopy(elementData, r,
                                  elementData, w,
                                  size - r);
                 w += size - r;
             }
             if (w != size) {
                 // clear to let GC do its work
                 //清除后面多余的元素，设为null，方便回收。
                 for (int i = w; i < size; i++)
                     elementData[i] = null;
                 modCount += size - w;
                 //修改容量
                 size = w;
                 modified = true;
             }
         }
         return modified;
     }
 ​

执行流程

  1. 遍历本集合元素，看是否包含在目标集合中。
  2. complement的值为true，表示取交集，值为false，表示取差集。
  3. 遍历的过程中，collection.contains（）方法可能会抛出异常而中断遍历，导致本集合中的元素没有读完。
  4. 如果本集合中的元素没有读完，就将剩下的元素，原封不动的添加到本集合末尾。
  5. 清除多余的元素

removeAll(Collection c)求两个集合的单方向差集

 public boolean removeAll(Collection<?> c) {
     Objects.requireNonNull(c);
     return batchRemove(c, false);
 }
 ​
 private boolean batchRemove(Collection<?> c, boolean complement) {
         final Object[] elementData = this.elementData;
     //r表示读的下标，w表示写的下标
         int r = 0, w = 0;
         boolean modified = false;
         try {
             //遍历自己的elementData，complement的值为true，表示取交集，值为false，表示取差集
             for (; r < size; r++)
                 if (c.contains(elementData[r]) == complement)
                     //从第一个元素位置重新写入元素
                     elementData[w++] = elementData[r];
         } finally {
             // Preserve behavioral compatibility with AbstractCollection,
             // even if c.contains() throws.
             //如果没有读完，就因为抛出异常而退出了，这里有补救措施
             if (r != size) {
                 //将没读完的元素添加到元素末尾
                 System.arraycopy(elementData, r,
                                  elementData, w,
                                  size - r);
                 w += size - r;
             }
             if (w != size) {
                 // clear to let GC do its work
                 //清除后面多余的元素，设为null，方便回收。
                 for (int i = w; i < size; i++)
                     elementData[i] = null;
                 modCount += size - w;
                 //修改容量
                 size = w;
                 modified = true;
             }
         }
         return modified;
     }
 ​

执行流程

跟retainAll的执行流程一样

序列化

序列化的作用

  1. 方便永久化存储对象
  2. 方便在网络中传输对象
  3. 可以用来创建对象副本

Serializable 序列化的工作机制：

序列化的时候系统会把当前类的 serialVersionUID 写入序列化的文件中（也可能是其他中介），当反序列化的时候系统会去检测文件中的 serialVersionUID ，看它是否和当前类的 serialVersionUID 一致，如果一致就说明序列化的类的版本和当前类的版本是相同的，这个时候可以成功反序列化，否则就说明当前类和序列化的类相比发生了某些变换，比如成员变量的数量，类型可能发生了改变，这个时候就会抛异常，反序列化失败。

１：当一个对象被序列化时，只保存对象的非静态成员变量（包括声明为private的变量），不能保存任何的成员方法和静态的成员变量。

２：如果一个对象的成员变量是一个对象，那么这个对象的数据成员也会被序列化。

３：如果一个可序列化的对象包含对某个不可序列化的对象的引用，那么整个序列化操作将会失败，并且会抛出一个NotSerializableException。我们可以将这个引用标记为transient，那么对象仍然可以序列化。

4 : 父类实现Serializable接口，子类没有实现Serializable接口，子类也能实现序列化。

探究默认的序列化方式，对不同类型属性的序列化结果。

 package src.top.goodbye.test.ListTest;
 //父类
 public class Animal {
     //不能对父类属性序列化
     protected String name;
 ​
     public Animal(String name) {
         this.name = name;
     }
 ​
     public Animal() {
     }
 }

 package src.top.goodbye.test.ListTest;
 ​
 import java.io.Serializable;
 //子类
 public class Dog extends Animal implements Serializable {
     //可以对子类普通属性序列化
     private String color;
     //不能对子类被transient修饰的属性序列化
     transient private Integer age;
     //不能对子类静态属性序列化
     private static String species="dog";
     public Dog() {
     }
 ​
     public Dog(String name, String color, int age) {
         super(name);
         this.color = color;
         this.age = age;
     }
 ​
     public Dog(String color, int age) {
         this.color = color;
         this.age = age;
     }
 ​
     @Override
     public String toString() {
         return String.format("父类的普通name属性=%s,\n子类的普通color属性=%s,\n子类的被transient修饰的 age属性=%d,\n子类的静态 species属性=%s",name,color,age,species);
     }
 }

 package src.top.goodbye.test.ListTest;
 ​
 import java.io.*;
 //测试类
 public class Test1 {
     public static void main(String[] args) {
         Dog dog=new Dog("可可","白色",2);
         try {
             //对象输出流
             ObjectOutputStream objectOutputStream = new ObjectOutputStream(new FileOutputStream("D:/SerializeTest"));
             //写出对象
             objectOutputStream.writeObject(dog);
             //对象写入流
             ObjectInputStream objectInputStream = new ObjectInputStream(new FileInputStream("D:/SerializeTest"));
             //写入对象
             Dog dogCopy = (Dog)objectInputStream.readObject();
             
             System.out.println(dogCopy);
 ​
         } catch (IOException e) {
             e.printStackTrace();
         } catch (ClassNotFoundException e) {
             e.printStackTrace();
         }
 ​
     }
 }

运行结果

  • 实现Serializable接口的父类的属性不会被序列化
  • 被transient修饰的属性，不会被序列化
  • 静态变量被所有的类实例共享，所以没必要进行序列化。这里虽然species属性被正常输出，但其实并没有被序列化

java还支持用户自定义类的序列化方式，来灵活的应对不同的场景。

可以在对象内部编写并实现下面两个函数，让类自己控制序列化

private void writeObject(java.io.ObjectOutputStream s)，

private void readObject(java.io.ObjectInputStream s)

注意 这两个方法的访问修饰符必须是private，但事实上，即使使用非private关键词修饰这两个方法，编译器也不会报错。但这样的话，jvm将调用默认的序列化方式进行序列化，而不会调用默认用户自定义的序列化函数。

例如 我想让 父类的普通name属性 和 子类的被transient修饰的 age属性 也被序列化。

 //父类方法没有做任何修改
 ​
 package src.top.goodbye.test.ListTest;
 ​
 public class Animal {
     protected String name;
 ​
     public Animal(String name) {
         this.name = name;
     }
 ​
     public Animal() {
     }
 }

 package src.top.goodbye.test.ListTest;
 ​
 import java.io.IOException;
 import java.io.Serializable;
 //子类增加了private void writeObject(java.io.ObjectOutputStream s)，  
 //private void readObject(java.io.ObjectInputStream s)两个方法
 public class Dog extends Animal implements Serializable {
     private String color;
     transient private Integer age;
     private static String species="dog";
     public Dog() {
     }
 ​
     public Dog(String name, String color, int age) {
         super(name);
         this.color = color;
         this.age = age;
     }
 ​
     public Dog(String color, int age) {
         this.color = color;
         this.age = age;
     }
 ​
     @Override
     public String toString() {
         return String.format("父类的普通name属性=%s,\n子类的普通color属性=%s,\n子类的被transient修饰的 age属性=%d,\n子类的静态 species属性=%s",name,color,age,species);
     }
 ​
     private void writeObject(java.io.ObjectOutputStream s){
         try {
             //写入普通属性
             s.defaultWriteObject();
             //手动写入被transient修饰的属性
             s.writeInt(age);
             //手动写入父类属性
             s.writeObject(name);
         } catch (IOException e) {
             e.printStackTrace();
         }
 ​
     }
     private void readObject(java.io.ObjectInputStream s){
         try {
             //读入普通属性
             s.defaultReadObject();
             //手动读入被transient修饰的属性
             this.age= s.readInt();
             //手动读入父类属性
             this.name=(String)s.readObject();
         } catch (IOException e) {
             e.printStackTrace();
         } catch (ClassNotFoundException e) {
             e.printStackTrace();
         }
 ​
     }
 }

 package src.top.goodbye.test.ListTest;
 ​
 import java.io.*;
 ​
 public class Test1 {
     public static void main(String[] args) {
         Dog dog=new Dog("可可","白色",2);
         try {
             ObjectOutputStream objectOutputStream = new ObjectOutputStream(new FileOutputStream("D:/SerializeTest"));
             objectOutputStream.writeObject(dog);
             ObjectInputStream objectInputStream = new ObjectInputStream(new FileInputStream("D:/SerializeTest"));
             Dog dogCopy = (Dog)objectInputStream.readObject();
             System.out.println(dogCopy);
 ​
         } catch (IOException e) {
             e.printStackTrace();
         } catch (ClassNotFoundException e) {
             e.printStackTrace();
         }
 ​
     }
 }

运行结果

看，父类的普通name属性 和 子类的被transient修饰的 age属性 也被还原了。

序列化小结

  • 欲实现序列化，要实现Serializable接口，这是一个标记性接口。
  • 默认序列化方式不能对父类的属性进行序列化。
  • 默认序列化方式不能对被transient修饰的属性序列化。
  • 不能对类的静态属性序列化，这样做也完全没必要。
  • 如果父类实现了Serializable接口，子类也能实现序列化。
  • 可以实现 private void writeObject(java.io.ObjectOutputStream s) 和 private void readObject(java.io.ObjectInputStream s)方法，来实现自定义序列化机制。
  • private void writeObject(java.io.ObjectOutputStream s) 和 private void readObject(java.io.ObjectInputStream s) 这两个方法必须被private修饰，返回值必须为void ，否则，jvm将调用默认的序列化方式进行序列化，而不会调用默认用户自定义的序列化函数。
  • 如果子类实现了Serializable接口，父类必须提供无参构造方法，因为在反序列化时，程序通过父类的无参构造方法创建父类对象。

ArrayList相关面试题

1. ArrayList如何扩容？

每次扩容至原容量的1.5倍，或所需最小容量。

2. ArrayList 频繁扩容导致添加性能急剧下降，如何处理？

可以在创建ArrayList时，调用带参构造方法，指定其初始容量。减少添加元素过程中的扩容次数。

效率对比

 //插入100W数据，效率对比
 public void Test1(){
     //不指定容量
     ArrayList<Integer> list1=new ArrayList<>();
     //指定容量
     ArrayList<Integer> list2=new ArrayList<>(1000000);
     //添加100W数据到list1
     long start1=System.currentTimeMillis();
     for (int i=0;i<1000000;i++){
         list1.add(i);
     }
     long end1=System.currentTimeMillis();
 ​
     //添加100W数据到list2
     long start2=System.currentTimeMillis();
     for (int i=0;i<1000000;i++){
         list2.add(i);
     }
     long end2=System.currentTimeMillis();
     //优化前耗时
     System.out.print("优化前：");
     System.out.println(end1-start1);
     //优化后耗时
     System.out.print("优化后：");
     System.out.println(end2-start2);
 ​
 ​
 }

3. ArrayList插入或删除元素是否一定比LinkedList慢？

实验测试

 public void Test2(){
     ArrayList<Integer> arrayList =new ArrayList<>();
     LinkedList<Integer> linkedList=new LinkedList<>();
     //向list1 和list2中 添加10w条数据
     for (int i = 0; i < 100000; i++) {
         arrayList.add(i);
         linkedList.add(i);
     }
 ​
     //ArrayList, LinkedList 头部添加元素效率对比
     //ArrayList头部添加1w条
     long start1=System.currentTimeMillis();
     for(int i=0;i<10000;i++){
         arrayList.add(0,i);
     }
     long end1=System.currentTimeMillis();
     System.out.println("---------ArrayList头部添加1w条数据耗时---------");
     System.out.println(end1-start1);
 ​
     //LinkedList头部添加1w条数据
     long start2=System.currentTimeMillis();
     for(int i=0;i<10000;i++){
         linkedList.add(0,i);
     }
     long end2=System.currentTimeMillis();
     System.out.println("---------LinkedList头部添加1w条数据耗时---------");
     System.out.println(end2-start2);
 ​
 ​
     //ArrayList, LinkedList 中间添加元素效率对比
     //ArrayList中间添加1w条
     long start3=System.currentTimeMillis();
     for(int i=0;i<10000;i++){
         int mid=arrayList.size()/2;
         arrayList.add(mid,i);
     }
     long end3=System.currentTimeMillis();
     System.out.println("---------ArrayList中间添加1w条数据耗时---------");
     System.out.println(end3-start3);
 ​
     //LinkedList中间添加10条数据
     long start4=System.currentTimeMillis();
     for(int i=0;i<10000;i++){
         int mid=linkedList.size()/2;
         linkedList.add(mid,i);
     }
     long end4=System.currentTimeMillis();
     System.out.println("---------LinkedList中间添加1w条数据耗时---------");
     System.out.println(end4-start4);
 ​
     //ArrayList, LinkedList 尾部添加元素效率对比
     //ArrayList尾部添加1w条
     long start5=System.currentTimeMillis();
     for(int i=0;i<10000;i++){
         arrayList.add(i);
     }
     long end5=System.currentTimeMillis();
     System.out.println("---------ArrayList尾部添加1w条数据耗时---------");
     System.out.println(end5-start5);
 ​
     //LinkedList尾部添加1w条数据
     long start6=System.currentTimeMillis();
     for(int i=0;i<10000;i++){
         linkedList.add(i);
     }
     long end6=System.currentTimeMillis();
     System.out.println("---------LinkedList尾部添加1w条数据耗时---------");
     System.out.println(end6-start6);
 ​
 ​
 ​
 }

头部插入中间插入尾部插入
ArrayList5012290
LinkedList220310

底层原理

  • ArrayList通过数组的拷贝，实现元素的添加与删除。
  • LinkedList通过修改元素的pre和next指针实现添加与删除元素。

效率分析

  • 头部插入：

    • ArrayList需要将集合中所有元素后移一位，效率低
    • LinkedList只需要修改头部指针，效率高。

  • 中间插入：

    • ArrayList需要将集合中一半的元素后移一位

    • LinkedList需要遍历集合中一半的元素

    两者的时间复杂度都是O(n), 效率应当是相当的。但是ArrayList却比LinkedList快了10倍，这其实要归功于System.arraycopy 方法。 ArrayList中数组的拷贝都是用的这个方法，这是一个native方法，调用的是c语言的代码。

  • 尾部插入：

    • ArrayList只需要在数组后面添加一个元素就可以了。
    • LinkedList也是只需要修改尾部指针。
    • 两者性能差不多。

下面是几种拷贝方式的比较。数据大小是100w

 public void Test4(){
     int[] array=new int[1000000];
     
     //System.arraycopy 方式
     int[] arraycopy1=new int[1000000];
     long start = System.currentTimeMillis();
     System.arraycopy(array,0,arraycopy1,0,array.length);
     long end = System.currentTimeMillis();
     System.out.println("-----------System.arrayList耗时-----------");
     System.out.println(end-start);
 ​
     //fori循环方式
     int[] arraycopy2=new int[1000000];
     long start2=System.currentTimeMillis();
     for(int i=0;i<array.length;i++){
         arraycopy2[i]=array[i];
     }
     long end2 = System.currentTimeMillis();
     System.out.println("-----------fori耗时-----------");
     System.out.println(end2-start2);
 ​
     //增强for方式
     int[] arraycopy3=new int[1000000];
     long start3=System.currentTimeMillis();
     int j=0;
     for(int i:array)
         arraycopy3[j++]=i;
 ​
     long end3 = System.currentTimeMillis();
     System.out.println("-----------增强for耗时-----------");
     System.out.println(end3-start3);
 ​
     //iterator 方式
     int[] arraycopy4=new int[1000000];
     PrimitiveIterator.OfInt iterator = Arrays.stream(array).iterator();
     long start4=System.currentTimeMillis();
     j=0;
 ​
     while(iterator.hasNext()){
         arraycopy4[j++]= iterator.nextInt();
     }
     long end4= System.currentTimeMillis();
     System.out.println("-----------iterator耗时-----------");
     System.out.println(end4-start4);
 }

4. ArrayList 是线程安全的吗？

不是，ArrayList中没有声明线程安全的方法。但是集合框架中还有一个Vector集合，是线程安全的，但效率要慢的多。

除了Vector集合外，还可以使用为如下方式

 List<String> list = new ArrayList<>();
 List<String> synchronizedList = Collections.synchronizedList(list);

这样得到的synchronizedList也是线程安全的。

5. 如何复制某个ArrayList到另外一个ArrayList中去呢？你能列举几种？

  • for循环
  • ArrayList(Collection<? extends E> c)
  • ArrayList.clone();
  • ArrayList.add(Collection<? extends E> c)

6. ArrayList和LinkedList 的区别？

ArrayListLinkedList
底层数组链表
随机查找✔️ 支持❌不支持
实现Deque接口❌ 没有实现✔️ 实现了
效率比较头部插入慢，中间插入和尾部插入优于LinkedList头部插入快，中间插入慢，尾部插入与ArrayList差不多

\

avatar
文章
阅读
粉丝
相关推荐
CopyOnWriteArrayList源码分析
298阅读
 · 
2点赞
【源码分析】ArrayList源码分析
130阅读
 · 
1点赞
ArrayList源码分析
862阅读
 · 
3点赞
ArrayList源码解析
277阅读
 · 
2点赞
ArrayList源码分析
334阅读
 · 
7点赞
ArrayList源码分析
451阅读
 · 
2点赞
比较详细的ArrayList源码解析
226阅读
 · 
3点赞
ArrayList源码分析（入门版本）
924阅读
 · 
3点赞
ArrayList方法源码 整理
1.4k阅读
 · 
13点赞
浅看Android 中ArrayList源码
729阅读
 · 
2点赞

友情链接：