ArrayList源码解析

　　特性
　　实现了三个标记接口: RandomAccess, Cloneable, java.io.Serializable public class ArrayList extends AbstractList       implements List, RandomAccess, Cloneable, java.io.Serializable RandomAccess
　　支持随机访问（基于下标）,为了能够更好地判断集合是ArrayList还是LinkedList，从而能够更好选择更优的遍历方式，提高性能！ Cloneable
　　支持拷贝：实现Cloneable接口，重写clone方法、方法内容默认调用父类的clone方法。 浅拷贝 对基本数据类型进行值传递，对引用数据类型进行引用传递般的拷贝 public Object clone() throws CloneNotSupportedException {       Study study = (Study) super.clone();       return study; } 深拷贝 对基本数据类型进行值传递，对引用数据类型创建一个新的对象，并复制内容，这是深拷贝     public Object clone() throws CloneNotSupportedException {         Study s = (Study) super.clone();         s.setScore(this.score.clone());         return s;     }
　　java的传参有基本类型和引用类型传参,参数传递时拷贝的都是栈中的内容。此处大概分为三种情况  基本类型,存储在栈中所以拷贝的就是真实的值，修改后不影响原值 引用类型:栈中内容为对象引用,拷贝的也为引用 修改改变的是引用所指向的对象,由于引用的同一个对象，所以元对象改变了 String:虽然String也是引用类型 但于String是不可变对象 在修改时会讲引用指向一个新的对象，所已他们的引用变得不同了，当然不会改变原值 Serializable
　　序列化：将对象状态转换为可保持或传输的格式的过程。与序列化相对的是反序列化，它将流转换为对象。这两个过程结合起来，可以轻松地存储和传输数据，在Java中的这个Serializable接口其实是给jvm看的，通知jvm，我不对这个类做序列化了，你(jvm)帮我序列化就好了。如果我们没有自己声明一个serialVersionUID变量,接口会默认生成一个serialVersionUID，默认的serialVersinUID对于class的细节非常敏感，反序列化时可能会导致InvalidClassException这个异常（每次序列化都会重新计算该值） AbstractList
　　继承了AbstractList ，说明它是一个列表，拥有相应的增，删，查，改等功能。 List
　　为什么继承了 AbstractList 还需要 实现List 接口？
　　在StackOverFlow 中 得票最高的答案的回答者说他问了当初写这段代码的 Josh Bloch，得知这就是一个写法错误。 I’ve asked Josh Bloch, and he informs me that it was a mistake.He used to think, long ago, that there was some value in it, but he since ＂saw the light＂.Clearly JDK maintainers haven’t considered this to be worth backing out later. 基本属性         /**          * 序列化版本号（类文件签名），如果不写会默认生成          * 类内容的改变会影响签名变化，导致反序列化失败          */         private static final long serialVersionUID = 8683452581122892189L;         /**          * 如果实例化时未指定容量，则在初次添加元素时会进行扩容使用此容量作为数组长度          */         private static final int DEFAULT_CAPACITY = 10;         /**          * static修饰，所有的未指定容量的实例(也未添加元素)共享此数组          * 两个空的数组有什么区别呢？          * 就是第一次添加元素时知道该 elementData 从空的构造函数还是有参构造函数被初始化的。          * 以便确认如何扩容。空的构造器则初始化为10，有参构造器则按照扩容因子扩容          */         private static final Object[] EMPTY_ELEMENTDATA = {};         private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};         /**          * arrayList真正存放元素的地方，长度大于等于size          */         transient Object[] elementData;         /**          * arrayList中的元素个数          */         private int size; 构造器         /**          * 无参构造器，构造一个容量大小为 10 的空的 list 集，          * 但构造函数只是给 elementData 赋值了一个空的数组，          * 是在第一次添加元素时容量扩大至 10 的。          */         public ArrayList() {             this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;         }          /**          * 当使用无参构造函数时是把DEFAULTCAPACITY_EMPTY_ELEMENTDATA 赋值给 elementData。          * 当initialCapacity 为零时则是把 EMPTY_ELEMENTDATA 赋值给 elementData。           * 当initialCapacity大于零初始化一个大小为initialCapacity的object数组并赋值给elementData。          * @param initialCapacity 初始大小          */         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);             }         }          /**          * 将 Collection 转化为数组，数组长度赋值给 size。           * 如果 size 不为零，则判断 elementData 的 class 类型是否为 ArrayList，不是的话则做一次转换。          * 如果 size 为零，则把 EMPTY_ELEMENTDATA 赋值给 elementData，相当于new ArrayList(0)。          * @param c           */         public ArrayList(Collection<? extends E> c) {             Object[] a = c.toArray();             if ((size = a.length) != 0) {                 if (c.getClass() == ArrayList.class) {                     elementData = a;                 } else {                     elementData = Arrays.copyOf(a, size, Object[].class);                 }             } else {                 // 指向空数组                 elementData = EMPTY_ELEMENTDATA;             }         } 添加元素尾部插入(默认)        /**          * 每次添加元素到集合中时都会先确认下集合容量大小。然后将 size 自增 1赋值          * @param e          * @return          */         public boolean add(E e) {             ensureCapacityInternal(size + 1);             elementData[size++] = e;             return true;         }          /**          * 判断如果 elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA          * 就取 DEFAULT_CAPACITY 和 minCapacity 的最大值也就是 10。          * 这就是 EMPTY_ELEMENTDATA 与DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的区别所在。          * 同时也验证了上面的说法：使用无参构造函数时是在第一次添加元素时初始化容量为 10 的          * @param minCapacity          */         private void ensureCapacityInternal(int minCapacity) {             if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {                 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);             }             ensureExplicitCapacity(minCapacity);         }          /**          * 对modCount自增1,记录操作次数,如果minCapacity大于elementData的长度,则对集合进行扩容,          * 第一次添加元素时 elementData 的长度为零          * @param minCapacity          */         private void ensureExplicitCapacity(int minCapacity) {             modCount++;             if (minCapacity - elementData.length > 0)                 grow(minCapacity);         }
　　插入性能与linkedList对比         package jdk8.list;          import java.util.ArrayList;         import java.util.LinkedList;         import java.util.List;          /**          * arrayList 提前指定容量大小 插入性能对比linkedList          * @author zhangzhifeng           */         public class EffectTest {              public static void main(String[] args) {                 //不指定下标插入                 int length = 10000000;                 //指定容量时                 List arrayList = new ArrayList(length);                  List linkedList = new LinkedList();                 long start5 = System.currentTimeMillis();                 for(int i=0;i > 1);                 /**                  * 如果1.5倍太小的话，则将我们所需的容量大小赋值给newCapacity                  */                 if (newCapacity - minCapacity < 0)                     newCapacity = minCapacity;                 /**                  * 如果1.5倍太大或者我们需要的容量太大，                  * 那就直接拿 newCapacity = (minCapacity > MAX_ARRAY_SIZE) ?                  * Integer.MAX_VALUE : MAX_ARRAY_SIZE 来扩容                  */                 if (newCapacity - MAX_ARRAY_SIZE > 0)                     newCapacity = hugeCapacity(minCapacity);                 /**                  * 然后将原数组中的数据复制到大小为 newCapacity 的新数组中，并将新数组赋值给 elementData。                  */                 elementData = Arrays.copyOf(elementData, newCapacity);             }              /**              * 需要的长度溢出 抛OOM异常              * 大于数组长度最大值直接取Integer.max              * 否则拿最大长度MAX_ARRAY_SIZE              *              * @param minCapacity              * @return              */             private static int hugeCapacity(int minCapacity) {                 if (minCapacity < 0) // overflow                     throw new OutOfMemoryError();                 return (minCapacity > MAX_ARRAY_SIZE) ?                         Integer.MAX_VALUE :                         MAX_ARRAY_SIZE;             } 删除元素    public E remove(int index) {             /**              * 检查 index 是否合法              */             rangeCheck(index);             /**              * 操作数+1              */             modCount++;             E oldValue = elementData(index);             int numMoved = size - index - 1;             /**              * 判断要删除的元素是否是最后一个位              * 如果 index 不是最后一个，就从 index + 1 开始往后所有的元素都向前拷贝一份。              * 然后将数组的最后一个位置空,如果 index 是最后一个元素那么就直接将数组的最后一个位置空              */             if (numMoved > 0)                 System.arraycopy(elementData, index+1, elementData, index, numMoved);             /**              * 让指针最后指向空，进行gc              */             elementData[--size] = null;             return oldValue;         }          /**          * 当我们调用 remove(Object o) 时，会把 o 分为是否为空来分别处理。          * 对数组做遍历，找到第一个与 o 对应的下标 index          * 调用 fastRemove 方法，删除下标为 index 的元素。          * @param o          * @return          */         public boolean remove(Object o) {             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;         }          /**          * fastRemove(int index) 方法和 remove(int index) 方法基本全部相同。          * 它不用校验index的合法性和记录删除的元素          * @param index          */         private void fastRemove(int index) {             modCount++;             int numMoved = size - index - 1;             if (numMoved > 0)                 System.arraycopy(elementData, index+1, elementData, index,numMoved);             elementData[--size] = null;         } 迭代器 iterator        /**          * 创建迭代器          * @return          */         public Iterator iterator() {              return new Itr();         }          /**          * ArrayList 内部类          */         private class Itr implements Iterator {             /**              * 代表下一个要访问的元素下标              */             int cursor;             /**              * 代表上一个要访问的元素下标              */             int lastRet = -1;             /**              * 代表对 ArrayList 修改次数的期望值，初始值为 modCount              */             int expectedModCount = modCount;              /**              * 如果下一个元素的下标等于集合的大小 ，就证明到最后了              * @return              */             public boolean hasNext() {                 return cursor != size;             }             @SuppressWarnings(＂unchecked＂)             public E next() {                  //判断expectedModCount和modCount是否相等,ConcurrentModificationException                 checkForComodification();                 int i = cursor;                 //对 cursor 进行判断，看是否超过集合大小和数组长度                 if (i >= size)                     throw new NoSuchElementException();                 Object[] elementData = ArrayList.this.elementData;                 if (i >= elementData.length)                     throw new ConcurrentModificationException();                 // 自增 1。开始时，cursor = 0，lastRet = -1；每调用一次next方法，cursor和lastRet都会自增1。                 cursor = i + 1;                 //将cursor赋值给lastRet，并返回下标为 lastRet 的元素                 return (E) elementData[lastRet = i];             }             public void remove() {                 //判断 lastRet 的值是否小于 0                 if (lastRet < 0)                     throw new IllegalStateException();                 //判断expectedModCount和modCount是否相等,ConcurrentModificationException                 checkForComodification();                 try {                     //直接调用 ArrayList 的 remove 方法删除下标为 lastRet 的元素                     ArrayList.this.remove(lastRet);                     //将 lastRet 赋值给 curso                     cursor = lastRet;                     //将 lastRet 重新赋值为 -1，并将 modCount 重新赋值给 expectedModCount。                     lastRet = -1;                     expectedModCount = modCount;                 } catch (IndexOutOfBoundsException ex) {                     throw new ConcurrentModificationException();                 }             }             final void checkForComodification() {                 if (modCount != expectedModCount)                     throw new ConcurrentModificationException();             }         }
　　remove 方法的弊端。 只能进行remove操作，add、clear 等 Itr 中没有。 调用 remove 之前必须先调用 next。因为 remove 开始就对 lastRet 做了校验。而 lastRet 初始化时为 -1。 next 之后只可以调用一次 remove。因为 remove 会将 lastRet 重新初始化为 -1 fail-fast
　　fail-fast机制是java集合中的一种错误机制。当使用迭代器迭代时，如果发现集合有修改，则快速失败做出响应，抛出ConcurrentModificationException异常。这种修改有可能是其它线程的修改，也有可能是当前线程自己的修改导致的，比如迭代的过程中直接调用remove()删除元素等。另外，并不是java中所有的集合都有fail-fast的机制。比如，像最终一致性的ConcurrentHashMap、CopyOnWriterArrayList等都是没有fast-fail的。
　　fail-fast是怎么实现的?
　　ArrayList、HashMap中都有一个属性叫modCount，每次对集合的修改这个值都会加1，在遍历前记录这个值到expectedModCount中，遍历中检查两者是否一致，如果出现不一致就说明有修改，则抛出ConcurrentModificationException异常。 底层数组存/取元素效率非常的高(get/set)，时间复杂度是O(1)，而查找（比如：indexOf，contain），插入和删除元素效率不太高，时间复杂度为O(n)。 插入/删除元素会触发底层数组频繁拷贝，效率不高，还会造成内存空间的浪费，解决方案：linkedList 查找元素效率不高，解决方案：HashMap（红黑树） 注意事项创建时指定最好初始长度,减少扩容次数提升效率 arrayList.subList(beginIndex,endIndex) 返回其内部类 通过指定偏移量操作原对象。（源对象不可变此处有fast-fail检查） 属性 modCount 每次添加删除元素 +1 fast-fail 检查 List unmodifiableList = Collections.unmodifiableList(list); 不可变list 原对象可变 //构造器   UnmodifiableList(List<? extends E> list) {   super(list);   this.list = list; } //get 操作的原对象 public E get(int index) {return list.get(index);} //变更操作直接抛异常 public E set(int index, E element) {   throw new UnsupportedOperationException(); } public void add(int index, E element) {   throw new UnsupportedOperationException(); } public E remove(int index) {   throw new UnsupportedOperationException(); }
　　5.Arrays.asList(T..) 返回的是Arrays内部类。若传入的数组为基本类型,返回的list长度一直为1。 Integer[] array = {1,2,3}; List list = Arrays.asList(array); //list.size() = 3 int[] array1 = {1,2,3}; List list1 = Arrays.asList(array1); // list.size() = 1 //基本类型不支持范型，此处会变成int[1][] // debug 自测